# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
887025 | 2023-12-13T13:41:02 Z | abcvuitunggio | 팀들 (IOI15_teams) | C++17 | 3409 ms | 348416 KB |
#include "teams.h" #include <bits/stdc++.h> using namespace std; const int INF=1e9; int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001]; vector <int> v[500001],ve; int update(int node, int l, int r, int u, int v){ int mid=(l+r)>>1,cur=++nNode; st[cur]=st[node]; le[cur]=le[node]; ri[cur]=ri[node]; if (l>=u&&r<=v){ st[cur]++; return cur; } if (u<=mid) le[cur]=update(le[node],l,mid,u,v); if (v>mid) ri[cur]=update(ri[node],mid+1,r,u,v); return cur; } int get(int node, int l, int r, int u, int v){ if (u>v||ve[v]<l||ve[u]>r) return -INF; if (l==r) return dp[u]-st[node]; int mid=(l+r)>>1; int x=upper_bound(ve.begin(),ve.end(),mid)-ve.begin(); return max(get(le[node],l,mid,u,min(v,x-1)),get(ri[node],mid+1,r,max(x,u),v))-st[node]; } void init(int N, int A[], int B[]){ n=N; for (int i=0;i<n;i++) v[A[i]].push_back(B[i]); for (int i=n;i;i--){ for (int j:v[i]){ nRoot++; root[nRoot]=update(root[nRoot-1],1,n,i,j); } R[i]=root[nRoot]; } } int can(int M, int K[]){ int sum=0; for (int i=0;i<M;i++){ sum+=K[i]; cnt[K[i]]=0; if (sum>n) return 0; } ve={0}; for (int i=0;i<M;i++){ if (!cnt[K[i]]) ve.push_back(K[i]); cnt[K[i]]+=K[i]; } sort(ve.begin(),ve.end()); for (int i=ve.size()-1;i>=0;i--) dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]]; return (!dp[0]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 14940 KB | Output is correct |
2 | Correct | 3 ms | 14940 KB | Output is correct |
3 | Correct | 4 ms | 14940 KB | Output is correct |
4 | Correct | 3 ms | 14940 KB | Output is correct |
5 | Correct | 4 ms | 14940 KB | Output is correct |
6 | Correct | 3 ms | 14940 KB | Output is correct |
7 | Correct | 3 ms | 14952 KB | Output is correct |
8 | Correct | 3 ms | 14940 KB | Output is correct |
9 | Correct | 4 ms | 14940 KB | Output is correct |
10 | Correct | 3 ms | 14940 KB | Output is correct |
11 | Correct | 3 ms | 14940 KB | Output is correct |
12 | Correct | 3 ms | 14940 KB | Output is correct |
13 | Correct | 3 ms | 14940 KB | Output is correct |
14 | Correct | 3 ms | 14940 KB | Output is correct |
15 | Correct | 3 ms | 14940 KB | Output is correct |
16 | Correct | 3 ms | 14940 KB | Output is correct |
17 | Correct | 3 ms | 14940 KB | Output is correct |
18 | Correct | 3 ms | 14940 KB | Output is correct |
19 | Correct | 3 ms | 14940 KB | Output is correct |
20 | Correct | 3 ms | 14940 KB | Output is correct |
21 | Correct | 3 ms | 14940 KB | Output is correct |
22 | Correct | 3 ms | 14940 KB | Output is correct |
23 | Correct | 3 ms | 14940 KB | Output is correct |
24 | Correct | 3 ms | 14940 KB | Output is correct |
25 | Correct | 3 ms | 14940 KB | Output is correct |
26 | Correct | 3 ms | 14940 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 72004 KB | Output is correct |
2 | Correct | 61 ms | 71864 KB | Output is correct |
3 | Correct | 60 ms | 72020 KB | Output is correct |
4 | Correct | 59 ms | 72272 KB | Output is correct |
5 | Correct | 22 ms | 40028 KB | Output is correct |
6 | Correct | 22 ms | 40176 KB | Output is correct |
7 | Correct | 22 ms | 40024 KB | Output is correct |
8 | Correct | 22 ms | 40172 KB | Output is correct |
9 | Correct | 9 ms | 19668 KB | Output is correct |
10 | Correct | 19 ms | 39916 KB | Output is correct |
11 | Correct | 20 ms | 41936 KB | Output is correct |
12 | Correct | 22 ms | 43988 KB | Output is correct |
13 | Correct | 34 ms | 60572 KB | Output is correct |
14 | Correct | 25 ms | 40332 KB | Output is correct |
15 | Correct | 55 ms | 71640 KB | Output is correct |
16 | Correct | 52 ms | 69712 KB | Output is correct |
17 | Correct | 28 ms | 48276 KB | Output is correct |
18 | Correct | 31 ms | 60500 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 486 ms | 72252 KB | Output is correct |
2 | Correct | 550 ms | 72532 KB | Output is correct |
3 | Correct | 110 ms | 75344 KB | Output is correct |
4 | Correct | 60 ms | 72272 KB | Output is correct |
5 | Correct | 473 ms | 40672 KB | Output is correct |
6 | Correct | 523 ms | 40960 KB | Output is correct |
7 | Correct | 455 ms | 40316 KB | Output is correct |
8 | Correct | 504 ms | 40320 KB | Output is correct |
9 | Correct | 8 ms | 19664 KB | Output is correct |
10 | Correct | 19 ms | 40144 KB | Output is correct |
11 | Correct | 26 ms | 42196 KB | Output is correct |
12 | Correct | 476 ms | 44476 KB | Output is correct |
13 | Correct | 194 ms | 61136 KB | Output is correct |
14 | Correct | 144 ms | 69456 KB | Output is correct |
15 | Correct | 127 ms | 70332 KB | Output is correct |
16 | Correct | 119 ms | 70200 KB | Output is correct |
17 | Correct | 130 ms | 52656 KB | Output is correct |
18 | Correct | 114 ms | 70908 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2926 ms | 333648 KB | Output is correct |
2 | Correct | 3409 ms | 333532 KB | Output is correct |
3 | Correct | 564 ms | 348416 KB | Output is correct |
4 | Correct | 403 ms | 340328 KB | Output is correct |
5 | Correct | 2609 ms | 149416 KB | Output is correct |
6 | Correct | 3120 ms | 149584 KB | Output is correct |
7 | Correct | 2634 ms | 149440 KB | Output is correct |
8 | Correct | 3088 ms | 149388 KB | Output is correct |
9 | Correct | 32 ms | 37312 KB | Output is correct |
10 | Correct | 97 ms | 164972 KB | Output is correct |
11 | Correct | 342 ms | 165760 KB | Output is correct |
12 | Correct | 1934 ms | 191596 KB | Output is correct |
13 | Correct | 811 ms | 270424 KB | Output is correct |
14 | Correct | 672 ms | 318920 KB | Output is correct |
15 | Correct | 519 ms | 326848 KB | Output is correct |
16 | Correct | 522 ms | 324708 KB | Output is correct |
17 | Correct | 412 ms | 255344 KB | Output is correct |
18 | Correct | 395 ms | 263352 KB | Output is correct |