Submission #1212987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212987		julia_08	Jelly Flavours (IOI20_jelly)	C++20	100 / 100	122 ms	157104 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e3 + 10;
const int MAXC = 1e4 + 10;

pair<int, int> jellies[MAXN];

int dp_1[MAXN][MAXC], dp_2[MAXN][MAXC];

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b){

  int n = a.size();

  for(int i=1; i<=n; i++) jellies[i] = {a[i - 1], b[i - 1]};

  sort(jellies + 1, jellies + n + 1);

  for(int i=1; i<=n; i++){
    for(int j=0; j<=y; j++){
      dp_1[i][j] = dp_1[i - 1][j];
      if(jellies[i].second <= j) dp_1[i][j] = max(dp_1[i][j], dp_1[i - 1][j - jellies[i].second] + jellies[i].first);
    }
  }

  for(int i=n; i>=1; i--){
    for(int j=0; j<=y; j++){
      dp_2[i][j] = dp_2[i + 1][j];
      if(jellies[i].second <= j) dp_2[i][j] = max(dp_2[i][j], dp_2[i + 1][j - jellies[i].second] + 1);
    }
  }

  int ans = 0, sum = 0;

  for(int i=1; i<=n; i++){

    sum += jellies[i].first;

    for(int j=0; j<=y; j++){
      if(sum - dp_1[i][j] <= x){
        ans = max(ans, i + dp_2[i + 1][y - j]);
      }
    }

  }

  return ans;
}

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