Submission #1295459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295459		am_aadvik	Lottery (JOI25_lottery)	C++20	0 / 100	5086 ms	5680 KiB

lottery

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<set>
#include<algorithm>
#include <iostream>
#include <cassert>
#include <cstdio>

void init(int N, int Q, std::vector<int> X, std::vector<int> Y);
int max_prize(int L, int R);
using namespace std;
#define SUBMIT 1

#ifndef SUBMIT
int main() {
	int N, Q;
	assert(scanf("%d %d", &N, &Q) == 2);

	std::vector<int> X(N), Y(N);
	for (int i = 0; i < N; i++) { assert(scanf("%d", &X[i]) == 1); }
	for (int i = 0; i < N; i++) { assert(scanf("%d", &Y[i]) == 1); }

	init(N, Q, X, Y);

	for (int k = 0; k < Q; k++) {
		int L, R;
		assert(scanf("%d %d", &L, &R) == 2);
		printf("%d\n", max_prize(L, R));
		fflush(stdout);
	}
}
#endif

vector<pair<int, int>> arr;
bool f = 0;
struct comp {
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
		if (a == b)return 0;
		return (a.first * b.second) > (b.first * a.second);
	}
};
void init(int n, int q, vector<int> x, vector<int> y) {
	for (int i = 0; i < n; ++i)
		arr.push_back({ x[i], y[i] });
}
int max_prize(int l, int r) {
	int s1 = 0, s2 = 0;
	for (int i = l; i <= r; ++i)
		s1 += arr[i].first, s2 += arr[i].second;
	if (s1 > s2) f = 0; else f = 1;
	multiset<pair<int, int>, comp> a;
	for (int i = l; i <= r; ++i) a.insert(arr[i]);
	int n = a.size(), ans = 0;
	while (1) {
		int cnt = 0;
		bool ok = 1;
		auto s = a;
		for (auto x : a) {
			s.erase(s.find(x));
			if (cnt < (n / 2)) { //make red
				if (x.first == 0) { ok = 0; break; }
				s.insert({ x.first - 1, x.second });
			}
			else { //make blue
				if (x.second == 0) { ok = 0; break; }
				s.insert({ x.first, x.second - 1 });
			}
			++cnt;
		}
		if (!ok) break;
		++ans, a = s;
		s1 = s2 = 0;
		for (auto x : a)
			s1 += x.first, s2 += x.second;
		if (s1 > s2) f = 0; else f = 1;
		multiset<pair<int, int>, comp> v;
	    for(auto x: a) v.insert(x);
	    a = v;
	}
	return ans;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23