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
AC × 3
AC × 21
WA × 10
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