Submission #556548

#	Time	Username	Problem	Language	Result	Execution time	Memory
556548		mosiashvililuka	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	1189 ms	7872 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long double N=999999999.0;
int a,b,c,d,e,i,j,ii,jj,zx,xc,K,I,IA;
pair <long double, long double> p[509];
long double A,B,C,D,dp[509][509],dp2[509][509],pas=N;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>K;
	for(i=1; i<=a; i++){
		cin>>p[i].second>>p[i].first;
		if(p[i].first==-1) p[i].first=N;
	}
	sort(p+1,p+a+1);
	for(i=1; i<=a; i++) if(p[i].first==N) p[i].first=-1;
	for(i=1; i<=a; i++) swap(p[i].first,p[i].second);
	for(i=0; i<=a+1; i++){
		for(j=0; j<=a+1; j++) dp2[i][j]=N;
	}
	dp2[a+1][0]=0;
	for(i=a; i>=1; i--){
		for(j=0; j<=a; j++){
			dp2[i][j]=dp2[i+1][j];
			if(j>0) dp2[i][j]=min(dp2[i][j],dp2[i+1][j-1]+p[i].first);
		}
	}
	for(jj=0; jj<=K; jj++){
		for(i=0; i<=K; i++){
			I=min(i,K);
			for(j=0; j<=i; j++){
				dp[i][j]=N;
			}
		}
		dp[0][0]=0;
		for(i=1; i<=K; i++){
			for(j=0; j<=i; j++){
				if(j<i){
					A=dp[i-1][j]+p[i].first/(jj+1.0);
					if(dp[i][j]>A) dp[i][j]=A;
				}
				if(j!=0&&p[i].second!=-1){
					A=dp[i-1][j-1]+p[i].second/j;
					if(dp[i][j]>A) dp[i][j]=A;
				}
				/*if(j==jj){
					A=dp[i][j]+dp2[i+1][K-i]/(jj+1.0);
					if(pas>A) pas=A;
				}*/
			}
		}
		for(i=jj; i<=K; i++){
			A=dp[i][jj]+dp2[i+1][K-i]/(jj+1.0);
			if(pas>A) pas=A;
		}
	}
	cout<<setprecision(12)<<pas;
	return 0;
}

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