oj.uz

Submission #824471

# Submission time Handle Problem Language Result Execution time Memory
824471 2023-08-14T06:43:08 Z ttamx Let's Win the Election (JOI22_ho_t3) C++14
21 / 100
 592 ms 8396 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=505;

typedef long double ld;

int n,m;
ld a[N],b[N],dp[N][N],dp2[N][N];
vector<pair<ld,ld>> vec;
ld ans=LDBL_MAX;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
        if(b[i]<0)b[i]=DBL_MAX;
        vec.emplace_back(b[i],a[i]);
    }
    sort(vec.begin(),vec.end());
    for(int i=1;i<=m;i++)dp2[n+1][i]=LDBL_MAX;
    for(int i=1;i<=n;i++)tie(b[i],a[i])=vec[i-1];
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            dp2[i][j]=min(dp2[i+1][j],dp2[i+1][j-1]+a[i]);
        }
    }
    for(int i=2;i<=m;i++)dp[0][i]=LDBL_MAX;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=i;k++){
                dp[j][k]=dp[j-1][k]+a[j]/i;
                if(k>1&&b[j]<=1000)dp[j][k]=min(dp[j][k],dp[j-1][k-1]+b[j]/(k-1));
            }
            ans=min(ans,dp[j][i]+dp2[j+1][m-j]/i);
        }
    }
    cout << fixed << setprecision(12) << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 6 ms 3988 KB Output is correct
7 Correct 41 ms 6384 KB Output is correct
8 Correct 122 ms 7284 KB Output is correct
9 Correct 289 ms 8292 KB Output is correct
10 Correct 98 ms 7116 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 6 ms 3988 KB Output is correct
7 Correct 41 ms 6384 KB Output is correct
8 Correct 122 ms 7284 KB Output is correct
9 Correct 289 ms 8292 KB Output is correct
10 Correct 98 ms 7116 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 17 ms 4564 KB Output is correct
13 Correct 16 ms 4416 KB Output is correct
14 Correct 14 ms 4512 KB Output is correct
15 Correct 178 ms 7104 KB Output is correct
16 Correct 168 ms 6988 KB Output is correct
17 Correct 119 ms 7024 KB Output is correct
18 Correct 592 ms 8184 KB Output is correct
19 Correct 441 ms 8396 KB Output is correct
20 Correct 325 ms 8268 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 8296 KB Output is correct
2 Correct 548 ms 8220 KB Output is correct
3 Correct 511 ms 8300 KB Output is correct
4 Correct 529 ms 8296 KB Output is correct
5 Correct 509 ms 8192 KB Output is correct
6 Correct 507 ms 8296 KB Output is correct
7 Correct 523 ms 8300 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 6 ms 3988 KB Output is correct
7 Correct 41 ms 6384 KB Output is correct
8 Correct 122 ms 7284 KB Output is correct
9 Correct 289 ms 8292 KB Output is correct
10 Correct 98 ms 7116 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 17 ms 4564 KB Output is correct
13 Correct 16 ms 4416 KB Output is correct
14 Correct 14 ms 4512 KB Output is correct
15 Correct 178 ms 7104 KB Output is correct
16 Correct 168 ms 6988 KB Output is correct
17 Correct 119 ms 7024 KB Output is correct
18 Correct 592 ms 8184 KB Output is correct
19 Correct 441 ms 8396 KB Output is correct
20 Correct 325 ms 8268 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -