oj.uz

Submission #831506

# Submission time Handle Problem Language Result Execution time Memory
831506 2023-08-20T09:58:28 Z jasmin Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 739 ms 1048576 KB 
//JOI 2022 Final Round
#include<bits/stdc++.h>
using namespace std;
#define double long double

const int N=505;
double dp[N][N][N];

const double INF=1e9+7;

void init(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            for(int k=0; k<N; k++){
                dp[i][j][k] = INF;
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> b(n);
    for(int i=0; i<n; i++){

        cin >> a[i] >> b[i];
    }

    vector<int> sorted(n);
    iota(sorted.begin(), sorted.end(), 0);
    sort(sorted.begin(), sorted.end(), [&](int i, int j){
        if(b[i]==-1) return false;
        if(b[j]==-1) return true;

        return b[i]<b[j];
    });

    cout.precision(300);

    init();
    dp[0][0][0]=(double)0;
    for(int i=0; i<n; i++){
        int ind=sorted[i];
        //cout << i << ": " << ind << "\n";

        for(int x=0; x<=i+1; x++){
            for(int y=0; y<=x; y++){

                dp[i+1][x][y] = dp[i][x][y];

                if(0<x){

                    dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x-1][y] + (double)a[ind]/(double)(y+1));
                }
                if(0<y && b[ind]!=-1){

                    dp[i+1][x][y] = min(dp[i+1][x][y], dp[i][x-1][y-1] + (double)b[ind]/(double)y);
                    //cout << dp[i][x-1][y-1] << "\n";
                }

                //cout << i << " " << x << " "  << y << ": " << dp[i+1][x][y] << "\n";

            }
        }
    }

    double ans=INF;
    for(int y=0; y<=n; y++){
        ans = min(ans, dp[n][k][y]);
    }
    cout << ans << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 634 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 634 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 739 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 739 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 739 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 577 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 634 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -