QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716875#1700. Redistrictingcjx100 ✓8ms6556kbC++20907b2024-11-06 16:13:552024-11-06 16:13:56

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 16:13:56]
  • 评测
  • 测评结果:100
  • 用时:8ms
  • 内存:6556kb
  • [2024-11-06 16:13:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
	long long x=0,f=1;char ch=getchar();
	while(!isdigit(ch))
	{if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(long long x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=3e5+10;
int n,k;
string s;
int a[N];
int f[N],q[N],tl,tr;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();k=read();
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+(s[i]=='H'?-1:1);
    }
    q[tl=tr=1]=0;
    for(int i=1;i<=n;i++){
        while(tl<=tr&&i-q[tl]>k)tl++;
        f[i]=f[q[tl]]+(a[i]-a[q[tl]]>=0);
        while(tl<=tr&&(f[q[tr]]>f[i]||(f[q[tr]]==f[i]&&a[q[tr]]<a[i])))tr--;
        q[++tr]=i;
    }
    write(f[n]);puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5.55556
Accepted
time: 0ms
memory: 3604kb

input:

7 2
HGHGGHG

output:

3

result:

ok single line: '3'

Test #2:

score: 5.55556
Accepted
time: 8ms
memory: 6216kb

input:

300000 4000
HHGGHHHHHGHHGHGGHGGGGHGGGHHGHGHHGGGGHGHHGGGHGGHGGGGHHHHHHHHHGGHHGHGHHHHGGHGGHHGGGGHGGHHHGHHHGHHGGGGHHGHHGHGGHGGGGGHGHGHGHHGGGGGGHHHGHGHHHGGHHHGGHHHHHGHGGHGGHHGHGGHGGHHHHGHGHHGHHGGHHGHHHGHHGGHGHGHGGHGHHHHHHGHGHGHGHGGHGGHHHGGHHHGHHGHHGGHHHHHHHHGHHGHGHHGGGGHHGGGGHHHHGGHHGHHGGGGGGHGGGHGGGHHH...

output:

30

result:

ok single line: '30'

Test #3:

score: 5.55556
Accepted
time: 8ms
memory: 6060kb

input:

300000 5000
HGHGGGGHHHHHHHGGHHHHGHGGGGGGHHHHGGGHHGHGHGHGGGHGGHHGHGGGGHHHHGHHGHGGGGGHGGGGHHGHHGHGGGHHHHHGHHGGHHGHGHHGHHGGGGHGGGHHGHHGGHGGGHHHHGHGGHGGHGGHHGHGHHGGGGHHHGHHGHGGGHHGGGGHGGGHGGGHGHGHHGGHHGHHHHHGHHGGHGGGHGGHHHGHGGGGHHHHHGGHGGGHHGHGGGGGGGHHGGGHGHHGGHHGHHGGGGGGHHHGGGHGGHHGGGGHGHGHGGHGGGHGHGGG...

output:

46

result:

ok single line: '46'

Test #4:

score: 5.55556
Accepted
time: 8ms
memory: 6088kb

input:

300000 5000
GHGHHGGGGHHGGGHHHGHHHGHGHHHHGGGHHGGGHHGHGHHGHGGHGHHHHGHHGHHGGGGGGHHGGGGHHHGHGGHGHGGGGHGGHGHHHHHHGGHHHGHGGHGGHGGGHGHGHHGHGGHGHGHHHGHGGGHHGHGGGGHHHGHHGHGGHGGHHGHHHGGHHHHHHGGGGGGGHGGGHGHHGGHHHGGHHHGHHHGGHGHGHGGHGHHGHHGHHGGGGHGHGHHHGGHGHGGGHHHGGHHHGHGGGGHHHGHGGHHHGHGHGGHGGHGGHHGGHHHGHHGGHHGG...

output:

8

result:

ok single line: '8'

Test #5:

score: 5.55556
Accepted
time: 8ms
memory: 6056kb

input:

300000 5000
GHGGHHGGHGHGGHGGHHHGHGHHHHHGHGGGGGGHHGGHGHGGHGGHGGGGHHGGHGGGHHHGHHHHHGHGGHHHGHGHHGHHGGHGGGHHGHHHGHGHHHGGHHHGGHHHGGHHGHHGGHHGGGHHGGGGGGHGGHHGHGHHGHHGHHHHHHHGGHGGHGHGGHHGGGGHGGHHGHGHHGHGHGGGGGHGHGHHHGHHHGGHGGGHGHGHHHGHGHGHGHHGHGGGHHGHGHHGGGHHHGHHGGGGGGHHGHHGGGHGGHHGHHGHHHHHGHGHGGGGGHGHGGHH...

output:

22

result:

ok single line: '22'

Test #6:

score: 5.55556
Accepted
time: 7ms
memory: 5944kb

input:

300000 10000
HGGHHHGHHHHHGHGGHHGGGGHGHGGHGGGHHHHHGHGHHGHHHGHGHHGHHHGHHHGGHHHHGHHGGGGHGGGGHHGHGGHGGHGGHHHHGGGHGHGGGGGGHGHGGGHGHGGGHGHGHGHGHGGHGGHGHHHHHHGHGGHHHHGGGGGHGGHHGHGHHHGHGHGGHHHGHGGGGGHGHGGGGHHGHHGHHGHHHHGHHHGHGHGGHGHGGHHHGGHHHGGHHHHHHHGHGGHHHGGHGHGGHHHGGHHHGHHHHHGHHHGHHGGGGGGGHHHGGHHHGHGGHGG...

output:

12

result:

ok single line: '12'

Test #7:

score: 5.55556
Accepted
time: 7ms
memory: 6556kb

input:

300000 20000
HGHHHHHHHHHGHHHHHHHGHHHHGGHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHHHHHGHHHHHHGGGHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHHHHGGHHGHHHHHHHHHHHHHHHGHHGGHGHHHGHHHHHHGHHHHHGGHHHHGHHHHHHHHHHHGHHHHHHHHHHGGHHHHHHHHHHHHHGGHHHHHHGHHGHHHHHGHHGHHHHHHHHGHHHHHGHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGGHHHHGHHHHG...

output:

5

result:

ok single line: '5'

Test #8:

score: 5.55556
Accepted
time: 7ms
memory: 6396kb

input:

300000 20000
HHHHHGGGHHHHHHHHHHHGGHHHHGHGGHHHHHHHHHHHHHGHHHHHHHHHHHGHHHHHGHHHHGHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHGGHHHHHHHHGHHHHGHHGHHHHHHHGHGGHHHGHHGHHHHHHGGGHHHHHGHHGHHGHHHHGHHHGHHHHHHGGGHHHHHHHHHGHHHHHHHHHHHGHHHHHGHHHGHHHHHHHHHHHGHHHHGGHHGGGHHHGHHGHGGHHHHGHHHHHHHHGHGHHHHHGHHHGHHHHHHGHHHGHHHHGHHGH...

output:

7

result:

ok single line: '7'

Test #9:

score: 5.55556
Accepted
time: 3ms
memory: 6248kb

input:

300000 20000
GHHHHHHHHHHHHGHHHGHHHHHHGHHHHHHGHGHHHGHHHHHHHHHGHHHHGHHGHHHHHHHHHGHHGHHHGHHHHHHHHHGHGHHHHHHHGHHHHHHHHHHHHHHGHGHHGHHHHHHHHHHGGGHGHHHHGHHHHHHHHHHGHHGGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHGHHGHHHHHGGHHGHGHHHGHHHGHHHHHGHHHHGHHHHHHGHHHHHHGGHHHHHHHHHHHHGHHHHHGHGHHHGHHGHHGHHGHHHHHHHHHHGHGHHGHHHHHHH...

output:

6

result:

ok single line: '6'

Test #10:

score: 5.55556
Accepted
time: 4ms
memory: 6040kb

input:

300000 50000
HHGGGGHHGGHHGGHGGHGGGGHGGGGGHHGHGGGHGGHHHGGGHGHGGGHGHGHGGHHGHGHHGGHHGHHGGGGGGHHGGGGGGGGGHHHGHGGGHHGHGGGHHHHHHGGHHHHHHGGHGGGGHGGGHGHHHHHGGHHGGGGHGGHHGGHGHGGHGHHHHGGHHHHGGGHHHHHGGHHHHHGGHGHHHHHGGHHGHGGGGHHGGHGHHHHGHHHHGGHHGHGHHHGGHHGGGGHGHGGHGGGGGHGHGHHGHGGHGGGHGGHGHHHGHGHGHGGGHGGHHHGGGGH...

output:

4

result:

ok single line: '4'

Test #11:

score: 5.55556
Accepted
time: 0ms
memory: 3600kb

input:

1000 20
HHHHHGGGGHHHGHGGHHGGGHGHGHGHGHGGHGGGGHHGGHGGHGGGGHGHHHGGGHGGHHGGGGGGGHGGHGHGGHHHHGHGGGHGGHHHHGHHHGHGHGHHGGGHGGHHHHGHGGHGGHHGHHGHGGHGGGGGGGGGGHGGHHGGHHHHGHHGHGHGHHHGGHGHHHGGGGGGHGGGHGHGGHGHGHHGGHGGHGGGGHHGGHHGHGGHGGHGGGGHGGHGGGGGGGHGHHGHGGHHHHHGHHHGGGHGHGGGHGHHGGHHGGGGHHGHGGGHGGHGGGGHHHGGGGGG...

output:

28

result:

ok single line: '28'

Test #12:

score: 5.55556
Accepted
time: 0ms
memory: 3616kb

input:

1000 100
GHHHGGGGHHHHGHHHHHHGGHGHGGGHHGGHGGGHHGHHGGHHGHGGGGGGGGGGGHHGHGGHGHHGGHGHGHHGHGGHGHGGHHGGHGHGGGGGGHGHHHHGGHGGHGGGHHHHGGHGGHHHGGHGGHGHGHGHHHHGGGHGGHHHHHGHHGGGGHHGGGGGGHHGGGHGGHGHHGHHGGGGHGGHHGGHHHGGGGGHHGGGGHGGHGGGGHHGGGGHHGGHGHGHGGGGHGHGHHHGGHHHHGGHHGHHHGHGHHGHGGHGGHGHHGHGGGGHHGHGGGHGHGHHHHG...

output:

6

result:

ok single line: '6'

Test #13:

score: 5.55556
Accepted
time: 0ms
memory: 3596kb

input:

1000 200
GGHGGHGGGHGGHHGGHGHHHHGGHGGHHGGGGHHGHGGGHGHHGHGHHGGHHHHHGGHGGGHGGGGGGGGGHGGHGHHGHGHGHGGGGGGGGGGHHHGGHGHHGGGHGGHGGGHGGHGGGHHHGGGGHGHGHGHGGHHHGHGHGGGHGGGHHHGGGHGGGGGGGHHHHHHHHGGHHGGGGGHHHGGGGHHHGGGHGGGGGGHHGHHGGHHGHHGGGHGHGGHGGGHHHHGGHHHGHHGGGHHHHGGGGGHGHHGHHHHHHGGHGGGHGHHHHHHHGGGHHHGGHHHHHGH...

output:

3

result:

ok single line: '3'

Test #14:

score: 5.55556
Accepted
time: 0ms
memory: 3596kb

input:

1000 300
GGGHHGHGGGGHHGGGHGHGHHGHHHHGHGHGGHGGHGGHHGHGHGHGGHHHHHHHHGGGGHGGHGGGGGGHGGGGHHGHHHHGHGHGGHGHGGGHGHHHGGHHHGHHGGHGGHGHHHGGHGGGGHHHHGHGHHGHGHHHGGGHHGGHGHHGGHGHHHHHGHGGHHHHHHHHGGHHHHHHHGHGHGHHGGHGGHGGGHGHHHGHGHHGHHHGGHHGGHGHGGHHGHHHHGHGGHGGGGHGHHHHHGHGGHHHHGHGGHHHGHHHHGGGHGGHHHGHGGGHHGGGGHHHGHH...

output:

1

result:

ok single line: '1'

Test #15:

score: 5.55556
Accepted
time: 8ms
memory: 6168kb

input:

300000 50
GGHHHGHGHHGHGGGHGGGHHHGHHHHHGHGGHHGGHGHHHGHHGGHHHGGGHGGGGHHGGGHGGGHGGHHHGGGHHHHGHGGHHHGGHHHHGGGHHHHHGHHHHHGGHHHHGGHHGHGHHGGGHGGGHHGGGGHGGGGHHGHGGGHGGGHHGHGHGGGGGGGHGGHGGGGHGHHHGHGHGHGHHGGGGGGHGHGGHGGGGHGHHGGGGHHHGHHHGGHHGGHGGGGGGHHGHGGHHHGHGHHHHGHGGHHHGGGHGHGHGGHGGHHHHGHHHHGGGGHHHHHHHGHGHG...

output:

1542

result:

ok single line: '1542'

Test #16:

score: 5.55556
Accepted
time: 2ms
memory: 6160kb

input:

300000 150
GHGHHGHHGHHGGHHGHHHGHHHGGGHGGHGGHGGGHHHHHHGHHGHGHHGHHGHGHHHGGGHHGHHGHHHHGGGGGHGGGHGHGHHGHHGGGGGHHHHGGHGHHHHHGGGHGGHGHHHHHGGHHGGGHHHGHGGGHHGHGHHGHGHHGHHHHGGHHGHHGHHHGGHGGGHHHHHHHGHGGGHHGGHHHGGHGHGGGGHGGHHGGHHGGGGGHHHGGHGHHHGGHHGGGGHHHHHHGHHHHGGHGHHGHGGGHHGGGHHHHHHGGHHHHHHGHGHHHHHGHGHHGHHGG...

output:

482

result:

ok single line: '482'

Test #17:

score: 5.55556
Accepted
time: 8ms
memory: 6104kb

input:

300000 2000
HHGHHHGGGHGHGGHGGHGHHGHHHGHGGHHHHGHGGGGGGGHGGHHGHGHHHGHGHHHHGHHGGGHHHHGHGGHGHHHHGGHHHGGGGGHHGHHGHGGHGHHHHHHHHGHHHHGHGGGHHGGHHGGHHGGGHGHHGHHHGHGGGGHGHGHHHHHGHHHHHHGHHGHHGHGGHHGHGHGHGHGHGHGGGGHGGHGGGGGGHGGHGHHHGGGHHGHGGGGGGGHHHHHHHGHHGHHGHGGGGGGGHGGGHHGHGHGGHGGHHGGGGHGGGGGGHGHHHHGGHHGGHGGG...

output:

32

result:

ok single line: '32'

Test #18:

score: 5.55556
Accepted
time: 8ms
memory: 5956kb

input:

300000 2000
HGHHGHHGHHHHGHGHGHHGHHGHHHGGHHGGGGGGHGGHGHHGHGGGGGHHHHGGGGHGGGGGHHHGGHGHHGHHGGGGHGGHGGGHHGHHGGHHGHHGGHGHHHHHHGGHHHHGHHGGGHGHGGHHHGGGGGGHGGHGHGGHGHGGHHGGHHGGHHHHGHGHGGHHHGGGHGGHGGGHGGGGGGGGGGGHGHHHGHHGGGHHHGHGHGHHGGHHHHHGGGGHGHHHHGHGGGHGGHGHHGGHGHHHGHGGHHGHHHHHHHHHHHGHHHHHHHGHGHHGHGGGHHGG...

output:

47

result:

ok single line: '47'