oj.uz

Submission #368221

# Submission time Handle Problem Language Result Execution time Memory
368221 2021-02-19T19:24:40 Z cheissmart Happiness (Balkan15_HAPPINESS) C++14
40 / 100
 646 ms 13760 KB 
//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<int> 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 2 ms 396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 269 ms 9024 KB Output is correct
7 Correct 267 ms 9044 KB Output is correct
8 Correct 325 ms 9112 KB Output is correct
9 Correct 454 ms 9460 KB Output is correct
10 Correct 646 ms 13136 KB Output is correct
11 Correct 224 ms 13580 KB Output is correct
12 Correct 221 ms 13760 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Incorrect 2 ms 396 KB Output isn't correct
7 Halted 0 ms 0 KB -