Submission #939855

#TimeUsernameProblemLanguageResultExecution timeMemory
939855Maite_MoraleLet's Win the Election (JOI22_ho_t3)C++14
61 / 100
899 ms3812 KiB
#include<bits/stdc++.h> #define F first #define S second #define MAX 500 #define oo 1e9+7 #define mod 1000000007 #define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(3); using namespace std; typedef long long ll; typedef long double db; #define pll pair<ll , ll> #define vll vector<ll> #define vvll vector<vll> #define vpll vector<pll> ll t,n,m; db dp[MAX][MAX]; pair<db,db> a[MAX]; int main(){ fast_in cin>>n>>m;t=n; for(int i=0;i<n;i++){ cin>>a[i].S>>a[i].F; if(a[i].F==-1){a[i].F=oo;t--;} } sort(a,a+n); db r=oo; for(int k=0;k<=min(t+1,m+1);k++){ for(int j=0;j<=k;j++){ for(int i=0;i+k<=m;i++){ dp[i][j]=oo; if(i+j==0)dp[i][j]=0; if(i>0 )dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i+j-1].S/(k+1)); if(j>0)dp[i][j]=min(dp[i][j],dp[i][j-1]+a[i+j-1].F/j); if(k==j){ // cout<<i<<" "<<j<<" "<<dp[i][j]<<" "; priority_queue<db> q; for(int h=i+k;h<n;h++){ q.push(-a[h].S); }db ans=0; for(int h=i+k;h<m;h++){ ans+=-q.top()/(k+1);q.pop(); }r=min(r,dp[i][k]+ans);//cout<<ans<<"\n"; } } } } cout<<r; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...