Submission #394598

#	Time	Username	Problem	Language	Result	Execution time	Memory
394598		shivensinha4	Teams (IOI15_teams)	C++17	0 / 100	99 ms	16120 KiB

teams

#include "bits/stdc++.h"
#include "teams.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'

int n;
vi endbefore, beginafter; // both inclusive: before -> <=, after -> >=

void init(int N, int A[], int B[]) {
	n = N;
	endbefore.resize(n); beginafter.resize(n);
	for_(i, 0, n) {
		endbefore[B[i]-1]++; beginafter[A[i]-1]++;
	}
	for_(i, 1, n) endbefore[i] += endbefore[i-1];
	for (int i = n-2; i >= 0; i--) beginafter[i] += beginafter[i+1];
}

int can(int M, int K[]) {
	for_(i, 0, M) K[i] -= 1;
	sort(K, K+M);
	
	int mx = 0;
	vi psum(M);
	for_(i, 0, M) psum[i] += K[i]+1;
	for_(i, 1, M) psum[i] += psum[i-1];
	
	// cout << "yoyo!" << endl;
	vi sufmx(M);
	for (int i = M-1; i >= 0; i--) {
		sufmx[i] = psum[i] + (K[i] < n-1 ? beginafter[K[i]+1] : 0);
		if (i < M-1) sufmx[i] = max(sufmx[i], sufmx[i+1]);
	}
	
	// if (K[M-1]+1 < n) {
		int ba = K[M-1]+1 < n ? beginafter[K[M-1]+1] : 0;
		int eb = K[M-1]-1 >= 0 ? endbefore[K[M-1]-1] : 0;
		mx = K[M-1]+1 + ba + eb;
	// }
	
	for_(i, 0, M-1) {
		int val = (K[i] >= 1 ? endbefore[K[i]-1] : 0) - (i > 0 ? psum[i-1] : 0) + sufmx[i];
		mx = max(mx, val);
	}
	
	return mx <= n;
}


// int main() {
// #ifdef mlocal
// 	freopen("teams.in", "r", stdin);
// #endif
	
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
	
// 	int t; cin >> t;
// 	cout << "got " << t << endl;
// 	while (t--) {
	
// 	}
// }

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