Submission #1039514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039514		Hacv16	Jelly Flavours (IOI20_jelly)	C++17	Compilation error	0 ms	0 KiB

jelly

/*
 * Anyway, the first few subtasks are pretty easy. In particular, when there's only 
 * one person (e.g. when y=0) we can simply sort all flavours according to price (for
 * that person) and greedily pick from the small ones. From the constraints, one may
 * guess that the only way to AC this problem is to do a O(nx) dp (not a O(nxy) one).
 * Now, let dp[i][t] be the dp state when we only consider the first i flavours and
 * exactly t dollars are spent on store B. Each dp state already captures the cost in
 * B, so it may (?!) natural to maximize the num of unique flavours she can buy while
 * minimizing the amount of money spent on store A.
 * So, we first SORT the flavours based on their price in store A (from small to
 * large). We know that if we've selected a subset of jelly in B, she would just
 * greedily pick the remaining ones in store A (from left to right). Therefore, in
 * each dp state, we store the max num of flavours we can buy. In addition, among all
 * choices that can reach the max. num of flavours, we store the max amount of money
 * that can be left with in store A. It's not difficult to prove that this is indeed
 * a valid approach using greedy arguments. Nice problem!
 * 
 * Time Complexity: O(ny)       (or equivalently, O(nx))
 * Implementation 1
*/

#include <bits/stdc++.h>
#include "jelly.h"
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#define fr first
#define sc second

const int MAXN = 2005;
const int MAXM = 20050
const int INF = 0x3f3f3f3f;
 
int a[MAX], b[MAX];
pair<int, int> dp[MAX][MAXM];

int find_maximum_unique(int x, int y, vector<int> _a, vector<int> _b)
{
	int n = _a.size();
	
	vector<pair<int, int>> aux;

	for(int i = 0; i < n; i++)
		aux.emplace_back(_a[i], _b[i]);

	sort(aux.begin(), aux.end());

	for(int i = 1; i <= n; i++){
		a[i] = aux[i - 1].fr;
		b[i] = aux[i - 1].sc;
	}	

	dp[0][0] = {0, x};

  	for(int i = 1; i <= y; i++) 
  		dp[0][i] = {-INF, -INF};

  	int ans = 0;

  	for(int i = 1; i <= n; i++){
  		for(int j = 0; j <= y; j++){
  			dp[i][j] = dp[i - 1][j];

  			if(dp[i][j].sc >= a[i])
  				dp[i][j].fr++, dp[i][j].sc -= a[i];

  			if(j >= b[i]){
  				pair<int, int> t = dp[i - 1][j - b[i]];
  				t.fr++;

  				if(t.fr > dp[i][j].fr || (t.fr == dp[i][j].fr && t.sc > dp[i][j].sc)) 
  					dp[i][j] = t;
  			}

  			ans = max(ans, dp[i][j].fr);
  		}
  	}
 
	return ans;
}

Compilation message (stderr)

jelly.cpp:34:1: error: expected ',' or ';' before 'const'
   34 | const int INF = 0x3f3f3f3f;
      | ^~~~~
jelly.cpp:36:7: error: 'MAX' was not declared in this scope; did you mean 'MAXM'?
   36 | int a[MAX], b[MAX];
      |       ^~~
      |       MAXM
jelly.cpp:36:15: error: 'MAX' was not declared in this scope; did you mean 'MAXM'?
   36 | int a[MAX], b[MAX];
      |               ^~~
      |               MAXM
jelly.cpp:37:19: error: 'MAX' was not declared in this scope; did you mean 'MAXM'?
   37 | pair<int, int> dp[MAX][MAXM];
      |                   ^~~
      |                   MAXM
jelly.cpp: In function 'int find_maximum_unique(int, int, std::vector<int>, std::vector<int>)':
jelly.cpp:51:3: error: 'a' was not declared in this scope
   51 |   a[i] = aux[i - 1].fr;
      |   ^
jelly.cpp:52:3: error: 'b' was not declared in this scope
   52 |   b[i] = aux[i - 1].sc;
      |   ^
jelly.cpp:55:2: error: 'dp' was not declared in this scope
   55 |  dp[0][0] = {0, x};
      |  ^~
jelly.cpp:58:18: error: 'INF' was not declared in this scope
   58 |     dp[0][i] = {-INF, -INF};
      |                  ^~~
jelly.cpp:66:24: error: 'a' was not declared in this scope
   66 |      if(dp[i][j].sc >= a[i])
      |                        ^
jelly.cpp:69:14: error: 'b' was not declared in this scope
   69 |      if(j >= b[i]){
      |              ^