Submission #526381

#	Time	Username	Problem	Language	Result	Execution time	Memory
526381		mosiashvililuka	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	1033 ms	18500 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=2009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,K,fx[509],PI,T;
pair <pair <int, int>, int> p[509];
pair <int, int> P[509];
long double pas,ans,A,B,C,D,E,JM,dp[109][109][109];
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].first.first>>p[i].first.second;ans+=p[i].first.first;p[i].second=i;
		if(p[i].first.second==-1) p[i].first.second=N;
	}
	for(i=1; i<=a; i++) swap(p[i].first.first,p[i].first.second);
	sort(p+1,p+a+1);
	for(i=1; i<=a; i++) swap(p[i].first.first,p[i].first.second);
	for(T=0; T<=K; T++){
		for(i=0; i<=a+1; i++){
			//for(j=0; j<=a+1-i; j++){
			for(j=0; j<=a+1; j++){
				for(ii=0; ii<=a+1; ii++){
					dp[ii][i][j]=500002.0;
				}
			}
		}
		dp[0][0][0]=0.0;
		for(ii=1; ii<=a; ii++){
			for(i=0; i<=ii; i++){
				if(i>K) break;
				for(j=0; j<=ii-i; j++){
					if(i+j>K||j>T) break;
					if(i+j<=ii-1){
						dp[ii][i][j]=min(dp[ii][i][j],dp[ii-1][i][j]);
					}
					if(i>0){
						A=p[ii].first.first;B=T+1;
						dp[ii][i][j]=min(dp[ii][i][j],dp[ii-1][i-1][j]+A/B);
					}
					if(j>0&&p[ii].first.second!=N){
						A=p[ii].first.second;B=j;
						dp[ii][i][j]=min(dp[ii][i][j],dp[ii-1][i][j-1]+A/B);
					}
				}
			}
		}
		//cout<<T<<" "<<dp[a][K-T][T]<<"\n";
		ans=min(ans,dp[a][K-T][T]);
	}
	cout<<setprecision(12)<<ans;
	return 0;
}

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