Submission #434119

#	Time	Username	Problem	Language	Result	Execution time	Memory
434119		krist7599555	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	62 ms	460 KiB

jelly

#include <algorithm>
#include <cassert>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
typedef std::vector<int> Vec;
#define rep(i,a,b) for(auto i = a; i != b; ++i)
 
auto ckmax = [](auto& a, const auto& b) { return b>a?a=b,1:0; };
auto ckmin = [](auto& a, const auto& b) { return b<a?a=b,1:0; };
 
const int MN = 2e3+10;
const int MV = 1e4+10;
 
struct Data {
	public:
		int jelly_count, remain_b_value;
		Data inc() {return {jelly_count+1, remain_b_value};}
		void buy(int cost) {++jelly_count, remain_b_value -= cost;}
		bool operator > (const Data& o) const {
      return jelly_count > o.jelly_count || !(o.jelly_count > jelly_count) && remain_b_value > o.remain_b_value;
    }
};
Data dp[MV];
 
int find_maximum_unique(int xn, int yn, std::vector<int> an, std::vector<int> bn)
{
	int N = an.size();
 
	std::vector<int> ord(N);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&](int u, int v){return bn[u] < bn[v];});
 
  std::fill_n(dp, xn+1, Data({ 0, yn }));

	for (int i = 0; i != N; ++i) {
		int a = an[ord[i]]; // a = ? ? ? ? ?
		int b = bn[ord[i]]; // b = 1 2 3 4 5 
		for(int ai = 0; ai <= xn; ++ai) {
			if (dp[ai].remain_b_value >= b) dp[ai].buy(b);
      if (int nxa = ai + a; nxa <= xn) {
        const Data nx = dp[nxa].inc();
        if (nx > dp[ai]) {
          dp[ai] = nx;
        }
      }
		}
	}
	return dp[0].jelly_count;
}

inline int input() {
  int i; std::cin >> i; return i;
}

#ifdef KRIST_LOCAL

int main() {
  assert(4 == find_maximum_unique(6, 12, Vec({5, 1, 5, 6, 3}), Vec({3, 5, 4, 6, 7})));
  puts("pass");
  // using namespace std;
  // cin.sync_with_stdio(0);
  // int n = input();
  // int x = input();
  // int y = input();
  // std::vector<int> xn(n);
  // std::vector<int> yn(n);
  // rep(i, 0, n) xn[i] = input();
  // rep(i, 0, n) yn[i] = input();
  // cout << find_maximum_unique(x, y, xn, yn);
}

#endif

Compilation message (stderr)

jelly.cpp: In member function 'bool Data::operator>(const Data&) const':
jelly.cpp:22:76: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |       return jelly_count > o.jelly_count || !(o.jelly_count > jelly_count) && remain_b_value > o.remain_b_value;
      |                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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