Submission #1137231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137231		TrinhKhanhDung	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	69 ms	328 KiB

Main

#include <bits/stdc++.h>

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);
    double pre = 0.0;
    for(int t = 1; t <= min(possible, K); t++){
        double res = 1e9, pos = -1;
        for(int i = 1; i <= N; i++) if(!isDel[i] && a[i].second != -1){
            isDel[i] = true;
            double cur = (double)a[i].second / t;
            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;
            }
            isDel[i] = false;
        }
        isDel[pos] = true;
        if(ans > pre + res){
            ans = pre + res;
        }

        pre += (double)a[pos].second / t;
    }

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

int 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: 0 / 11
• Subtask 7: 0 / 23