Submission #332818

#TimeUsernameProblemLanguageResultExecution timeMemory
332818cki86201Teams (IOI15_teams)C++17
77 / 100
4108 ms150892 KiB
#include <bits/stdc++.h> #include "teams.h" using namespace std; #define Fi first #define Se second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(), (x).end() #define pb push_back #define szz(x) (int)(x).size() #define rep(i, n) for(int i=0;i<(n);i++) typedef tuple<int, int, int> t3; int rt[500050], tn; int T[10000010], N; int ch[10000010][2]; vector <int> bl[500050]; int Ins(int prt, int l, int r, int x) { int me = ++tn; T[me] = T[prt] + 1; ch[me][0] = ch[prt][0]; ch[me][1] = ch[prt][1]; if(l != r) { int m = (l + r) >> 1; if(x <= m) ch[me][0] = Ins(ch[prt][0], l, m, x); else ch[me][1] = Ins(ch[prt][1], m+1, r, x); } return me; } int read(int prt, int l, int r, int s, int e) { if(s <= l && r <= e) return T[prt]; int m = (l + r) >> 1, res = 0; if(s <= m) res += read(ch[prt][0], l, m, s, e); if(m < e) res += read(ch[prt][1], m+1, r, s, e); return res; } int Read(int x, int l, int r) { return read(rt[x], 1, N, l, r); } void init(int N, int A[], int B[]) { ::N = N; rt[0] = ++tn; for(int i=0;i<N;i++) bl[A[i]].pb(B[i]); for(int i=1;i<=N;i++) { rt[i] = rt[i-1]; for(int r : bl[i]) { rt[i] = Ins(rt[i], 1, N, r); } } } int dp[200020]; int can(int M, int K[]) { sort(K, K+M, greater<>()); vector <pii> V; for(int i=0, s=0;i<M;i++) { if(szz(V) && V.back().Fi == K[i]) V.back().Se += K[i]; else V.pb({K[i], K[i]}); s += K[i]; if(s > N) return 0; } for(int i=0;i<szz(V);i++) { auto [x, cnt] = V[i]; dp[i] = Read(x, x, N) - cnt; for(int j=0;j<i;j++) { dp[i] = min(dp[i], dp[j] + Read(x, x, V[j].Fi - 1) - cnt); } if(dp[i] < 0) return 0; } return 1; }

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:45:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   45 | void init(int N, int A[], int B[]) {
      |                                  ^
teams.cpp:17:18: note: shadowed declaration is here
   17 | int T[10000010], N;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...