Submission #1137250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137250		TrinhKhanhDung	Let's Win the Election (JOI22_ho_t3)	C++20	21 / 100	172 ms	452 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define double long double

using namespace std;

//const int LOG =
//
//struct fen{
//    vector<pair<int, int>> tree;
//    int n;
//
//    fen(int _n = 0){
//        n = _n;
//        tree.resize(n + 3);
//    }
//
//    void update(int p, int a, int b){
//        for(; p <= n; p += p & -p){
//            tree[p].first += a;
//            tree[p].second += b;
//        }
//    }
//
//    int get(int k){
//        int p = 0, ans = 0;
//        for(int i = )
//    }
//};

void solve(){
    int N, K; cin >> N >> K;

    vector<pair<int, int>> a(N + 3);
    int possible = 0;
    for(int i = 1; i <= N; i++){
        cin >> a[i].first >> a[i].second;
        possible += a[i].second != -1;
    }
    sort(a.begin() + 1, a.begin() + N + 1);

    double ans = 0;
    for(int i = 1; i <= K; i++){
        ans += (double)a[i].first;
    }

    vector<bool> isDel(N + 3, false);
    vector<int> chosen(K + 3, 0);
    for(int t = 1; t <= min(possible, K); t++){
        double res = 1e9, pos = -1, ID = -1;
        for(int i = 1; i <= N; i++) if(!isDel[i] && a[i].second != -1){
            isDel[i] = true;
            double cur = 0;
            int id = 0;
            for(int j = 1; j < t; j++){
                if(chosen[j] < a[i].second){
                    id = j;
                }
            }
            for(int j = 1; j <= id; j++){
                cur += (double)chosen[j] / j;
            }
            cur += (double)a[i].second / (id + 1);
            for(int j = id + 1; j < t; j++){
                cur += (double)chosen[j] / (j + 1);
            }
            for(int j = 1, d = K - t; j <= N && d > 0; j++){
                if(!isDel[j]){
                    cur += (double)a[j].first / (t + 1);
                    d--;
                }
            }
            if(cur < res){
                res = cur;
                pos = i;
                ID = id;
            }
            isDel[i] = false;
        }
        isDel[pos] = true;
        if(ans > res){
            ans = res;
        }
        for(int i = t - 1; i > ID; i--){
            chosen[i + 1] = chosen[i];
        }
        chosen[ID + 1] = a[pos].second;
//        cout << pos << ' ' << ID << ' ';
//        for(int i = 1; i <= t; i++){
//            cout << chosen[i] << ' ';
//        }
//        cout << '\n';
    }

    cout << fixed << setprecision(15) << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("SHIP.inp", "r", stdin);
//    freopen("SHIP.out", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23