oj.uz

Submission #593569

# Submission time Handle Problem Language Result Execution time Memory
593569 2022-07-11T12:00:05 Z oleh1421 Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 19 ms 16744 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const ll inf=1e18;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=510;
const int Lg=16;
ld pref[N][N];
ld suf[N][N];
ll sum[N];
void solve(){
    int n,k;cin>>n>>k;
    vector<pair<ll,ll> >v;
    for (int i=1;i<=n;i++){
        ll a,b;cin>>a>>b;
        if (b==-1) b=inf;
        v.push_back({b,a});
    }
    sort(v.begin(),v.end());
    ld res=inf;
    vector<ll>u;
    for (int i=n-1;i>=0;i--){
        sum[i]=0;
        for (int j=0;j<k-i-1;j++) sum[i]+=u[j];
        u.push_back(v[i].second);
        sort(u.begin(),u.end());
    }
    for (int l=0;l<k;l++){
        for (int i=0;i<=n+1;i++){
            for (int j=0;j<=n+1;j++){
                pref[i][j]=suf[i][j]=inf;
            }
        }
        pref[0][0]=0.0;
        for (int i=0;i<n;i++){
            for (int j=0;j<=i;j++){
                pref[i+1][j]=min(pref[i+1][j],pref[i][j]+(ld)v[i].second/(l+1.0));
                if (v[i].first<inf) pref[i+1][j+1]=min(pref[i+1][j+1],pref[i][j]+(ld)v[i].first/(j+1.0));
            }
        }
        vector<ll>u;
        for (int i=n-1;i>=0;i--){
            ld cur=pref[i+1][l];
            cur+=(ld)sum[i]/(l+1.0);
            res=min(res,cur);
        }
        ld cur=0.0;
        for (int i=0;i<k;i++) cur+=u[i];
        res=min(res,cur);
    }
    cout<<setprecision(10)<<fixed<<res<<endl;
}
int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 16744 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -