제출 #1264012

#제출 시각아이디문제언어결과실행 시간메모리
1264012goulthenLet's Win the Election (JOI22_ho_t3)C++20
10 / 100
66 ms2376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,a,b) for (int i = a; i <= b; ++i) #define pii pair<int,int> #define fi first #define se second #define pb push_back #define all(v) (v).begin(), (v).end() const int MAXN = 510; pii a[MAXN]; double dp[MAXN][MAXN]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); int n,k; cin >> n >> k; rep(i,1,n) { cin >> a[i].se >> a[i].fi; if (a[i].fi == -1) a[i].fi = 1e9; } sort(a+1, a+n+1); double ans = 1e9; rep(cc,0,k) { if (a[cc].fi == 1e9) break; rep(j,1,n) dp[0][j] = 1e9; rep(i,1,cc) { dp[i][0] = dp[i-1][0] + (double)a[i].fi/i; rep(j,1,n) dp[i][j] = dp[i-1][j]; } rep(i,cc+1,n) { rep(j,0,n) { dp[i][j] = dp[i-1][j]; if (j>0) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (double)a[i].se/(cc+1)); //cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; } } ans = min(ans, dp[n][k-cc]); } cout << fixed << setprecision(15) << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...