Submission #334162

#	Time	Username	Problem	Language	Result	Execution time	Memory
334162		rqi	Teams (IOI15_teams)	C++14	0 / 100	184 ms	30932 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define all(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define bk back()

const int MOD = 1000000007;

const int mx = 500005;

int N;
int A[mx];
int B[mx];

vpi students;
int pref[mx];
int suf[mx];

void init(int _N, int _A[], int _B[]) {
	N = _N;
	for(int i = 0; i < N; i++){
		A[i] = _A[i]; B[i] = _B[i];
	}

	for(int i = 0; i < N; i++){
		students.pb(mp(A[i], B[i]));
	}
	sort(all(students));

	for(int i = 0; i < N; i++){
		pref[students[i].s]++;
		suf[students[i].f]++;
	}

	for(int i = N; i >= 1; i--){
		suf[i]+=suf[i+1];
	}
	for(int i = 1; i <= N; i++){
		pref[i]+=pref[i-1];
	}

}

int can(int M, int _K[]) {
	vi K;
	int Ksum = 0;
	for(int i = 0; i < M; i++){
		K.pb(_K[i]);
		Ksum+=K[i];
		if(Ksum > N) return 0;
	}
	sort(all(K));
	vpi pv; // position, value --> csum
	for(int i = 0; i < M; i++){
		pv.pb(mp(K[i], 0));
		for(int j = i; j < M; j++){
			if(K[j] == K[i]){
				pv.bk.s+=K[j];
				i = j;
			}
			else{
				break;
			}
		}
	}

	for(int i = 1; i < sz(pv); i++){
		pv[i].s+=pv[i-1].s;
	}

	vi num1, num2;

	num1.pb(pref[pv[0].f-1]);
	for(int i = 1; i < sz(pv); i++){
		num1.pb(pref[pv[i].f-1]-pv[i-1].s);
	}
	for(int i = 0; i < sz(pv); i++){
		num2.pb(suf[pv[i].f+1]+pv[i].s);
	}

	int curmax = -MOD;
	int maxval = -MOD;
	for(int i = 0; i < sz(pv); i++){
		curmax = max(curmax, num1[i]);
		maxval = max(maxval, curmax+num2[i]);
	}

	if(maxval > N) return 0;

	return 1;
}

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