QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#74808#5035. foo~Sljeuo0 76ms98276kbC++141.2kb2023-02-04 09:10:182023-02-04 09:10:21

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-04 09:10:21]
  • 评测
  • 测评结果:0
  • 用时:76ms
  • 内存:98276kb
  • [2023-02-04 09:10:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=2100000000,N=6e5+5,K=30+5;
int n,k;
int f[K][N],lasf[N],lasb[N],st[N];
int calc(int p[],int i,int &tp)
{
	while(tp&&p[i]>p[st[tp]])
		--tp;
	st[++tp]=i;
	return st[tp-1];
}
int a[N];
void tic(int las[],int i,int op=1)
{
	for(int j=1; j<=n; ++j)
		a[j]=f[i-1][j-1]+1;
	for(int j=1; j<=n; ++j)
		a[j]=max(a[j],a[j-1]);
	if(op)
	{
		for(int j=1; j<=n; ++j)
			if(las[j])
				a[j]=max(a[j],a[las[j]]+1);	
	}
	else
	{
		for(int j=1; j<=n; ++j)
			if(las[j])
				a[las[j]]=max(a[las[j]],a[j]+1);			
	}
	for(int j=1; j<=n; ++j)
		f[i][j]=max(f[i][j],a[j]);
}
int work(int p[])
{
//	for(int i=1; i<=n; ++i)
//		cout<<p[i]<<' ';
//	cout<<endl;
	memset(f,0,sizeof(f));
	for(int i=1,tp=0; i<=n; ++i)
		lasf[i]=calc(p,i,tp);
	for(int i=n,tp=0; i>=1; --i)
		lasb[i]=calc(p,i,tp);
	for(int i=1; i<=k; ++i)
		tic(lasf,i),tic(lasb,i,0);
	return f[k][n];
}
int p[N<<1];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>k;
	int pn=0;
	for(int i=1; i<=n; ++i)
	{
		scanf("%d",&p[i]),p[n+i]=p[i];
		if(p[i]==n)
			pn=i;
	}
	printf("%d\n",max(work(p+pn-1),work(p+pn)));		
    return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 17ms
memory: 92192kb

input:

23 6
16 20 22 4 21 10 3 7 5 8 15 12 9 1 6 17 23 13 11 19 18 14 2

output:

20

result:

ok "20"

Test #2:

score: 0
Accepted
time: 10ms
memory: 92300kb

input:

13 6
13 9 3 4 12 6 5 1 8 10 11 7 2

output:

13

result:

ok "13"

Test #3:

score: 0
Accepted
time: 24ms
memory: 93668kb

input:

25 3
25 2 3 19 5 6 7 11 8 10 9 20 4 14 21 1 17 12 13 18 15 22 23 16 24

output:

16

result:

ok "16"

Test #4:

score: 0
Accepted
time: 13ms
memory: 93348kb

input:

25 9
1 11 10 23 9 24 7 8 19 3 5 21 18 12 15 16 17 13 2 20 14 22 4 6 25

output:

23

result:

ok "23"

Test #5:

score: 0
Accepted
time: 8ms
memory: 92632kb

input:

13 2
1 4 2 3 5 6 7 8 9 10 12 11 13

output:

12

result:

ok "12"

Test #6:

score: 0
Accepted
time: 23ms
memory: 93560kb

input:

17 5
4 2 3 6 5 1 7 8 13 16 11 12 9 14 15 10 17

output:

15

result:

ok "15"

Test #7:

score: 0
Accepted
time: 19ms
memory: 92384kb

input:

8 2
1 2 5 6 3 4 7 8

output:

8

result:

ok "8"

Test #8:

score: 0
Accepted
time: 15ms
memory: 92936kb

input:

11 5
3 11 2 10 6 5 1 4 8 7 9

output:

11

result:

ok "11"

Test #9:

score: 0
Accepted
time: 12ms
memory: 93528kb

input:

10 1
5 3 4 1 10 8 9 6 7 2

output:

6

result:

ok "6"

Test #10:

score: -10
Wrong Answer
time: 16ms
memory: 93748kb

input:

16 2
15 12 14 9 11 13 1 3 10 8 5 2 16 4 6 7

output:

10

result:

wrong answer 1st words differ - expected: '9', found: '10'

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 10
Accepted
time: 26ms
memory: 94476kb

input:

93943 1
87243 48984 50611 19218 77699 25025 85769 28141 13380 34875 42459 66419 53472 4367 48292 16894 92171 87263 42527 67085 30687 29235 27515 81053 31421 34864 83591 70491 75344 7026 50250 63402 26773 5330 36308 76399 80032 15501 16205 71750 73964 67876 68901 70548 2043 79979 89479 19784 38838 44...

output:

25

result:

ok "25"

Test #22:

score: 0
Accepted
time: 30ms
memory: 95780kb

input:

112118 1
24338 1586 3 108269 5 53472 80391 70331 9 15335 62487 28331 13 14 16564 94323 36681 108815 32632 44382 21 22 23 24 11758 40070 21518 51991 109983 30 45524 59784 33 2068 62111 36 37 38 39 89031 30508 42 43 16414 110006 34303 47 10331 44651 50 93957 95407 22019 88681 56605 12426 28498 58 59 8...

output:

281

result:

ok "281"

Test #23:

score: 0
Accepted
time: 60ms
memory: 98276kb

input:

391400 1
158965 280194 3 4 5 369036 92293 245923 57403 10 6887 280754 277300 110148 314164 135940 17 46573 126951 111447 301107 22 23 24 25 26 247952 28 342994 339309 23647 350245 33 299608 35 36 37 263236 232063 40 41 42 43 44 39280 46 299122 11961 380375 384513 51 318009 162567 54 55 56 27356 58 6...

output:

693

result:

ok "693"

Test #24:

score: 0
Accepted
time: 76ms
memory: 97600kb

input:

440571 1
243784 2 3 130039 61385 6 7 8 244611 260729 29014 12 326371 416098 15 293728 182717 66822 387603 156910 225815 413135 171756 315815 26444 302419 384825 37746 17634 391896 354575 426625 290920 34 49456 36 161212 212843 39 40 41 436888 43 102088 405279 46 47 77451 49 50 368530 52402 34143 54 ...

output:

665

result:

ok "665"

Test #25:

score: 0
Accepted
time: 58ms
memory: 95572kb

input:

237580 1
1 2 3 4 5 45736 171997 8 235046 10 11 186778 13 14 15 16 17 18 19 20 21 22 23 91724 25 147783 27 125261 29 30 27556 32 108919 76675 35 36 18966 212471 100584 11715 204252 77843 43 176763 18552 46 82644 48 49 50 51 191552 53 232631 160703 114013 69672 75193 59 60 207114 62 63 167312 83372 66...

output:

890

result:

ok "890"

Test #26:

score: 0
Accepted
time: 29ms
memory: 94788kb

input:

108629 1
1 2 3 35575 5 7205 104276 8 9 10 104552 12 13 99818 15 16 17 18 19 16579 21 74459 23 24 25 98758 27 30553 28622 105401 31 32 33 98277 29214 36 37 38 34671 99851 41 42 20159 65626 49334 58829 47 48 15553 50 16448 157 96610 71139 51449 24593 66195 11741 5738 45685 61 76006 91433 64 13205 66 6...

output:

549

result:

ok "549"

Test #27:

score: 0
Accepted
time: 16ms
memory: 94596kb

input:

7474 1
6087 2 3 3276 2246 1022 4790 8 9 10 11 3555 13 14 5187 16 17 18 5222 2852 21 3905 23 2069 25 26 27 6248 29 30 31 32 33 3467 35 5413 37 38 39 40 41 42 43 44 45 46 47 6366 6217 6683 4855 86 6754 7423 55 56 3421 58 7129 6415 2719 964 63 7191 6681 5871 2830 68 1114 70 71 4387 73 74 75 76 77 394 7...

output:

117

result:

ok "117"

Test #28:

score: -10
Wrong Answer
time: 54ms
memory: 98256kb

input:

327474 1
210193 138271 6815 114087 210548 236834 247829 287541 142327 57519 226037 185228 4602 111639 172642 13926 122775 323427 276201 198051 175153 262523 182602 84772 315273 161585 146845 231049 98201 170526 58890 213780 86346 161912 320369 55154 202159 224318 92082 314469 92925 225630 89586 2190...

output:

29

result:

wrong answer 1st words differ - expected: '31', found: '29'

Subtask #3:

score: 0
Wrong Answer

Test #36:

score: 0
Wrong Answer
time: 20ms
memory: 92896kb

input:

1992 25
144 612 1315 1966 1779 1773 1529 625 36 1849 1783 1441 1388 1558 1258 724 137 397 542 353 1162 1213 406 792 1317 882 994 298 1864 1969 103 449 508 1501 89 1721 195 778 657 222 1152 1780 613 743 1206 694 829 142 69 1973 1465 1343 655 1540 155 146 350 491 759 1695 1082 1357 1329 1745 232 1850 ...

output:

245

result:

wrong answer 1st words differ - expected: '237', found: '245'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #2:

0%