제출 #1306606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306606		vtnoo	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	782 ms	4712 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=505,INF=1e9;
int A[MAXN],B[MAXN],v[MAXN];
void chmin(double &a,double b){
	if(a>b)a=b;
}
int main(){FIN;
	int n,k;cin>>n>>k;
	iota(v,v+n,0);
	fore(i,0,n){
		cin>>A[i]>>B[i];
		if(B[i]==-1)B[i]=INF;
	}
	sort(v,v+n,[&](int a,int b){
		return B[a]<B[b];
	});
	double ans=INF;
	fore(C,0,n){
		vector<vector<double>>ndp(n+1,vector<double>(C+1,INF));
		ndp[0][0]=0;
		fore(i,0,n){
			fore(l,0,C+1){
				//~ chmin(dp[i+1][j][l],dp[i][j][l]); -- no lo uso
				int ii=v[i];
				chmin(ndp[i+1][l],ndp[i][l]+(double)A[ii]/((double)C+1));
				if(l<C)chmin(ndp[i+1][l+1],ndp[i][l]+(double)B[ii]/((double)l+1));
			}
		}
		//~ cout<<"====================="<<endl;
		//~ fore(i,0,n){
			//~ fore(l,0,C+1)cout<<ndp[i][l]<<" ";
			//~ cout<<endl;
		//~ }
		vector<vector<double>>dp(n+1,vector<double>(k+1,INF));
		fore(i,0,n+1){
			if(i<=k)chmin(dp[i][i],ndp[i][C]);
			fore(j,0,k+1){
				if(i<n)chmin(dp[i+1][j],dp[i][j]);
				int ii=v[i];
				if(i<n&&j<k)chmin(dp[i+1][j+1],dp[i][j]+(double)A[ii]/((double)C+1));
			}
		}
		//~ fore(i,0,n){
			//~ fore(l,0,k+1)cout<<dp[i][l]<<" ";
			//~ cout<<endl;
		//~ }
		chmin(ans,dp[n][k]);
	}
	cout<<fixed<<setprecision(20)<<ans<<endl;
}

• 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