# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
937889 | 2024-03-04T16:05:08 Z | danikoynov | Teams (IOI15_teams) | C++14 | 0 ms | 0 KB |
#include "teams.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; struct segment { ll l, r; segment(ll _l = 0, ll _r = 0) { l = _l; r = _r; } }; const ll maxn = 5e5 + 10; ll n; segment s[maxn]; void init(ll N, ll A[], ll B[]) { n = N; for (ll i = 1; i <= n; i ++) { s[i] = segment(A[i - 1], B[i - 1]); } } ll zeta(ll a, ll b) { ll cnt = 0; for (ll i = 1; i <= n; i ++) { if (s[i].l <= a && s[i].r >= a) continue; if (s[i].l <= b && s[i].r >= b) cnt ++; } return cnt; } ll dp[maxn]; ll can(ll M, ll K[]) { for (ll i = 0; i < M; i ++) { dp[i] = zeta(0, K[i]) - K[i]; for (ll j = 0; j < i; j ++) { dp[i] = min(dp[i], dp[j] + zeta(K[j], K[i]) - K[i]); } if (dp[i] < 0) return 0; } return 1; }