Submission #1267715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267715		enzy	Let's Win the Election (JOI22_ho_t3)	C++20	0 / 100	676 ms	1114112 KiB

Main

#include<bits/stdc++.h>
#define lb long double
using namespace std;
const int maxn=502;
const int inf=1e8;
lb dp[maxn][maxn][maxn]; // dp[i][j][k]=min de tempo, para ter j votos e k colaboradores, com os i primeiros caras
pair<lb,lb> v[maxn];
bool cmp(pair<lb,lb> a, pair<lb,lb> b){
    if(a.second!=b.second){
        if(a.second==-1) return false;
        if(b.second==-1) return true;
        return a.second<b.second;
    }
    return a.first<b.first;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m; cin >> n >> m;
    for(int i=1;i<=n;i++) cin>> v[i].first >> v[i].second;
    sort(v+1,v+1+n,cmp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n+1;k++) dp[i][j][k]=inf;
    dp[1][0][1]=0; dp[1][1][1]=v[1].first; 
    if(v[1].second!=-1) dp[1][1][2]=v[1].second;
    lb resp=inf, sum=v[1].first;
    for(int i=2;i<=n;i++){
        if(i<=m) sum+=v[i].first;
        //cout << i << ": " << endl;
        for(int j=1;j<=i;j++){
            for(int k=1;k<=j+1;k++){
                dp[i][j][k]=min(dp[i-1][j][k],dp[i][j][k]);
                if(k!=j+1) dp[i][j][k]=min(dp[i-1][j-1][k]+(v[i].first/k),dp[i][j][k]);
                if(k!=1&&v[i].second!=-1) dp[i][j][k]=min(dp[i-1][j-1][k-1]+(v[i].second/(k-1)),dp[i][j][k]);
                if(j>=m) resp=min(resp,dp[i][j][k]);
                //cout << dp[i][j][k] << " ";
            }
            //cout << endl;
        }
        //cout << endl;
    }
    assert(sum>=resp);
    cout << fixed << setprecision(12) << resp << endl;
}

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