#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second
const int K=2e7;
int L[K],R[K],s[K];
const int sz=1<<19;
int nxt=1;
int add(int v, int l, int r, int i, int x) {
if (r-l==1) {
s[nxt]=s[v]+x;
return nxt++;
}
int m=(l+r)>>1;
if (i<m) {
if (L[v]==0) L[v]=nxt++;
int n = add(L[v],l,m,i,x);
L[nxt]=n, R[nxt]=R[v], s[nxt]=s[v]+x;
return nxt++;
} else {
if (R[v]==0) R[v]=nxt++;
int n = add(R[v],m,r,i,x);
L[nxt]=L[v], R[nxt]=n, s[nxt]=s[v]+x;
return nxt++;
}
}
int add(int v, int i, int x) {
return add(v,0,sz,i,x);
}
int sum(int v, int l, int r, int lx, int rx) {
if (lx<=l && r<=rx) return s[v];
int m=(l+r)>>1;
int lq = L[v] ? ( (lx>=m)?0:sum(L[v],l,m,lx,rx) ) : 0;
int rq = R[v] ? ( (rx<=m)?0:sum(R[v],m,r,lx,rx) ) : 0;
return lq+rq;
}
int sum(int v, int l, int r) {
if (l>=r) return 0;
return sum(v,0,sz,l,r);
}
int st[(int)5e5+55];
pi a[(int)5e5];
int n;
void init(int _n, int f[], int s[]) {
n=_n;
forn(i,n) a[i]={f[i],s[i]};
vector<vector<int>> v(n+1);
forn(i,n) v[a[i].s].pb(i);
st[n+1]=0;
for(int i=n;i>0;--i) {
st[i]=st[i+1];
for(auto&x:v[i]) {
auto t=add(st[i],a[x].f,1);
st[i]=t;
}
}
}
int can(int m, int k[]) {
vector<int> v(m);
forn(i,m) v[i]=k[i];
sort(all(v));
int s=0; forn(i,m) s+=k[i];
if (s>n) return 0;
vector<pi> z;
forn(i,m) {
if (!z.size()) {
z.pb({v[i],1}); continue;
}
if (v[i]==z.back().f) z.back().s++;
else z.pb({v[i],1});
}
int t=z.size();
vector<int> dp(t+1,-1e9);
dp[0]=0;
forn(i,t) {
int mx=i;
for(int j=i-1; j>=0; --j) {
if (dp[j]<=dp[mx]) continue;
int cnt;
if (mx==0) {
cnt=sum(st[z[i].f],0,z[i].f+1);
} else {
cnt=sum(st[z[i].f],z[mx-1].f+1,z[i].f+1);
}
dp[i+1]=max(dp[i+1],dp[mx]-cnt);
mx=j;
}
int cnt;
if (mx==0) {
cnt=sum(st[z[i].f],0,z[i].f+1);
} else {
cnt=sum(st[z[i].f],z[mx-1].f+1,z[i].f+1);
}
dp[i+1]=max(dp[i+1],dp[mx]-cnt);
dp[i+1]+=z[i].f*z[i].s;
if (dp[i+1]>0) return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:10:11: warning: declaration of 'second' shadows a global declaration [-Wshadow]
10 | #define s second
| ^
teams.cpp:55:32: note: in expansion of macro 's'
55 | void init(int _n, int f[], int s[]) {
| ^
teams.cpp:10:11: note: shadowed declaration is here
10 | #define s second
| ^~~~~~
teams.cpp:13:15: note: in expansion of macro 's'
13 | int L[K],R[K],s[K];
| ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:10:11: warning: declaration of 'second' shadows a global declaration [-Wshadow]
10 | #define s second
| ^~~~~~
teams.cpp:74:7: note: in expansion of macro 's'
74 | int s=0; forn(i,m) s+=k[i];
| ^
teams.cpp:10:11: note: shadowed declaration is here
10 | #define s second
| ^~~~~~
teams.cpp:13:15: note: in expansion of macro 's'
13 | int L[K],R[K],s[K];
| ^
teams.cpp:85:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
85 | int t=z.size();
| ~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
31468 KB |
Output is correct |
2 |
Correct |
48 ms |
31512 KB |
Output is correct |
3 |
Correct |
70 ms |
31532 KB |
Output is correct |
4 |
Correct |
72 ms |
31548 KB |
Output is correct |
5 |
Correct |
23 ms |
28800 KB |
Output is correct |
6 |
Correct |
23 ms |
28756 KB |
Output is correct |
7 |
Correct |
24 ms |
28748 KB |
Output is correct |
8 |
Correct |
23 ms |
28756 KB |
Output is correct |
9 |
Correct |
23 ms |
28620 KB |
Output is correct |
10 |
Correct |
22 ms |
28576 KB |
Output is correct |
11 |
Correct |
22 ms |
28620 KB |
Output is correct |
12 |
Correct |
23 ms |
28620 KB |
Output is correct |
13 |
Correct |
31 ms |
28876 KB |
Output is correct |
14 |
Correct |
36 ms |
29956 KB |
Output is correct |
15 |
Correct |
47 ms |
31184 KB |
Output is correct |
16 |
Correct |
44 ms |
31124 KB |
Output is correct |
17 |
Correct |
25 ms |
28824 KB |
Output is correct |
18 |
Correct |
25 ms |
28756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
31436 KB |
Output is correct |
2 |
Correct |
55 ms |
31464 KB |
Output is correct |
3 |
Correct |
125 ms |
31504 KB |
Output is correct |
4 |
Correct |
52 ms |
31564 KB |
Output is correct |
5 |
Correct |
51 ms |
28804 KB |
Output is correct |
6 |
Correct |
46 ms |
28788 KB |
Output is correct |
7 |
Correct |
29 ms |
28732 KB |
Output is correct |
8 |
Correct |
42 ms |
28748 KB |
Output is correct |
9 |
Correct |
23 ms |
28620 KB |
Output is correct |
10 |
Correct |
26 ms |
28564 KB |
Output is correct |
11 |
Correct |
28 ms |
28576 KB |
Output is correct |
12 |
Correct |
57 ms |
28656 KB |
Output is correct |
13 |
Correct |
105 ms |
28876 KB |
Output is correct |
14 |
Correct |
128 ms |
31016 KB |
Output is correct |
15 |
Correct |
74 ms |
31116 KB |
Output is correct |
16 |
Correct |
76 ms |
31176 KB |
Output is correct |
17 |
Correct |
45 ms |
28784 KB |
Output is correct |
18 |
Correct |
48 ms |
28756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
425 ms |
156420 KB |
Output is correct |
2 |
Correct |
438 ms |
156364 KB |
Output is correct |
3 |
Correct |
680 ms |
156488 KB |
Output is correct |
4 |
Correct |
426 ms |
156460 KB |
Output is correct |
5 |
Correct |
192 ms |
142292 KB |
Output is correct |
6 |
Correct |
181 ms |
142320 KB |
Output is correct |
7 |
Correct |
140 ms |
142236 KB |
Output is correct |
8 |
Correct |
177 ms |
142264 KB |
Output is correct |
9 |
Correct |
112 ms |
141244 KB |
Output is correct |
10 |
Correct |
107 ms |
141272 KB |
Output is correct |
11 |
Correct |
127 ms |
141232 KB |
Output is correct |
12 |
Correct |
205 ms |
141408 KB |
Output is correct |
13 |
Correct |
418 ms |
143124 KB |
Output is correct |
14 |
Correct |
692 ms |
153928 KB |
Output is correct |
15 |
Correct |
366 ms |
153288 KB |
Output is correct |
16 |
Correct |
372 ms |
153052 KB |
Output is correct |
17 |
Correct |
174 ms |
142548 KB |
Output is correct |
18 |
Correct |
168 ms |
142620 KB |
Output is correct |