Submission #1267734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267734		enzy	Let's Win the Election (JOI22_ho_t3)	C++20	23 / 100	2601 ms	334096 KiB

Main

#include<bits/stdc++.h>
#define lb long double
using namespace std;
const int maxn=22;
const int inf=1e8;
lb dp[2][maxn][maxn][1000*maxn]; // dp[i][j][k]=min de tempo, para ter j votos e k colaboradores, com os i primeiros caras
pair<int,int> 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=0;i<=1;i++){
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n+1;k++)
                for(int l=0;l<=1000*n;l++) dp[i][j][k][l]=inf;
        dp[i][0][1][0]=0;
    }
    dp[1][0][1][0]=0; dp[1][1][1][v[1].first]=0; 
    if(v[1].second!=-1) dp[1][1][2][0]=v[1].second;
    lb resp=inf;
    if(m==1) resp=v[1].first;
    for(int i=2;i<=n;i++){
        //cout << i << ": " << endl;
        int par=i%2, inv=1^par;
        for(int j=1;j<=i;j++){
            for(int k=1;k<=j+1;k++){
                for(int l=0;l<=1000*j;l++){
                    lb help=v[i].second; help/=(k-1);
                    dp[par][j][k][l]=min(dp[inv][j][k][l],dp[par][j][k][l]);
                    if(k!=j+1&&l>=v[i].first) dp[par][j][k][l]=min(dp[inv][j-1][k][l-v[i].first],dp[par][j][k][l]);
                    if(k!=1&&v[i].second!=-1) dp[par][j][k][l]=min(dp[inv][j-1][k-1][l]+help,dp[par][j][k][l]);
                    if(j>=m){
                        lb a=l, b=k;
                        resp=min(resp,dp[par][j][k][l]+a/b);
                    }
                }
                //cout << dp[i][j][k] << " ";
            }
            //cout << endl;
        }
        //cout << endl;
    }
    cout << fixed << setprecision(16) << resp << endl;
}

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