Submission #782731

#	Time	Username	Problem	Language	Result	Execution time	Memory
782731		ymm	Teams (IOI15_teams)	C++17	21 / 100	4062 ms	8948 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 200010;
int n;

namespace seg {
	vector<pii> vec;
	void add(int x, int y) {
		vec.push_back({x, y});
	}
	int get(int l1, int r1, int l2, int r2) {
		int ans = 0;
		for (auto [x, y] : vec)
			ans += l1 <= x && x < r1 && l2 <= y && y < r2;
		return ans;
	}
}

int cnt[N];

void init(int n, int a[], int b[]) {
	Loop (i,0,n) {
		seg::add(a[i], b[i]+1);
		cnt[a[i]]++;
		cnt[b[i]+1]--;
	}
	Loop (i,1,N)
		cnt[i] += cnt[i-1];
	::n = n;
}

int can(int m, int k[]) {
	ll sum = 0;
	Loop (i,0,m)
		sum += k[i];
	if (sum > n)
		return 0;
	sort(k, k+m);
	vector<int> dp(m);
	LoopR (i,0,m) {
		dp[i] = cnt[k[i]] - k[i];
		Loop (j,i+1,m) {
			int x = seg::get(0, k[i]+1, k[i]+1, k[j]+1);
			x += dp[j] - k[i];
			dp[i] = min(dp[i], x);
		}
		if (dp[i] < 0)
			return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:27:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   27 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:10:5: note: shadowed declaration is here
   10 | int n;
      |     ^

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