제출 #1306412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306412		vtnoo	Let's Win the Election (JOI22_ho_t3)	C++20	56 / 100	337 ms	8964 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=105,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<vector<double>>>dp(n+1,vector<vector<double>>(k+1,vector<double>(C+1,INF)));
		dp[0][0][0]=0;
		fore(i,0,n){
			fore(j,0,k+1){
				fore(l,0,C+1){
					chmin(dp[i+1][j][l],dp[i][j][l]); // no lo uso
					int ii=v[i];
					if(j<k)chmin(dp[i+1][j+1][l],dp[i][j][l]+(double)A[ii]/((double)C+1));
					if(j<k&&l<C)chmin(dp[i+1][j+1][l+1],dp[i][j][l]+(double)B[ii]/((double)l+1));
				}
			}
		}
		chmin(ans,dp[n][k][C]);
	}
	cout<<fixed<<setprecision(20)<<ans<<endl;
}

• 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