Submission #907858

#TimeUsernameProblemLanguageResultExecution timeMemory
907858bobbilykingLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
362 ms4696 KiB
#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include<bits/stdc++.h> #include<math.h> using namespace std; typedef int ll; typedef double ld; typedef pair<ll, ll> pl; typedef vector<ll> vl; #define FD(i, r, l) for(ll i = r; i > (l); --i) #define K first #define V second #define G(x) ll x; cin >> x; #define GD(x) ld x; cin >> x; #define GS(s) string s; cin >> s; #define EX(x) { cout << x << '\n'; exit(0); } #define A(a) (a).begin(), (a).end() #define F(i, l, r) for (ll i = l; i < (r); ++i) #define NN 510 vector<pl> votes; vector<pl> votes2; ll n, k; ll take; // The final observation is this: // We can't actually "skip" votes in the optimal construction. // Since there's absolutely no world in which we skip b[i] but take b[i+1]. // If we don't make b[i] a comrade, we MUST make him a voter. ld dp[NN][NN]; ld dp2[NN][NN]; ld query(ll i, ll need) { if (need <= 0) return 0; return dp2[i][need]; } ld rec(ll i, ll bs) { if (bs == take) return query(i, k - i) / (1 + take); if (i == n) return 1e9; auto &DP = dp[i][bs]; if (DP != DP) { DP = 1e9; DP = min(DP, rec(i+1, bs) + ld(votes[i].V)/(1 + take)); DP = min(DP, rec(i+1, bs+1) + ld(votes[i].K)/(1 + bs)); } return DP; } int main(){ // freopen("a.in", "r", stdin); // freopen("a.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); cin >> n >> k; votes.resize(n); for (auto &[b, a]: votes) { cin >> a >> b; if (!~b) b = 1e9; } sort(A(votes)); F(i, 0, NN) F(j, 0, NN) dp2[i][j] = 1e12; F(suff, 0, n+1) { votes2 = votes; sort(suff + A(votes2), [&](const pl &a, const pl &b) { return a.V < b.V; }); ld sm = 0; ll take = 1; for (auto it = votes2.begin() + suff; it != votes2.end(); it++) { sm += it->V; dp2[suff][take++] = sm; } } ld ans = 1e9; for (take = 0; take <= n; take++) { memset(dp, -1, sizeof dp); ans = min(ans, rec(0, 0)); } cout << ans << endl; }
#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...