Submission #836356

#TimeUsernameProblemLanguageResultExecution timeMemory
836356rainboyJelly Flavours (IOI20_jelly)C++17
100 / 100
45 ms584 KiB
#include "jelly.h" #include <vector> using namespace std; typedef vector<int> vi; const int N = 2000, T = 10000; int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } int aa[N], bb[N]; void sort(int *ii, int l, int r) { while (l < r) { int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp; while (j < k) if (aa[ii[j]] == aa[i_]) j++; else if (aa[ii[j]] < aa[i_]) { tmp = ii[i], ii[i] = ii[j], ii[j] = tmp; i++, j++; } else { k--; tmp = ii[j], ii[j] = ii[k], ii[k] = tmp; } sort(ii, l, i); l = k; } } int find_maximum_unique(int s_, int t_, vi aa_, vi bb_) { static int ii[N], dp[T + 1], tt[N + 1]; int n = aa_.size(); for (int i = 0; i < n; i++) { aa[i] = aa_[i], bb[i] = bb_[i]; ii[i] = i; } sort(ii, 0, n); for (int t = 0; t <= t_; t++) dp[t] = s_ + 1; dp[0] = 0; tt[0] = 0; for (int i = 0; i < n; i++) { int i_ = ii[i]; for (int t = t_; t >= 0; t--) { int s = dp[t]; if (s > s_) continue; dp[t] = min(s + aa[i_], s_ + 1); if (t + bb[i_] <= t_) dp[t + bb[i_]] = min(dp[t + bb[i_]], s); } tt[i + 1] = t_ + 1; for (int t = 0; t <= t_; t++) if (dp[t] <= s_) { tt[i + 1] = t; break; } } int k = 0; for (int i = n; i >= 0; i--) { for (int j = i; j + 1 < n && bb[ii[j]] > bb[ii[j + 1]]; j++) { int tmp; tmp = ii[j], ii[j] = ii[j + 1], ii[j + 1] = tmp; } if (tt[i] <= t_) { int t = tt[i], j = i; while (j < n && t + bb[ii[j]] <= t_) t += bb[ii[j++]]; k = max(k, j); } } return k; }
#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...