Submission #534967

#	Time	Username	Problem	Language	Result	Execution time	Memory
534967		Wither	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	9 ms	460 KiB

Main

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23