oj.uz

Submission #534967

# Submission time Handle Problem Language Result Execution time Memory
534967 2022-03-09T08:01:38 Z Wither Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 9 ms 460 KB 
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define INF (ll)(9e18)
#define endl '\n'
//#define int double
using namespace std;
using pii=pair<int,int>;

 
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	set<int> data;
	int N,K;
	cin>>N>>K;;
	vector<pii> cty;
	vector<pii> clb;
	int c=0;
	
	int ab[N]={0};
	
	
	for (int i=0;i<N;i++){
		pii temp;
		cin>>temp.F;
		ab[i]=temp.F;
		temp.S=i;
		cty.push_back(temp);
		
		cin>>temp.F;
		if (temp.F!=-1){
			clb.push_back(temp);
			c+=1;
		}
	}
	sort(cty.begin(),cty.end());
	sort(clb.begin(),clb.end());
	double ans=0;
	for (int i=0;i<K;i++){
		ans+=cty[i].F;
	}
	if (c==0){
		cout<<ans;
	}
	else{
		double temp=1;
		double ansss=0; //chosen B
		int ub=min(c,K-1);
		double anssss=0;//chosen A
		for (int i=0;i<ub;i++){
			ansss+=(clb[i].F)/temp;
//			cout<<ansss<<endl;
			temp+=1;
			double anss=anssss;//chosen A
			data.insert(clb[i].S);
			
			int pn=temp-1;
			int ct=0;
			int id=0;				
			while (id<K-pn){
				if (data.count(cty[ct].S)){
					ct+=1;
					continue;
				}
				else{
					//cout<<cty[ct].S<<" ";
					anss+=cty[ct].F;
					ct+=1;
					id+=1;
				}
			}
			double nc=(anss+ab[clb[i].S])/(temp-1)+ansss-clb[i].F/temp;
			double yc=anss/temp+ansss;
//			cout<<nc<<" "<<yc<<endl;
			if (nc<yc){
//				cout<<clb[i].S<<" "<<"n"<<endl;
				ansss-=(clb[i].F)/temp;
				temp-=1;
				anssss+=ab[clb[i].S];
			}
			else{
//				cout<<clb[i].S<<" "<<"y"<<endl;
			}
			if (nc<ans){
				ans=nc;
			}
			if (yc<ans){
				ans=yc;
			}
//			cout<<ansss<<" "<<anssss<<endl;
		}
		cout<<ans;
	}	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 6 ms 340 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 2 ms 204 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Incorrect 1 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Incorrect 1 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Incorrect 1 ms 316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 3 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 6 ms 340 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 2 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 1 ms 308 KB Output is correct
29 Incorrect 1 ms 316 KB Output isn't correct
30 Halted 0 ms 0 KB -