Submission #556966

#	Time	Username	Problem	Language	Result	Execution time	Memory
556966		luka1234	Let's Win the Election (JOI22_ho_t3)	C++14	16 / 100	284 ms	2344 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define db double 
using namespace std;
int n,m;
vector<pair<db,db> > a;
db dp[501][501];
bool comp(pair<db,db> p1,pair<db,db> p2){
	if(p1.ss<p2.ss)
	   return 1;
	else{
		if(p1.ss==p2.ss){
			if(p1.ff<p2.ff)
			   return 1;
			else
			   return 0;
		}
		else
		   return 0;
	}
}
void make(){
	for(int i=0;i<=500;i++){
			for(int j=0;j<=500;j++)
			    dp[i][j]=1e18;
		}
}
int main(){
	cin>>n>>m;
	a.push_back({-1,-1});
	for(int k=1;k<=n;k++){
		db x,y;
		cin>>x>>y;
		if(y==-1)
		   y=1e18;
		a.push_back({x,y});
	}
	db p1,p2;
	set<db> s;
	set<db>::iterator it;
	db das;
	db mn=1e18;
	db cnt=0;
	db cur=0;
	db cnt1=0;
	db ans1=0;
	sort(a.begin()+1,a.end());
	for(int k=1;k<=m;k++){
		ans1+=a[k].ff;
	}
	sort(a.begin()+1,a.end(),comp);
	for(int k=1;k<=m;k++){	
	    make();
		dp[0][0]=0;
		cnt1=0;
		for(int i=1;i<=n;i++){
			cnt1+=a[i].ff;
			dp[i][0]=cnt1;
			for(int j=1;j<=min(k,i);j++){
				p1=dp[i-1][j]+a[i].ff/(k+1);
				if(i-1<j)
				   p1=1e18;
				p2=dp[i-1][j-1]+a[i].ss/j; 
				if(a[i].ss==1e18)
				   p2=1e18;
				dp[i][j]=min(p1,p2);
				   
			}
		}
		s.clear();
		for(int i=n;i>=k;i--){
			das=m-i;
			cnt=0;
			if(das<0){
				mn=min(mn,dp[i][k]);
				s.insert(a[i].ff);
				continue;
			}
			if(s.size()<das){
				s.insert(a[i].ff);
				continue;
			}
			cur=dp[i][k];
			for(it=s.begin();it!=s.end();it++){
			    if(cnt==das)
				   break;
				db ddd=*it;
				cur+=(*it)/(k+1);
				cnt++;
				
			}
			s.insert(a[i].ff);
			mn=min(mn,cur);
		}
	}
	mn=min(mn,ans1);
	cout<<fixed<<setprecision(5)<<mn;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:89:8: warning: unused variable 'ddd' [-Wunused-variable]
   89 |     db ddd=*it;
      |        ^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23