oj.uz

Submission #954458

# Submission time Handle Problem Language Result Execution time Memory
954458 2024-03-28T01:44:16 Z koukirocks Sure Bet (CEOI17_sure) C++17
100 / 100
 158 ms 8880 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;

int n;
vector<ldb> a,b;
vector<ldb> pa,pb;

ldb w(int l,int r) {
	return min(pa[l],pb[r]);
}

int main() {
//	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		ldb x,y;
		cin>>x>>y;
		a.push_back(x);
		b.push_back(y);
	}
	auto cmp=[&](ldb a,ldb b) {
		return a>b;
	};
	sort(all(a),cmp);
	sort(all(b),cmp);
	pa.resize(n+1);
	pb.resize(n+1);
	pa[0]=0;
	pb[0]=0;
	for (int i=1;i<=n;i++) {
		pa[i]=pa[i-1]+a[i-1];
		pb[i]=pb[i-1]+b[i-1];
	}
	ldb ans=0;
	for (int i=1;i<=2*n;i++) {
//		cout<<i<<" i\n"<<flush;
		int l=max(0,i-n),r=min(i,n);
		while (l<r) {
			int m1=(2*l+r)/3;
			int m2=(l+2*r+1)/3;
//			cout<<l<<" "<<m1<<" "<<m2<<" "<<r<<"\n"<<flush;
			if (w(m1,i-m1)<w(m2,i-m2)) l=m1+1;
			else r=m2-1;
		}
//		cout<<l<<" "<<i-l<<" "<<w(i,i-l)<<"\n";
		ans=max(ans,w(l,i-l)-i);
	}
	printf("%.4lf",(double)ans);
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 344 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 344 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 145 ms 8104 KB Output is correct
18 Correct 155 ms 8332 KB Output is correct
19 Correct 157 ms 8108 KB Output is correct
20 Correct 148 ms 8104 KB Output is correct
21 Correct 158 ms 8880 KB Output is correct
22 Correct 154 ms 8108 KB Output is correct
23 Correct 152 ms 8292 KB Output is correct
24 Correct 146 ms 8228 KB Output is correct
25 Correct 148 ms 8224 KB Output is correct
26 Correct 157 ms 8520 KB Output is correct