Submission #19723845
Source Code Expand
Copy
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
// declaration shortcuts
typedef long long int ll;
#define int ll
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997;
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI = 3.14159265358979323846L;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int n;
vector<pair<int,int>>v;
int total = 0;
bool check(int mid){
if(mid == 0) return true;
int have = 0;
multiset<pair<int,int>>s;
int left = total;
for(int i = 0; i < mid; i++){
have += v[i].first;
s.insert({v[i].second + v[i].first, v[i].first});
left -= (v[i].first + v[i].second);
}
for(int i = mid ; i < n; i++){
int curr_diff = left - have;
auto t = s.end();
t--;
pair<int,int> p = *t;
if((left - (v[i].second + v[i].first) + p.first - (have - p.second + v[i].first)) > curr_diff){
s.erase(s.find(p));
s.insert({v[i].first + v[i].second, v[i].first});
left -= (v[i].second + v[i].first) + p.first;
have -= p.second + v[i].first;
}
}
return left > have;
}
int32_t main(){
fastio();
cin >> n;
for(int i = 0; i < n; i++){
int a,b;
cin >> a >> b;
total += a + b;
v.push_back({a,b});
}
sort(all(v));
int low = 0, high = n;
int ans = 0;
while(low <= high){
int mid = (low + high) / 2;
if(check(mid)){
ans = mid;
low = mid + 1;
}else high = mid - 1;
}
cout << n - ans;
}
Submission Info
Submission Time |
|
Task |
D - Choose Me |
User |
rohitrj |
Language |
C++ (GCC 9.2.1) |
Score |
0 |
Code Size |
1825 Byte |
Status |
WA |
Exec Time |
984 ms |
Memory |
18704 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
01_small.txt, 02_small.txt, 03_small.txt, 04_small.txt, 05_small.txt, 06_small.txt, 07_small.txt, 08_small.txt, 09_small.txt, 10_small.txt, 11_small.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_large.txt, 17_large.txt, 18_large.txt, 19_large.txt, 20_large.txt, 21_large.txt, 22_large.txt, 23_large.txt, 24_large.txt, 25_large.txt, 26_max.txt, 27_max.txt, 28_max.txt, sample_01.txt, sample_02.txt, sample_03.txt |
Case Name |
Status |
Exec Time |
Memory |
01_small.txt |
AC |
6 ms |
3628 KB |
02_small.txt |
AC |
2 ms |
3604 KB |
03_small.txt |
AC |
2 ms |
3540 KB |
04_small.txt |
AC |
3 ms |
3500 KB |
05_small.txt |
AC |
2 ms |
3480 KB |
06_small.txt |
AC |
3 ms |
3552 KB |
07_small.txt |
AC |
3 ms |
3444 KB |
08_small.txt |
AC |
4 ms |
3548 KB |
09_small.txt |
AC |
4 ms |
3588 KB |
10_small.txt |
AC |
2 ms |
3600 KB |
11_small.txt |
AC |
3 ms |
3548 KB |
12_small.txt |
AC |
2 ms |
3444 KB |
13_small.txt |
AC |
3 ms |
3624 KB |
14_small.txt |
AC |
3 ms |
3476 KB |
15_small.txt |
AC |
2 ms |
3476 KB |
16_large.txt |
WA |
275 ms |
8896 KB |
17_large.txt |
WA |
859 ms |
14444 KB |
18_large.txt |
WA |
159 ms |
6296 KB |
19_large.txt |
WA |
121 ms |
6600 KB |
20_large.txt |
WA |
184 ms |
6716 KB |
21_large.txt |
WA |
144 ms |
5948 KB |
22_large.txt |
WA |
105 ms |
5392 KB |
23_large.txt |
WA |
12 ms |
3732 KB |
24_large.txt |
WA |
526 ms |
12832 KB |
25_large.txt |
WA |
984 ms |
15380 KB |
26_max.txt |
AC |
360 ms |
15832 KB |
27_max.txt |
AC |
671 ms |
18704 KB |
28_max.txt |
AC |
470 ms |
15776 KB |
sample_01.txt |
AC |
3 ms |
3552 KB |
sample_02.txt |
AC |
2 ms |
3576 KB |
sample_03.txt |
AC |
2 ms |
3548 KB |