Submission #941183

#TimeUsernameProblemLanguageResultExecution timeMemory
941183peterandvoiLet's Win the Election (JOI22_ho_t3)C++17
32 / 100
130 ms2644 KiB
#include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const int N = 505; int n, k; double dp[N][N]; pair<int, int> a[N]; double get(int mid) { for (int i = 0; i <= n; ++i) { for (int j = 0; j <= k - mid; ++j) { dp[i][j] = 1e9; } } dp[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= min(i, k - mid); ++j) { int x = i - j - 1; if (j > 0) { dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1.0 * a[i].first / (mid + 1)); } dp[i][j] = min(dp[i][j], dp[i - 1][j] + (x < mid ? 1.0 * a[i].second / (x + 1) : 0)); } } return dp[n][k - mid]; } signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cout << fixed << setprecision(15); cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i].first >> a[i].second; a[i].second = a[i].second == -1 ? 1001 : a[i].second; } sort(a + 1, a + n + 1, [&](auto x, auto y) { return x.second < y.second; }); int l = 1, r = n; double res = 1e9; for (int i = 1; i <= n; ++i) { r -= a[i].second == 1001; } r = min(r, k); for (int i = 0; i <= r; ++i) { res = min(res, get(i)); } cout << res; // while (l <= r) { // int mid = l + r >> 1; // if (get(mid - 1) >= get(mid)) { // res = mid; // l = mid + 1; // } else { // r = mid - 1; // } // } // cout << get(res); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:9: warning: unused variable 'l' [-Wunused-variable]
   52 |     int l = 1, r = 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...