QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670395 | #7067. The Great Wall | Soestx | WA | 1ms | 4020kb | C++23 | 1.1kb | 2024-10-23 21:33:50 | 2024-10-23 21:33:50 |
Judging History
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'