QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#670395#7067. The Great WallSoestxWA 1ms4020kbC++231.1kb2024-10-23 21:33:502024-10-23 21:33:50

Judging History

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

  • [2024-10-23 21:33:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4020kb
  • [2024-10-23 21:33:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pll pair<int,int>
#define fi first
#define se second
typedef long long LL;
typedef unsigned long long ull;
int n, m, k;
const int N = 1e4 + 10, M = 1e7 + 10, mod = 998244353;
const double eps = 1e-6, inf = 1e8;

int dp[2][N][4];
int num[N];
void solve() {
	cin>>n;
	for(int i=1;i<=n;i++) cin>>num[i];
	memset(dp,-0x3f,sizeof dp);
	dp[1][0][2]=0;
	int idx=1;
	for(int i=1;i<=n;i++)
	{
		idx^=1;
		for(int j=1;j<=i;j++)
		{
			dp[idx][j][0]=dp[idx^1][j][0];
			dp[idx][j][1]=dp[idx^1][j][1];
			dp[idx][j][2]=max({dp[idx^1][j][2],dp[idx^1][j][0]+num[i],dp[idx^1][j][1]-num[i]});
			
			dp[idx][j][0]=max(dp[idx][j][0],dp[idx^1][j-1][2]-num[i]);
			dp[idx][j][1]=max(dp[idx][j][1],dp[idx^1][j-1][2]+num[i]);
			dp[idx][j][2]=max({dp[idx][j][2],dp[idx^1][j-1][2]});
		}
	}
	for(int i=1;i<=n;i++) cout<<dp[idx][i][2]<<endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
*/

详细

Test #1:

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

input:

5
1 2 3 4 5

output:

4
3
2
1
0

result:

ok 5 lines

Test #2:

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

input:

5
1 2 1 2 1

output:

1
2
2
1
0

result:

ok 5 lines

Test #3:

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

input:

6
1 1 4 5 1 4

output:

4
7
7
7
4
0

result:

ok 6 lines

Test #4:

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

input:

6
1 9 1 9 8 1

output:

8
16
23
16
8
0

result:

ok 6 lines

Test #5:

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

input:

12
1 1 4 5 1 4 1 9 1 9 8 1

output:

8
16
23
27
30
30
30
27
23
16
8
0

result:

ok 12 lines

Test #6:

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

input:

1
79932

output:

0

result:

ok single line: '0'

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 4020kb

input:

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

output:

9
18
27
36
45
54
63
72
81
90
99
108
117
126
135
144
153
162
171
180
189
198
207
216
225
234
243
252
261
270
279
288
297
306
315
323
331
339
347
355
363
371
379
387
395
403
411
419
427
435
443
451
459
467
475
483
491
498
506
513
520
527
534
541
548
555
562
569
576
583
590
597
604
610
616
622
628
634
...

result:

wrong answer 58th lines differ - expected: '499', found: '498'