oj.uz

Submission #394598

# Submission time Handle Problem Language Result Execution time Memory
394598 2021-04-27T05:21:50 Z shivensinha4 Teams (IOI15_teams) C++17
0 / 100
 99 ms 16120 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2572 KB Output is correct
2 Correct 9 ms 2636 KB Output is correct
3 Correct 8 ms 2664 KB Output is correct
4 Correct 12 ms 3732 KB Output is correct
5 Correct 6 ms 2660 KB Output is correct
6 Correct 6 ms 2636 KB Output is correct
7 Incorrect 7 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3048 KB Output is correct
2 Correct 17 ms 2992 KB Output is correct
3 Correct 32 ms 6084 KB Output is correct
4 Correct 12 ms 3960 KB Output is correct
5 Correct 14 ms 3148 KB Output is correct
6 Correct 14 ms 3132 KB Output is correct
7 Incorrect 14 ms 3148 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10600 KB Output is correct
2 Correct 57 ms 10224 KB Output is correct
3 Correct 99 ms 16120 KB Output is correct
4 Correct 50 ms 11344 KB Output is correct
5 Correct 44 ms 9988 KB Output is correct
6 Correct 44 ms 13508 KB Output is correct
7 Incorrect 45 ms 13460 KB Output isn't correct
8 Halted 0 ms 0 KB -