Submission #1049560

#TimeUsernameProblemLanguageResultExecution timeMemory
1049560ymmLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
714 ms4524 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x) #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x) typedef long long ll; typedef std::pair<int, int> pii; typedef std::pair<ll , ll > pll; using namespace std; const int N = 512; const ll inf = 1e15; double dp1_[N][N], dp2_[N][N]; auto dp1 = dp1_, dp2 = dp2_; pll a[N]; int n; #define SMIN(x, y) ((x) = min((x), (y))) double calc(ll col_tar, ll tot_tar) { dp1[0][0] = 0; Loop (pos,0,n) { Loop (col,0,pos+1) Loop (tot,col,pos+1) dp2[col][tot] = dp1[col][tot]; Loop (col,0,pos+2) dp2[col][pos+1] = inf; if (a[pos].first != inf) { Loop (col,0,pos+1) Loop (tot,col,pos+1) SMIN(dp2[col+1][tot+1], dp1[col][tot] + (double)a[pos].first / (col + 1)); } Loop (col,0,pos+1) Loop (tot,col,pos+1) SMIN(dp2[col][tot+1], dp1[col][tot] + (double)a[pos].second / (col_tar + 1)); swap(dp1, dp2); } return dp1[col_tar][tot_tar]; } int main() { cin.tie(0) -> sync_with_stdio(false); int k; cin >> n >> k; Loop (i,0,n) { cin >> a[i].second >> a[i].first; if (a[i].first == -1) a[i].first = inf; } sort(a, a + n); int l = 0, r = k-1; while (l < r) { int m = (l + r)/2; if (calc(m, k) > calc(m+1, k)) l = m+1; else r = m; } cout << fixed << setprecision(9); cout << calc(l, k) << '\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...