Submission #1157580
Source Code Expand
#include "bits/stdc++.h"
#ifndef err
#define err(...)(void)0
#endif
using namespace std;
using ll = long long;
using ull = decltype(1ull);
template<class T>int size(T&&a) { return a.size(); }
#define REP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.first,_l##t=a.second;t<_l##t;t++)
#define RREP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.second-1,_l##t=a.first;t>=_l##t;t--)
template<class B>pair<int, B>make_pair(B b) { return{ 0,b }; }
#define rep(t,...)REP(t,make_pair(__VA_ARGS__))
#define rrep(t,...)RREP(t,make_pair(__VA_ARGS__))
#define all(a)begin(a),end(a)
#define rall(a)a.rbegin(),a.rend()
void Calc();
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cin.exceptions(istream::failbit | istream::badbit);
cout << fixed << setprecision(15); Calc(); cout.flush(); return 0;
}
template<class A>void amax(A&a, A b) { a = max(a, b); }
template<class A>void amin(A&a, A b) { a = min(a, b); }
struct Scanner {
template<class A = string>A Next() { A a; cin >> a; return a; }
template<class A = int>vector<A>Array(int n) { vector<A>a(n); for (A&i : a) cin >> i; return a; }
string Line() const { string s; getline(cin, s); return s; }
template<class A>Scanner&operator,(A&a) { a = Next<A>(); return *this; }
template<class A>operator A() { return Next<A>(); }
}in;
/*---------------------------------------------------------------------*/
void Calc() {
int n = in;
struct Data {
int i, a;
void In() {
in, a;
}
bool operator<(const Data&d)const {
return a < d.a;
}
};
vector<Data> d(n);
rep(i, n) {
d[i].In();
d[i].i = i;
}
sort(all(d));
int cnt = 0;
auto solve = [&](int mid) {
ll now = d[mid].a;
rep(i, n) {
if (i == mid)continue;
if (d[i].a <= now * 2) {
now += d[i].a;
} else {
return false;
}
}
return true;
};
int l = 0, r = n;
while (r - l > 0) {
int mid = (r + l) / 2;
if (solve(mid)) r = mid;
else l = mid + 1;
}
err(l, r, n);
cout << (n-l) << endl;
}
Submission Info
Submission Time |
|
Task |
B - Colorful Creatures |
User |
oigami |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2139 Byte |
Status |
AC |
Exec Time |
20 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 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 |
AC |
19 ms |
1024 KB |
in10.txt |
AC |
8 ms |
640 KB |
in11.txt |
AC |
19 ms |
1024 KB |
in12.txt |
AC |
14 ms |
1024 KB |
in13.txt |
AC |
14 ms |
1024 KB |
in2.txt |
AC |
20 ms |
1024 KB |
in3.txt |
AC |
20 ms |
1024 KB |
in4.txt |
AC |
20 ms |
1024 KB |
in5.txt |
AC |
8 ms |
512 KB |
in6.txt |
AC |
17 ms |
1024 KB |
in7.txt |
AC |
19 ms |
1024 KB |
in8.txt |
AC |
17 ms |
1024 KB |
in9.txt |
AC |
3 ms |
384 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |