Submission #1083968

#TimeUsernameProblemLanguageResultExecution timeMemory
1083968dwuyLet's Win the Election (JOI22_ho_t3)C++14
100 / 100
95 ms604 KiB
/** - dwuy -       />  フ       |  _  _|       /`ミ _x ノ      /      |     /  ヽ   ?  / ̄|   | | |  | ( ̄ヽ__ヽ_)_)  \二つ **/ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) (int)((s).size()) #define MASK(k)(1LL<<(k)) #define TASK "test" #define int long long using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 505; int n, k; pii a[MX]; double f[2][505]; int32_t main(){ fastIO; //file(TASK); cin >> n >> k; for(int i=1; i<=n; i++){ cin >> a[i].se >> a[i].fi; if(a[i].fi == -1) a[i].fi = OO; } sort(a + 1, a + 1 + n); double ans = OO; for(int t=0; t<=k; t++) if(a[t].fi < OO){ for(int i=0; i<MX; i++) f[0][i] = f[1][i] = OO; f[0][0] = 0; for(int i=1; i<=n; i++){ int c = i&1; for(int j=0; j<=min(i, k-t); j++){ f[c][j] = f[c^1][j]; if(i - j <= t) f[c][j] += 1.0*a[i].fi/(i - j); if(j) f[c][j] = min(f[c][j], f[c^1][j-1] + 1.0*a[i].se/(t + 1)); } } ans = min(ans, f[n&1][k - t]); } cout << setprecision(9) << fixed << ans; return 0; }
#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...