Submission #992034

#	Time	Username	Problem	Language	Result	Execution time	Memory
992034		Otalp	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	2592 ms	15192 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define ld long double
#define pb push_back

pair<ld, ld> a[300100];
ll b[300100];
ll us[300100];
ll n, m;
ld dp[600][600], ob[600][600];


bool cmp(int x, int y){
    return a[x].ss < a[y].ss;
}

bool cmp2(pair<ld, ld> a, pair<ld, ld> b){
    return a.ss < b.ss;
}

void solve(){
    cin>>n>>m;
    int cnt = 0;
    vector<int> q;
    for(int i=1; i<=n; i++){
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ss == -1) a[i].ss = 1e9;
        else cnt ++; 
    }
    sort(a + 1, a + 1 + n, cmp2);
    ld ans = 1e18;
    for(int D=0; D<=n; D++){
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                dp[i][j] = ob[i][j] =   1e9;
            }
        }
        dp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int d=0; d<=n; d++){
                for(int k=0; k<=n; k++){
                    ob[d][k] = min(ob[d][k], dp[d][k]);
                    ob[d][k + 1] = min(ob[d][k + 1], dp[d][k] + a[i].ff / (D + 1));
                    if(a[i].ss != 1e9) ob[d + 1][k + 1] = min(ob[d + 1][k + 1], dp[d][k] + a[i].ss / (d + 1));
                }
            }
            
            for(int i=0; i<=n; i++){
                for(int j=0; j<=n; j++){
                    dp[i][j] = ob[i][j];
                    ob[i][j] = 1e9;
                }
            }
        }
        ans = min(ans, dp[D][m]);

    }
    cout<<fixed<<setprecision(9)<<ans<<'\n';
}


signed main(){
    solve();
}

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