Submission #1076374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076374		MilosMilutinovic	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	79 ms	816 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>

using namespace std;

void upd(pair<int, int> &a, pair<int, int> b) {
  if (a.first < b.first) {
    a = b;
  } else if (a.first == b.first && a.second < b.second) {
    a = b;
  }
}

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
  int n = (int) a.size();
  vector<pair<int, int>> dp(x + 1, make_pair(-n, -1));
  dp[0] = {0, y};
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return b[i] < b[j];
  });
  for (int i : order) {
    auto new_dp = dp;
    for (int w = 0; w + a[i] <= x; w++) {
      upd(new_dp[w + a[i]], make_pair(dp[w].first + 1, dp[w].second));
    }
    for (int w = 0; w <= x; w++) {
      if (dp[w].second < b[i]) {
        continue;
      }
      upd(new_dp[w], make_pair(dp[w].first + 1, dp[w].second - b[i]));
    }
    swap(dp, new_dp);
  }
  int res = 0;
  for (int i = 0; i <= x; i++) {
    res = max(res, dp[i].first);
  }
  return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32