제출 #1159232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159232		tw20000807	Let's Win the Election (JOI22_ho_t3)	C++20	11 / 100	238 ms	2684 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;
    });
    auto chk = [&](int t) -> double {
        vector< vector< double > > dp(n + 1, vector< double > (t + 2, 1e18));
        dp[0][1] = 0;
        for(int i = 0; i < n; ++i){
            for(int p = 1; p <= t; ++p){
                dp[i + 1][p] = min(dp[i + 1][p], dp[i][p] + 1.0 * v[i].X / t);
                dp[i + 1][p + 1] = min(dp[i + 1][p + 1], dp[i][p] + 1.0 * v[i].Y / p);
            }
        }
        return dp[n][t];
    };
    double ans = 1e18;
    for(int i = 1; i <= n + 1; ++i){
        ans = min(ans, chk(i));
    }
    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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23