Submission #368223

#	Time	Username	Problem	Language	Result	Execution time	Memory
368223		cheissmart	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	743 ms	16236 KiB

happiness

//https://usaco.guide/solutions/balkan-15-happiness?lang=cpp
#include "happiness.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "no-stack-protector", "unroll-loops")
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

ll sum[40];
multiset<ll> s[40];

void add(ll x, int type) {
	int bucket = __lg(x);
	if(type == 1) {
		s[bucket].insert(x);
		sum[bucket] += x;
	} else {
		s[bucket].erase(s[bucket].find(x));
		sum[bucket] -= x;
	}
}

bool happy() {
	ll SUM = 0;
	for(int i = 0; i < 40; i++) if(s[i].size()) {
		ll x = *s[i].begin();
		if(SUM + 1 < x) return false;
		if(s[i].size() > 1) {
			ll y = *next(s[i].begin());
			if(SUM + x + 1 < y) return false;
		}
		SUM += sum[i];
	}
	return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	for(int i = 0; i < 40; i++) {
		s[i].clear();
		sum[i] = 0;
	}
	for(int i = 0; i < coinsCount; i++)
		add(coins[i], 1);
	return happy();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i = 0; i < coinsCount; i++)
		add(coins[i], event);
	return happy();
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40