QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#21629	#2848. 城市地铁规划	LFCode^#	WA	19ms	109356kb	C++14	2.6kb	2022-03-07 17:08:27	2022-05-08 03:44:13

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-05-08 03:44:13]
评测

测评结果：WA
用时：19ms
内存：109356kb

查看

[2022-03-07 17:08:27]
提交

answer

#include<bits/stdc++.h>
#include<cstdio>
#include<cctype>
#define ll long long
#define PI pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ui unsigned int
#define pb push_back
#define llu long long unsigned
using namespace std;
const int MB=1<<20;
struct FastIO{
	char ib[MB+100],*p,*q;
	char ob[MB+100],*r,stk[128];
	int tp;
	FastIO(){p=q=ib,r=ob,tp=0;}
	~FastIO(){fwrite(ob,1,r-ob,stdout);}
	char read_char(){if(p==q){p=ib,q=ib+fread(ib,1,MB,stdin);if(p==q)return 0;}return *p++;}
	template<typename T>
	void read_int(T& x){char c=read_char(),l=0;for(x=0;!isdigit(c);c=read_char())l=c;for(;isdigit(c);c=read_char())x=x*10-'0'+c;if(l=='-')x=-x;}
	void write_char(char c){if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);*r++=c;}
	template<typename T>
	void write_int(T x){if(x<0)write_char('-'),x=-x;do stk[++tp]=x%10+'0';while(x/=10);while(tp)write_char(stk[tp--]);}
}IO;
//IO.read_int(a);c=IO.read_char();IO.write_int(a);//IO.write_char(c);
const int N=3010,M=6010,mod=59393;
int T,n,k,a[N];
int f[N][N],ff[M];
PI bef[N][N];
int qwq[M];
int rd[N];
int main(){
//	scanf("%d",&T);
	T=1;
	while(T--){
		scanf("%d%d",&n,&k);
		ll lytqwq=0;
		for(int i=0;i<=k;i++){
			scanf("%d",&a[i]);
			lytqwq+=a[i];
		}
		if(n==1){
			printf("0 0\n");
			return 0;
		}
		else if(n==2){
			printf("%d %lld\n",1,lytqwq*2);
			printf("1 2\n");
			return 0;
		}
		for(int i=1;i<=2*n;i++){
			int res=1;
			for(int o=0;o<=k;o++){
				ff[i]=(ff[i]+res*1ll*a[o])%mod;
				res=res*1ll*i%mod;
			}
		}
		ll res=ff[1]*1ll*n,rrr=ff[1];
		for(int i=1;i<=2*n-1;i++){
			ff[i]=ff[i+1]-rrr;
		}
		
		memset(f,-0x3f,sizeof(f));
		f[n-1][n-2]=0;
		for(int i=n-2;i>=1;i--){
			for(int v=n-2;v>=0;v--){
				bef[i][v]=mp(i+1,v);
				f[i][v]=f[i+1][v];
				if(v+i<=n-1){
					if(f[i][v+i]+ff[i]>f[i][v]){
						f[i][v]=f[i][v+i]+ff[i];
						bef[i][v]=mp(i,v+i);
					}
				}
			}
		}
		PI now=mp(1,0),endd=mp(n-1,n-2);
		printf("%d %lld\n",n-1,f[1][0]+res);
		while(now!=endd){
			qwq[bef[now.fi][now.se].se-now.se+1]++;
			now=bef[now.fi][now.se];
		}
		int ss=0;
		for(int i=2;i<=2*(n-1);i++){
			ss+=qwq[i];
		}
		int noww=0,fal=ss;
		for(int i=2;i<=2*(n-1);i++){
			while(qwq[i]--){
				noww++;
				int t=i-1-(noww!=1);
				while(t--){
					ss++;
					printf("%d %d\n",noww,ss);
				}
				if(noww!=fal)
				printf("%d %d\n",noww,noww+1);
				else 
				printf("%d %d\n",noww,ss+1);
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int v=1;v<=2*n;v++){
//				for(int k=1;k<=v;k++){
//					f[i][v]=max(f[i][v],f[i-1][v-k]+ff[k]);
//				}
//			}
//		}
//		printf("%d\n",f[n][2*(n-1)]);
	}
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 10ms

memory: 43008kb

input:

63 7
4 50 14 48 33 13 44 24

output:

result:

ok

Test #2:

score: 0

Accepted

time: 9ms

memory: 43844kb

input:

208 7
23 28 14 16 46 28 26 28

output:

207 3317121
1 104
1 105
1 2
2 106
2 3
3 107
3 4
4 108
4 5
5 109
5 6
6 110
6 7
7 111
7 8
8 112
8 9
9 113
9 10
10 114
10 11
11 115
11 12
12 116
12 13
13 117
13 14
14 118
14 15
15 119
15 16
16 120
16 17
17 121
17 18
18 122
18 19
19 123
19 20
20 124
20 21
21 125
21 22
22 126
22 23
23 127
23 24
24 128
24...

result:

ok

Test #3:

score: 0

Accepted

time: 19ms

memory: 109356kb

input:

2928 3
27 20 7 29

output:

2927 13889888
1 267
1 268
1 269
1 270
1 271
1 272
1 273
1 274
1 275
1 276
1 277
1 2
2 278
2 279
2 280
2 281
2 282
2 283
2 284
2 285
2 286
2 287
2 3
3 288
3 289
3 290
3 291
3 292
3 293
3 294
3 295
3 296
3 297
3 4
4 298
4 299
4 300
4 301
4 302
4 303
4 304
4 305
4 306
4 307
4 5
5 308
5 309
5 310
5 311
...

result:

ok

Test #4:

score: 0

Accepted

time: 8ms

memory: 44800kb

input:

320 3
46 42 15 15

output:

319 1260206
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 2
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 3
3 47
3 48
3 49
3 50
3 51
3 52
3 53
3 54
3 55
3 56
3 57
3 58
3 59
3 4
4 60
4 61
4 62
4 63
4 64
4 65
4 66
4 67
4 68
4 69
4 70
4 71
4 72
4 5
5 73
5 74
5 75
5 76
5 77
5 ...

result:

ok

Test #5:

score: 0

Accepted

time: 3ms

memory: 45268kb

input:

380 5
41 27 8 3 31 0

output:

379 3140470
1 77
1 78
1 79
1 2
2 80
2 81
2 82
2 83
2 3
3 84
3 85
3 86
3 87
3 4
4 88
4 89
4 90
4 91
4 5
5 92
5 93
5 94
5 95
5 6
6 96
6 97
6 98
6 99
6 7
7 100
7 101
7 102
7 103
7 8
8 104
8 105
8 106
8 107
8 9
9 108
9 109
9 110
9 111
9 10
10 112
10 113
10 114
10 115
10 11
11 116
11 117
11 118
11 119
11...

result:

ok

Test #6:

score: 0

Accepted

time: 4ms

memory: 43176kb

input:

365 5
35 20 24 29 3 25

output:

364 3508667
1 122
1 123
1 124
1 2
2 125
2 126
2 3
3 127
3 128
3 4
4 129
4 130
4 5
5 131
5 132
5 6
6 133
6 134
6 7
7 135
7 136
7 8
8 137
8 138
8 9
9 139
9 140
9 10
10 141
10 142
10 11
11 143
11 144
11 12
12 145
12 146
12 13
13 147
13 148
13 14
14 149
14 150
14 15
15 151
15 152
15 16
16 153
16 154
16 ...

result:

ok

Test #7:

score: 0

Accepted

time: 3ms

memory: 42624kb

input:

318 6
4 44 46 6 37 14 49

output:

317 6799456
1 159
1 160
1 2
2 161
2 3
3 162
3 4
4 163
4 5
5 164
5 6
6 165
6 7
7 166
7 8
8 167
8 9
9 168
9 10
10 169
10 11
11 170
11 12
12 171
12 13
13 172
13 14
14 173
14 15
15 174
15 16
16 175
16 17
17 176
17 18
18 177
18 19
19 178
19 20
20 179
20 21
21 180
21 22
22 181
22 23
23 182
23 24
24 183
24...

result:

ok

Test #8:

score: 0

Accepted

time: 3ms

memory: 43648kb

input:

416 6
30 23 4 16 45 32 19

output:

415 5383994
1 208
1 209
1 2
2 210
2 3
3 211
3 4
4 212
4 5
5 213
5 6
6 214
6 7
7 215
7 8
8 216
8 9
9 217
9 10
10 218
10 11
11 219
11 12
12 220
12 13
13 221
13 14
14 222
14 15
15 223
15 16
16 224
16 17
17 225
17 18
18 226
18 19
19 227
19 20
20 228
20 21
21 229
21 22
22 230
22 23
23 231
23 24
24 232
24...

result:

ok

Test #9:

score: 0

Accepted

time: 4ms

memory: 45416kb

input:

572 5
15 27 5 18 3 46

output:

571 9396678
1 191
1 192
1 193
1 2
2 194
2 195
2 3
3 196
3 197
3 4
4 198
4 199
4 5
5 200
5 201
5 6
6 202
6 203
6 7
7 204
7 205
7 8
8 206
8 207
8 9
9 208
9 209
9 10
10 210
10 211
10 11
11 212
11 213
11 12
12 214
12 215
12 13
13 216
13 217
13 14
14 218
14 219
14 15
15 220
15 221
15 16
16 222
16 223
16 ...

result:

ok

Test #10:

score: 0

Accepted

time: 4ms

memory: 44940kb

input:

531 8
20 13 35 27 41 43 36 25 5

output:

530 9024252
1 178
1 2
2 179
2 180
2 3
3 181
3 182
3 4
4 183
4 184
4 5
5 185
5 186
5 6
6 187
6 188
6 7
7 189
7 190
7 8
8 191
8 192
8 9
9 193
9 194
9 10
10 195
10 196
10 11
11 197
11 198
11 12
12 199
12 200
12 13
13 201
13 202
13 14
14 203
14 204
14 15
15 205
15 206
15 16
16 207
16 208
16 17
17 209
17...

result:

ok

Test #11:

score: 0

Accepted

time: 9ms

memory: 46480kb

input:

487 10
29 29 40 45 5 16 40 47 47 2 14

output:

486 18026623
1 486
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

result:

ok

Test #12:

score: 0

Accepted

time: 0ms

memory: 45572kb

input:

584 7
10 27 29 8 32 43 26 3

output:

583 11437238
1 292
1 293
1 2
2 294
2 3
3 295
3 4
4 296
4 5
5 297
5 6
6 298
6 7
7 299
7 8
8 300
8 9
9 301
9 10
10 302
10 11
11 303
11 12
12 304
12 13
13 305
13 14
14 306
14 15
15 307
15 16
16 308
16 17
17 309
17 18
18 310
18 19
19 311
19 20
20 312
20 21
21 313
21 22
22 314
22 23
23 315
23 24
24 316
2...

result:

ok

Test #13:

score: 0

Accepted

time: 8ms

memory: 42972kb

input:

59 4
48 16 9 42 21

output:

result:

ok

Test #14:

score: 0

Accepted

time: 3ms

memory: 45204kb

input:

561 3
22 31 17 49

output:

560 3223790
1 64
1 2
2 65
2 66
2 67
2 68
2 69
2 70
2 71
2 72
2 3
3 73
3 74
3 75
3 76
3 77
3 78
3 79
3 80
3 4
4 81
4 82
4 83
4 84
4 85
4 86
4 87
4 88
4 5
5 89
5 90
5 91
5 92
5 93
5 94
5 95
5 96
5 6
6 97
6 98
6 99
6 100
6 101
6 102
6 103
6 104
6 7
7 105
7 106
7 107
7 108
7 109
7 110
7 111
7 112
7 8
8 ...

result:

ok

Test #15:

score: 0

Accepted

time: 10ms

memory: 48356kb

input:

629 6
26 31 41 32 13 39 41

output:

628 13149156
1 315
1 2
2 316
2 3
3 317
3 4
4 318
4 5
5 319
5 6
6 320
6 7
7 321
7 8
8 322
8 9
9 323
9 10
10 324
10 11
11 325
11 12
12 326
12 13
13 327
13 14
14 328
14 15
15 329
15 16
16 330
16 17
17 331
17 18
18 332
18 19
19 333
19 20
20 334
20 21
21 335
21 22
22 336
22 23
23 337
23 24
24 338
24 25
2...

result:

ok

Test #16:

score: 0

Accepted

time: 7ms

memory: 46048kb

input:

616 3
38 48 27 2

output:

615 1394108
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 2
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
2 60
2 61
2 62
2 63
2 3
3 64
3 65
3 66
3 67
3 68
3 69
3 70
3 71
3 72
3 73
3 74
3 75
3 76
3 77
3 78
3 79
3 80
3 81
...

result:

ok

Test #17:

score: 0

Accepted

time: 4ms

memory: 49932kb

input:

744 2
49 45 50

output:

743 1425426
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 2
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
2 60
2 61
2 62
2 63
2 64
2 65
2 66
2 67
2 68
2 69
2 70
2 71
2 3
3 72
3 73
3 74
3 75
3 76
3 77
3 78
3 79
...

result:

ok

Test #18:

score: 0

Accepted

time: 10ms

memory: 46220kb

input:

629 7
27 18 48 24 37 38 6 3

output:

628 9258317
1 159
1 2
2 160
2 3
3 161
3 162
3 163
3 4
4 164
4 165
4 166
4 5
5 167
5 168
5 169
5 6
6 170
6 171
6 172
6 7
7 173
7 174
7 175
7 8
8 176
8 177
8 178
8 9
9 179
9 180
9 181
9 10
10 182
10 183
10 184
10 11
11 185
11 186
11 187
11 12
12 188
12 189
12 190
12 13
13 191
13 192
13 193
13 14
14 19...

result:

ok

Test #19:

score: 0

Accepted

time: 5ms

memory: 47988kb

input:

602 8
17 25 14 13 2 16 23 24 44

output:

601 9947756
1 601
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

result:

ok

Test #20:

score: 0

Accepted

time: 17ms

memory: 50552kb

input:

900 2
9 13 12

output:

result:

ok

Test #21:

score: 0

Accepted

time: 12ms

memory: 49484kb

input:

839 7
12 12 28 33 35 29 14 17

output:

838 24516016
1 420
1 2
2 421
2 3
3 422
3 4
4 423
4 5
5 424
5 6
6 425
6 7
7 426
7 8
8 427
8 9
9 428
9 10
10 429
10 11
11 430
11 12
12 431
12 13
13 432
13 14
14 433
14 15
15 434
15 16
16 435
16 17
17 436
17 18
18 437
18 19
19 438
19 20
20 439
20 21
21 440
21 22
22 441
22 23
23 442
23 24
24 443
24 25
2...

result:

ok

Test #22:

score: 0

Accepted

time: 12ms

memory: 48308kb

input:

768 7
27 3 40 6 39 9 48 31

output:

767 18960055
1 384
1 385
1 2
2 386
2 3
3 387
3 4
4 388
4 5
5 389
5 6
6 390
6 7
7 391
7 8
8 392
8 9
9 393
9 10
10 394
10 11
11 395
11 12
12 396
12 13
13 397
13 14
14 398
14 15
15 399
15 16
16 400
16 17
17 401
17 18
18 402
18 19
19 403
19 20
20 404
20 21
21 405
21 22
22 406
22 23
23 407
23 24
24 408
2...

result:

ok

Test #23:

score: 0

Accepted

time: 3ms

memory: 48548kb

input:

783 3
25 19 31 45

output:

782 4263811
1 88
1 89
1 90
1 91
1 92
1 93
1 94
1 2
2 95
2 96
2 97
2 98
2 99
2 100
2 101
2 102
2 3
3 103
3 104
3 105
3 106
3 107
3 108
3 109
3 110
3 4
4 111
4 112
4 113
4 114
4 115
4 116
4 117
4 118
4 5
5 119
5 120
5 121
5 122
5 123
5 124
5 125
5 126
5 6
6 127
6 128
6 129
6 130
6 131
6 132
6 133
6 13...

result:

ok

Test #24:

score: 0

Accepted

time: 1ms

memory: 5840kb

input:

2 4
24 9 31 45 15

output:

1 248
1 2

result:

ok

Test #25:

score: 0

Accepted

time: 17ms

memory: 48612kb

input:

792 5
28 40 21 32 44 11

output:

791 6695732
1 265
1 2
2 266
2 267
2 3
3 268
3 269
3 4
4 270
4 271
4 5
5 272
5 273
5 6
6 274
6 275
6 7
7 276
7 277
7 8
8 278
8 279
8 9
9 280
9 281
9 10
10 282
10 283
10 11
11 284
11 285
11 12
12 286
12 287
12 13
13 288
13 289
13 14
14 290
14 291
14 15
15 292
15 293
15 16
16 294
16 295
16 17
17 296
17...

result:

ok

Test #26:

score: 0

Accepted

time: 8ms

memory: 53324kb

input:

939 5
35 7 31 40 25 28

output:

938 12031060
1 313
1 314
1 315
1 2
2 316
2 317
2 3
3 318
3 319
3 4
4 320
4 321
4 5
5 322
5 323
5 6
6 324
6 325
6 7
7 326
7 327
7 8
8 328
8 329
8 9
9 330
9 331
9 10
10 332
10 333
10 11
11 334
11 335
11 12
12 336
12 337
12 13
13 338
13 339
13 14
14 340
14 341
14 15
15 342
15 343
15 16
16 344
16 345
16...

result:

ok

Test #27:

score: 0

Accepted

time: 4ms

memory: 53020kb

input:

924 6
30 26 21 8 12 42 26

output:

923 14203740
1 462
1 463
1 2
2 464
2 3
3 465
3 4
4 466
4 5
5 467
5 6
6 468
6 7
7 469
7 8
8 470
8 9
9 471
9 10
10 472
10 11
11 473
11 12
12 474
12 13
13 475
13 14
14 476
14 15
15 477
15 16
16 478
16 17
17 479
17 18
18 480
18 19
19 481
19 20
20 482
20 21
21 483
21 22
22 484
22 23
23 485
23 24
24 486
2...

result:

ok

Test #28:

score: 0

Accepted

time: 3ms

memory: 50532kb

input:

902 8
8 48 35 25 32 28 21 2 44

output:

901 13244886
1 901
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 5...

result:

ok

Test #29:

score: 0

Accepted

time: 13ms

memory: 52824kb

input:

1021 2
11 16 14

output:

1020 977447
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 2
2 29
2 30
2 31
2 32
2 33
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
2 60
2 61
2 62
2 63
2 64
2 65
2 66
2 67
2 68
2 69
2 70
2 71
2 72
2 73
2 74...

result:

ok

Test #30:

score: -100

Wrong Answer

time: 3ms

memory: 5708kb

input:

1 9
18 7 32 20 44 12 15 38 14 43

output:

0 0

result:

wrong answer