Submission #1017816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017816		AmirAli_H1	Teams (IOI15_teams)	C++17	34 / 100	4069 ms	10444 KiB

teams

// In the name of Allah

#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 19) + 4;

int n, q;
pii A[maxn]; pll Q[maxn];
ll dp[maxn]; vector<ll> ls;

void init(int Nx, int Ax[], int Bx[]) {
	n = Nx;
	for (int i = 0; i < n; i++) A[i] = Mp(Ax[i], Bx[i]);
}

int can(int Mx, int Qx[]) {
	q = Mx; ll sm = 0;
	for (int i = 0; i < q; i++) sm += Qx[i];
	if (sm > n) return 0;
	
	int sz = 0; sort(Qx, Qx + q);
	for (int i = 0; i < q; i++) {
		if (sz == 0) {
			Q[sz] = Mp(Qx[i], Qx[i]); sz++;
		}
		else {
			if (Q[sz - 1].F == Qx[i]) Q[sz - 1].S += Qx[i];
			else {
				Q[sz] = Mp(Qx[i], Qx[i]); sz++;
			}
		}
	}
	q = sz;
	
	for (int i = 1; i <= q; i++) {
		ls.clear();
		for (int k = 0; k < n; k++) {
			if (A[k].F <= Q[i - 1].F && A[k].S >= Q[i - 1].F) ls.pb(A[k].F);
		}
		sort(all(ls));
		dp[i] = len(ls) - Q[i - 1].S;
		
		int k = len(ls);
		for (int j = i - 1; j >= 1; j--) {
			while (k - 1 >= 0 && ls[k - 1] > Q[j - 1].F) k--;
			dp[i] = min(dp[i], dp[j] + (len(ls) - k) - Q[i - 1].S);
		}
		if (dp[i] < 0) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:14:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   14 | #define  len(x)     ((ll) (x).size())
      |                     ~^~~~~~~~~~~~~~~~
teams.cpp:64:11: note: in expansion of macro 'len'
   64 |   int k = len(ls);
      |           ^~~

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