Submission #1157282
Source Code Expand
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <complex>
#include <list>
#define pb push_back
#define lb lower_bound
#define lowbit(x) (x)&(-x)
#define forup(i,a,b) for(int i=(a);i<=(b);i++)
#define fordown(i,a,b) for(int i=(a);i>=(b);i--)
#define maxn 4000005
#define INF 1070000000
#define pa pair<double,int>
#define mp make_pair
#define pi acos(-1);
#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline void read(T& num){ num = 0; bool f = true;char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} num = f ? num: -num; }
int out[100];
template<class T> inline
void write(T x,char ch){ if (x==0) {putchar('0'); putchar(ch); return;} if (x<0) {putchar('-'); x=-x;} int num=0; while (x){ out[num++]=(x%10); x=x/10;} fordown(i,num-1,0) putchar(out[i]+'0'); putchar(ch); }
/*========================================================*/
int n,c,k;
int t[maxn];
struct per
{ int siz,col;}p[maxn];
bool cmp(per x,per y)
{return x.siz<y.siz;}
bool vis[maxn];
bool check(int x)
{ int sz=p[x].siz;
forup(i,1,n)
{ if(i==x) continue;
if(p[i].siz<=sz*2)
{ sz+=p[i].siz;}
else {return 0;}
}
return 1;
}
signed main()
{ cin>>n;
forup(i,1,n)
{ read(p[i].siz);
p[i].col=i;
}
sort(p+1,p+1+n,cmp);
//forup(i,1,n)
//sum[i]=sum[i-1]+p[i].siz;
int l=1,r=n;
while(l<r)
{ int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
int sta;
if(check(l)) sta=l;
else sta=r;
// cout<<sta<<endl;
forup(i,sta,n)
{ vis[p[i].col]=1; }
int cnt=0;
forup(i,1,n)
if(vis[i]) cnt++;
cout<<cnt;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Colorful Creatures |
User |
stalin |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2103 Byte |
Status |
TLE |
Exec Time |
2103 ms |
Memory |
4480 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
TLE |
2103 ms |
4352 KB |
in10.txt |
TLE |
2103 ms |
4352 KB |
in11.txt |
TLE |
2103 ms |
4352 KB |
in12.txt |
TLE |
2103 ms |
4352 KB |
in13.txt |
TLE |
2103 ms |
4352 KB |
in2.txt |
AC |
20 ms |
4480 KB |
in3.txt |
AC |
20 ms |
4480 KB |
in4.txt |
TLE |
2103 ms |
4352 KB |
in5.txt |
AC |
9 ms |
4352 KB |
in6.txt |
TLE |
2103 ms |
4352 KB |
in7.txt |
TLE |
2103 ms |
4352 KB |
in8.txt |
TLE |
2103 ms |
4352 KB |
in9.txt |
TLE |
2103 ms |
4352 KB |
sample1.txt |
TLE |
2103 ms |
2304 KB |
sample2.txt |
AC |
1 ms |
2304 KB |
sample3.txt |
TLE |
2103 ms |
2304 KB |