Submission #937325

#TimeUsernameProblemLanguageResultExecution timeMemory
937325Maite_MoraleLet's Win the Election (JOI22_ho_t3)C++14
32 / 100
897 ms834652 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,mn[MAX],m,l[MAX]; pll aux[MAX]; db dp[MAX][MAX][MAX],cost[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--;} aux[i]={a[i].S,a[i].F}; mn[i]=a[i].S; } sort(a,a+n);sort(mn,mn+n);sort(aux,aux+n); ll s=0,top=m-1; for(int i=0;i<n;i++){ aux[i]={aux[i].S,i}; if(i<m)s+=mn[i]; l[i]=i; }sort(aux,aux+n); for(int i=0;i<m;i++){ cost[i]=s; if(aux[i].S<top){ s-=mn[aux[i].S]; if(aux[i].S>0)l[aux[i].S]=l[aux[i].S-1]; } else{ s-=mn[top];top=l[top-1]; } } db r=cost[0]; cost[m]=s; for(int k=0;k<=min(t,m);k++){ for(int j=0;j<=k;j++){ for(int i=0;i+k<=m;i++){ dp[i][j][k]=oo; if(i+j==0)dp[i][j][k]=0; if(i>0)dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+a[i+j-1].S/(k+1)); if(j>0)dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+a[i+j-1].F/j); // if(i>0)cout<<dp[i-1][j][k]<<"+"<<a[i+j-1].S/k<<".\n"; // if(j>0)cout<<dp[i][j-1][k]<<"+"<<a[i+j-1].F/j<<"'\n"; if(j==k){ // cout<<i<<" "<<k<<" "<<" "<<dp[i][k][k]<<"+"<<cost[i+k]<<"\n"; if(cost[i+k]==0)r=min(r,dp[i][j][k]); else r=min(r,dp[i][j][k]+cost[i+k]/(k+1)); } } } } 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...