oj.uz

Submission #824486

# Submission time Handle Problem Language Result Execution time Memory
824486 2023-08-14T06:51:26 Z ttamx Let's Win the Election (JOI22_ho_t3) C++14
11 / 100
 670 ms 8300 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<=n;i++)tie(b[i],a[i])=vec[i-1];
    for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)dp2[i][j]=DBL_MAX;
    dp2[n+1][0]=0;
    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]);
        }
        ans=min(ans,dp2[i][m]);
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++)for(int k=0;k<=i;k++)dp[j][k]=LDBL_MAX;
        dp[0][1]=0;
        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
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 0 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 638 ms 8300 KB Output is correct
2 Correct 652 ms 8296 KB Output is correct
3 Correct 610 ms 8268 KB Output is correct
4 Correct 624 ms 8300 KB Output is correct
5 Correct 620 ms 8300 KB Output is correct
6 Correct 614 ms 8296 KB Output is correct
7 Correct 670 ms 8188 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 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -