Submission #1159219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159219		tw20000807	Let's Win the Election (JOI22_ho_t3)	C++20	16 / 100	2594 ms	2148 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;

void sol(){
    int n, k;
    cin >> n >> k;
    vector< pii > v(n);
    for(auto &[a, b] : v){
        cin >> a >> b;
        if(b == -1) b = llmx;
    }
    sort(all(v), [&](pii a, pii b){
        return a.Y < b.Y;
    });
    double ans = 1e18;
    auto chk = [&](int t) -> double {
        vector< vector< double > > dp(k + 2, vector< double > (t + 2, 1e18));
        dp[0][1] = 0;
        for(int i = 0; i < n; ++i){
            for(int p = k; p >= 0; --p) for(int q = t; q > 0; --q){
                dp[p + 1][q] = min(dp[p + 1][q], dp[p][q] + 1.0 * v[i].X / t);
                dp[p + 1][q + 1] = min(dp[p + 1][q + 1], dp[p][q] + 1.0 * v[i].Y / q);
            }
        }
        return dp[k][t];
    };
    int l = 1, r = k + 1;
    while(l <= r){
        int ml = (l + l + r) / 3, mr = (l + r + r) / 3;
        double tl = chk(ml), tr = chk(mr);
        // cerr << l << " " << r << " " << ml << ":" << tl << " " << mr << ":" << tr << "..\n";
        ans = min({ans, tl, tr});
        if(tl <= tr) r = mr - 1;
        else l = ml + 1;
    }
    cout << fixed << setprecision(10) << ans << "\n";
}
/*
3
3
1 5
2 3
4 5
// 5.5

7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1
// 32


5
3
4 -1
5 -1
6 -1
7 7
8 8
// 11.5

7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51
// 62.166


20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260
// 644.203517

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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