QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#239097#6191. Hard ProblemCrysflyAC ✓27ms4264kbC++17924b2023-11-04 18:30:022023-11-04 18:30:03

Judging History

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

  • [2023-11-04 18:30:03]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:4264kb
  • [2023-11-04 18:30:02]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define maxn 100005
int T,n,a[maxn],f[8],g[8];
inline void chkmax(int&x,int y){x=max(x,y);}
void work()
{
	n=read();
	For(i,1,n)a[i]=read();
	memset(f,-63,sizeof f),f[0]=0;
	Rep(i,n,1){
		memset(g,-63,sizeof g);
		int val=a[i];
		if(i>2)val-=a[i-2];
		For(s,0,7){
			int v1=(s&1),w1=(s&2)>>1,w2=(s&4)>>2;
			For(v0,0,1) For(w0,0,1)
				chkmax(g[v0|(w0<<1)|(w1<<2)],f[s]+val*w0-max(0ll,-v0+v1+w0-w2)*a[i]);
		}
		swap(f,g);
	}
	cout<<*max_element(f,f+8)<<endl;
}
signed main()
{
	int T=read();
	while(T--)work(); 
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3372kb

input:

3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000 1000000000 0 1000000000 1000000000
13
1 1 4 5 1 4 1 9 1 9 8 1 0

output:

2
3000000000
19

result:

ok 3 number(s): "2 3000000000 19"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

5
50
3 4 10 2 9 1 2 1 3 8 8 4 0 7 5 4 4 3 9 7 4 1 3 5 2 1 5 10 1 5 9 2 2 4 9 10 10 0 1 0 6 2 1 4 4 1 0 10 9 8
50
447 695 336 2 590 444 493 390 62 255 475 342 518 539 780 636 811 813 231 990 804 778 742 627 555 625 211 843 200 638 340 172 99 866 189 125 51 406 294 409 158 126 489 402 256 433 121 546 ...

output:

77
5333
567261
71740184
7111068521

result:

ok 5 number(s): "77 5333 567261 71740184 7111068521"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

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

output:

10
7
12
8
9
7
12
8
6
10

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 3392kb

input:

10
50
25 24 28 15 45 2 40 25 23 32 38 49 7 33 34 9 10 37 49 20 19 38 19 22 43 48 26 49 26 34 15 50 18 17 8 3 5 23 5 14 4 42 24 22 11 43 4 36 39 14
50
45 1 49 43 43 46 1 18 39 23 3 30 41 10 3 3 34 1 33 3 27 41 1 36 36 0 20 18 15 26 1 27 10 34 22 13 2 25 4 24 7 50 10 43 0 3 38 11 32 33
50
14 37 39 50 ...

output:

341
417
371
342
357
321
309
340
305
324

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3372kb

input:

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

output:

314
390
366
350
390
293
408
442
333
323

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 3376kb

input:

10
200
180 105 5 152 124 95 115 168 61 91 66 92 160 125 65 44 128 39 69 43 32 134 144 10 18 81 10 161 113 169 13 60 31 164 148 93 4 96 85 114 67 177 178 173 9 124 163 74 20 6 121 20 74 166 143 133 113 139 10 31 128 46 33 192 108 57 178 131 97 160 86 60 40 106 70 0 125 37 90 152 108 106 62 173 190 25...

output:

5786
5845
4942
5243
4875
4472
5569
5505
5291
5985

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

10
200
13 169 101 137 5 66 83 119 26 196 173 91 100 108 94 141 109 105 4 144 128 168 39 41 11 8 11 121 96 158 10 7 133 120 33 129 178 168 200 166 14 96 21 53 82 115 99 67 198 56 24 10 33 135 38 56 117 146 145 135 112 198 170 191 124 145 150 167 107 72 113 137 5 62 122 29 116 29 169 128 28 116 125 58...

output:

4937
5410
5354
4816
5650
5106
5161
5586
4864
5350

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 3364kb

input:

10
200
474241179 824759444 179897408 58543033 31219226 992918564 586279732 745512362 694893964 271873492 677197939 726776376 847464287 86622849 549167172 374838617 250574641 70790981 173344739 936000682 906357546 101457135 916382647 15826598 31323108 890116978 879804005 663739122 405558169 523052230...

output:

27149795167
26148727940
26657484986
28158059012
28395912986
25674071785
27037638566
26893405040
26976445221
27115391316

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

10
1000
144351583 427808372 841332406 915042334 791881292 121459161 206543816 442016184 648630707 22844293 662475389 449451433 124399854 746991357 672974863 837034768 670357798 557319603 532613172 890926196 3785951 539326786 214237940 677853321 397141215 697387063 143226671 380329904 503382495 58109...

output:

131580223531
133091338611
133276284628
129327529241
126624435850
127006306206
132543542806
129438528140
135842416361
125438351371

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 4ms
memory: 3344kb

input:

10
10000
134528114 757277876 488671939 294865299 146085056 337058121 89424776 790702183 406201207 393774627 395342526 580057960 750924565 179044376 743848556 614982465 180343233 368251400 621103535 20052648 880689403 543904645 553789869 999554838 262332413 504818531 564886153 371494125 859477682 775...

output:

1295832812264
1285008354812
1271754417664
1278371646136
1306392422562
1296376575571
1284140246537
1308925058551
1286308426452
1280308892116

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 3448kb

input:

10
10000
739801696 647485569 994894748 877842747 391687964 718068752 981359359 898151633 855874358 973821299 240488593 216013041 808751983 551019381 270550547 219735291 779811783 458416207 465567637 250276842 283194919 985677626 780226733 294065751 742485325 946238295 478132811 939912689 223080452 2...

output:

1295460152007
1278930025733
1286291384294
1283764398140
1287033111223
1298678827861
1292107371003
1288078509120
1276101012983
1277948652599

result:

ok 10 numbers

Test #12:

score: 0
Accepted
time: 27ms
memory: 4264kb

input:

10
100000
630607255 461950434 120706961 486326610 202590109 968496359 374214488 838696181 683763082 426146834 707152820 674635530 723129820 338776480 786753996 485930718 271119036 795148496 988325677 832086919 362657498 68165453 395535090 155788206 851511578 817546215 702638021 503068098 751800844 4...

output:

12854769460577
12879187620566
12903502337369
12907876797073
12858297018275
12912851305219
12861588234578
12879271004787
12857728357913
12882389664500

result:

ok 10 numbers