Submission #828350

#TimeUsernameProblemLanguageResultExecution timeMemory
828350RaresFelixLet's Win the Election (JOI22_ho_t3)C++17
10 / 100
536 ms984740 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 501; const double INF = 1e18; struct stat { double a, b; bool operator < (const stat &rhs) const { return tie((b < 0) ? INF : b, a) < tie((rhs.b < 0) ? INF : rhs.b, rhs.a); } } A[MN]; int n, k; double DP[MN][MN][MN]; int main() { cin >> n >> k; for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) for(int w = 0; w <= k; ++w) DP[i][j][w] = INF; for(int i = 1; i <= n; ++i) { cin >> A[i].a >> A[i].b; } sort(A + 1, A + n + 1); DP[0][1][0] = 0; for(int i = 0; i < n; ++i) { for(int j = 1; j <= n; ++j) { for(int w = 0; w <= k; ++w) { ///propag (i, j, w) in orasul i + 1 DP[i + 1][j][w] = min(DP[i + 1][j][w], DP[i][j][w]); DP[i + 1][j][w + 1] = min(DP[i + 1][j][w + 1], DP[i][j][w] + (A[i + 1].a / double(j))); if(A[i + 1].b >= 0) DP[i + 1][j + 1][w + 1] = min(DP[i + 1][j + 1][w + 1], DP[i][j][w] + (A[i + 1].b / double(j))); } } } double re = INF; for(int j = 1; j <= n; ++j) re = min(re, DP[n][j][k]); cout << fixed << setprecision(10) << re << "\n"; 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...