Submission #1276247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276247		enzy	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	488 ms	5464 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define lb long double
const int maxn=510;
const int inf=1e9+7;
bool cmp(pair<int,int> x, pair<int,int> y){
    if(x.second!=y.second){
        if(x.second==-1) return false;
        if(y.second==-1) return true;
        return x.second<y.second;
    }
    return x.first>y.first;
}
int a[maxn], b[maxn], dp1[maxn][maxn];
lb dp2[maxn][maxn];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k; cin >> n >> k;
    vector<pair<int,int>>process(n);
    for(pair<int,int> &p : process) cin >> p.first >> p.second;
    sort(process.begin(),process.end(),cmp);
    for(int i=1;i<=n;i++){
        a[i]=process[i-1].first;
        b[i]=process[i-1].second;
    }
    memset(dp1,1,sizeof(dp1));
    dp1[n+1][0]=0;
    for(int i=n;i>=1;i--){
        for(int j=0;j<=n;j++){
            dp1[i][j]=dp1[i+1][j];
            if(j) dp1[i][j]=min(dp1[i][j],dp1[i+1][j-1]+a[i]);
        }
    }
    lb resp=dp1[1][k];
    for(int x=1;x<=k;x++){ //pegar x caras para serem colaboradores
        if(b[x]==-1) break;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=x;j++) dp2[i][j]=inf;
        //cout << x << ":\n";
        dp2[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=x;j++){
                dp2[i][j]=dp2[i-1][j];
                lb c1=(lb)a[i]/(lb)(x+1), c2=inf;
                if(j&&b[i]!=-1) c2=(lb)b[i]/(lb)j;
                //cout << c1 << " " << c2 << endl;
                dp2[i][j]=min(dp2[i-1][j]+c1,dp2[i-1][j-1]+c2);
            }
            lb aux=0;
            if(i<=k) aux=dp1[i+1][k-i];
            aux/=(lb)(x+1);
            resp=min(resp,dp2[i][x]+aux);
            //cout << i << ' ' << dp2[i][x] << " " << aux << endl;
        }
    }
    cout << fixed << setprecision(16) << resp << endl; 
}

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