QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #684883 | #9258. Huawei Frequencies Selection | S00021 | TL | 3ms | 16200kb | C++14 | 1.5kb | 2024-10-28 16:22:36 | 2024-10-28 16:22:37 |
Judging History
answer
#include<bits/stdc++.h>
#define N 2000005
#define INF 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define MP make_pair
#define lb(x) ((x)&-(x))
using namespace std;
int n,K,a[N],f[N],s0[N],s1[N];
struct BIT1{ int T[N]={0};
void cl(){for(int i=0;i<=n+1;i++) T[i]=-INF;}
void add(int x,int d){x++; for(int i=x;i<=n+1;i+=lb(i)) T[i]=max(T[i],d);}
int ask(int x){ if(x<0) return -INF;
x++; int ret=-INF; for(int i=x;i;i-=lb(i)) ret=max(ret,T[i]); return ret;}
}T1;
struct BIT2{ int T[N]={0};
void cl(){for(int i=0;i<=n+1;i++) T[i]=-INF;}
void add(int x,int d){x++; for(int i=x;i;i-=lb(i)) T[i]=max(T[i],d);}
int ask(int x){ if(x<0) return -INF;
x++; int ret=-INF; for(int i=x;i<=n+1;i+=lb(i)) ret=max(ret,T[i]); return ret;}
}T2;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
scanf("%d%d",&n,&K); int c0=0,c00=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),c00+=(a[i]>0),c0+=(a[i]==0);
for(int i=1;i<=n;i++){
s0[i]=s0[i-1]+(a[i]==0);
s1[i]=s1[i-1]+(a[i]==1);
}if(c0>=K) return !printf("0");
memset(f,0xcf,sizeof(f));
f[0]=0,T1.cl(),T2.cl(),T1.add(0,0),T2.add(0,0);
for(int i=1,m0=0,m1=0;i<=n;i++){
if(a[i]==0) m0=i; if(a[i]==1) m1=i;
for(int j=0;j<i;j++){
bool t0=(s0[i]-s0[j]>0);
bool t1=(s1[i]-s1[j]>0);
if(t0&&!t1) continue;
f[i]=max(f[i],f[j]+1);
}if(!m0&&!m1) f[i]=i;
T1.add(i,f[i]),T2.add(i,f[i]);
}if(f[n]>=K||c00==n) return !printf("1");
return !printf("2");
}/*
20 15
1 2 2 0 3 3 2 2 2 0 1 1 2 1 3 1 0 2 2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16136kb
input:
2 2 0 2
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 3ms
memory: 16160kb
input:
3 1 2 1 1
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 16144kb
input:
3 2 1 3 0
output:
2
result:
ok answer is '2'
Test #4:
score: 0
Accepted
time: 3ms
memory: 16144kb
input:
20 15 1 2 2 0 3 3 2 2 2 0 1 1 2 1 3 1 0 2 2 1
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 16196kb
input:
9 4 0 0 2 1 3 1 3 0 3
output:
1
result:
ok answer is '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 14096kb
input:
19 17 1 0 0 3 0 0 2 3 1 0 3 3 3 1 3 0 0 3 1
output:
2
result:
ok answer is '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 16084kb
input:
17 15 0 0 3 0 1 1 2 1 2 1 1 1 3 0 0 1 0
output:
2
result:
ok answer is '2'
Test #8:
score: 0
Accepted
time: 3ms
memory: 16128kb
input:
6 5 2 1 3 0 1 0
output:
2
result:
ok answer is '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 14028kb
input:
16 12 0 2 0 1 2 0 0 0 1 3 3 0 1 0 3 1
output:
2
result:
ok answer is '2'
Test #10:
score: 0
Accepted
time: 3ms
memory: 16108kb
input:
15 9 0 2 2 1 2 0 3 3 1 0 1 1 1 0 1
output:
2
result:
ok answer is '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 16144kb
input:
8 6 0 0 0 1 0 1 0 1
output:
2
result:
ok answer is '2'
Test #12:
score: 0
Accepted
time: 2ms
memory: 16128kb
input:
10 6 1 0 0 1 0 1 0 3 3 0
output:
2
result:
ok answer is '2'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5884kb
input:
1 1 0
output:
0
result:
ok answer is '0'
Test #14:
score: 0
Accepted
time: 0ms
memory: 16128kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 2ms
memory: 14012kb
input:
7 4 0 1 0 2 1 3 0
output:
2
result:
ok answer is '2'
Test #16:
score: 0
Accepted
time: 3ms
memory: 16200kb
input:
8 5 1 0 1 0 2 1 3 0
output:
2
result:
ok answer is '2'
Test #17:
score: -100
Time Limit Exceeded
input:
1000000 1000000 507624 225615 645997 324384 930930 165669 488080 968655 530722 293286 929521 65826 242278 483915 447838 683484 757911 811652 223115 648468 287602 113125 150435 645440 413280 788127 48622 967532 334599 130555 888316 315597 102200 535955 54735 505596 746579 99783 536797 245479 758694 9...