Submission #636882

#TimeUsernameProblemLanguageResultExecution timeMemory
636882danikoynovLet's Win the Election (JOI22_ho_t3)C++14
10 / 100
2 ms340 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 510; struct city { int a, b, idx; }c[maxn], ct[maxn]; int n, k, used[maxn]; bool cmpa(city c1, city c2) { return c1.a < c2.a; } bool cmpb(city c1, city c2) { if (c1.b != -1 && c2.b != -1) return c1.b < c2.b; if (c1.b != -1) return true; if (c2.b != -1) return false; return c1.idx < c2.idx; } void solve() { cin >> n >> k; int col = 0; for (int i = 1; i <= n; i ++) { cin >> c[i].a >> c[i].b; if (c[i].b != -1) col ++; c[i].idx = i; ct[i] = c[i]; } sort(c + 1, c + n + 1, cmpa); sort(ct + 1, ct + n + 1, cmpb); double best = 1e18; for (int f = 0; f <= min(col, k); f ++) { double ans = 0.0, hp = 0; for (int i = 1; i <= n; i ++) used[i] = 0; for (int i = 1; i <= f; i ++) { ans = ans + (double)(ct[i].b) / (hp + 1.0); used[ct[i].idx] = 1; hp ++; } ///cout << f << " - " << ans << endl; int sum = 0; for (int i = 1; i <= n && sum < k - (int)f; i ++) { if (used[c[i].idx]) continue; ans = ans + (double)(c[i].a) / (hp + 1.0); sum ++; } best = min(best, ans); } printf("%0.6f\n", best); } int main() { solve(); 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...