oj.uz

Submission #658844

# Submission time Handle Problem Language Result Execution time Memory
658844 2022-11-15T04:00:24 Z Darren0724 Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 1417 ms 4608 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define double long double
int INF=1e9;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    int k;cin>>k;
    vector<pair<int,int>> v(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        if(v[i].second==-1){
            v[i].second=INF;
        }
    }
    sort(all(v),[&](pair<int,int> a,pair<int,int> b){
        return a.second<b.second;
    });
    double ans=INF;
    for(int t=0;t<k;t++){
        vector<vector<double>> dp(t+1,vector<double>(n+1,INF));
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            dp[0][i]=dp[0][i-1]+v[i].first/(t+1);
        }
        for(int i=1;i<=t;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][j-1]+(double)v[j].first/(t+1));
            }
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(double)v[j].second/i);
            }
        }
        double total=0;
        double mn=INF;
        priority_queue<double,vector<double>,greater<double>> pq;
        for(int i=n;i>k;i--){
            pq.push((double)v[i].first/(t+1));
        }
        for(int i=k;i>=t;i--){
            mn=min(mn,dp[t][i]+total);
            pq.push((double)v[i].first/(t+1));
            total+=pq.top();
            pq.pop();
        }
        ans=min(ans,mn);
    }
    cout<<setprecision(9)<<ans<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 16 ms 788 KB Output is correct
6 Correct 86 ms 1336 KB Output is correct
7 Correct 328 ms 2280 KB Output is correct
8 Correct 761 ms 3360 KB Output is correct
9 Correct 1417 ms 4348 KB Output is correct
10 Correct 660 ms 3416 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 16 ms 788 KB Output is correct
6 Correct 86 ms 1336 KB Output is correct
7 Correct 328 ms 2280 KB Output is correct
8 Correct 761 ms 3360 KB Output is correct
9 Correct 1417 ms 4348 KB Output is correct
10 Correct 660 ms 3416 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 127 ms 1560 KB Output is correct
13 Correct 126 ms 1596 KB Output is correct
14 Correct 117 ms 1496 KB Output is correct
15 Correct 662 ms 3172 KB Output is correct
16 Correct 655 ms 3160 KB Output is correct
17 Correct 644 ms 3208 KB Output is correct
18 Correct 1306 ms 4484 KB Output is correct
19 Correct 1315 ms 4416 KB Output is correct
20 Correct 1320 ms 4276 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1333 ms 4608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 16 ms 788 KB Output is correct
6 Correct 86 ms 1336 KB Output is correct
7 Correct 328 ms 2280 KB Output is correct
8 Correct 761 ms 3360 KB Output is correct
9 Correct 1417 ms 4348 KB Output is correct
10 Correct 660 ms 3416 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 127 ms 1560 KB Output is correct
13 Correct 126 ms 1596 KB Output is correct
14 Correct 117 ms 1496 KB Output is correct
15 Correct 662 ms 3172 KB Output is correct
16 Correct 655 ms 3160 KB Output is correct
17 Correct 644 ms 3208 KB Output is correct
18 Correct 1306 ms 4484 KB Output is correct
19 Correct 1315 ms 4416 KB Output is correct
20 Correct 1320 ms 4276 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 324 KB Output is correct
23 Correct 0 ms 316 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 312 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Incorrect 0 ms 212 KB Output isn't correct
31 Halted 0 ms 0 KB -