Submission #604298

#	Time	Username	Problem	Language	Result	Execution time	Memory
604298		cheissmart	Teams (IOI15_teams)	C++14	0 / 100	4062 ms	25708 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

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

const int INF = 1e9 + 7, N = 5e5 + 7;

int n;
vi G[N];

int qry(int i, int lb, int rb) {
	assert(lb <= rb);
	// l <= i && r in [lb, rb]
	int cnt = 0;
	for(int l = 1; l <= i; l++)
		for(int r:G[l])
			cnt += lb <= r && r <= rb;
	return cnt;
}

void init(int _n, int a[], int b[]) {
	n = _n;
	for(int i = 0; i < n; i++) {
		G[a[i]].PB(b[i]);
	}
}

int can(int m, int a[]) {
	if(accumulate(a, a + m, 0LL) > n) return 0;
	sort(a, a + m);

	V<pi> aux;
	for(int i = 0; i < m;) {
		int j = i;
		while(i < m && a[i] == a[j]) i++;
		aux.EB(a[j], (i - j) * a[j]);
	}

	for(int i = 0; i + 1 < SZ(aux); i++) {
		int all = qry(aux[i].F, aux[i].F, n);
		int self = qry(aux[i].F, aux[i].F, aux[i + 1].F - 1);
		if(aux[i].S > all) return 0;
		if(aux[i].S > self) {
			aux[i + 1].S += aux[i].S - self;
		}
	}
	return qry(aux.back().F, aux.back().F, n) >= aux.back().S;

}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23