QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #281752 | #3032. Cheese Game | Dualqwq# | AC ✓ | 365ms | 5672kb | C++20 | 567b | 2023-12-10 17:45:42 | 2023-12-10 17:45:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n,a[N];
long long dp[N];
inline void Main() {
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
dp[0] = 0;dp[1] = a[1];
for(int i = 2;i <= n;i++) {
dp[i] = -1e18;
if(i >= 2) dp[i] = max(dp[i],dp[i - 2] + a[i]);
if(i >= 3) dp[i] = max(dp[i],dp[i - 3] + min(a[i - 1],a[i - 2]) + a[i]);
}
long long ans = max(dp[n - 1],dp[n]);
ans = max(ans,dp[n - 2] + min(a[n - 1],a[n]));
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while(T--) Main();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5672kb
input:
20 2 2 1 1 1000000 4 3 2 4 3 8 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 8 1000000 1000000 1000000 1 1000000 1000000 1000000 1000000 9 723059 133070 898168 961394 18457 175012 478043 176230 377374 8 289384 930887 692778 636916 747794 238336 885387 760493 8 516650 641422 202363 ...
output:
2 1000000 8 5000000 5000000 2691397 3314426 2475496 4999998 10 3 1 2 8 4000001 15 3213803 24 3000002 4
result:
ok 20 lines
Test #2:
score: 0
Accepted
time: 365ms
memory: 4820kb
input:
20 100000 859485 390674 819590 695284 505824 962572 577989 53378 307332 754253 103728 302519 19948 48169 659522 389802 262161 848413 224854 965949 70782 789156 772974 876205 410327 900390 392837 362222 582187 762071 74734 958024 152744 410676 169659 174919 373247 264000 744649 196931 18252 848376 15...
output:
33024883937 33135467117 66667000000 33237375393 58332975002 33104918259 33172888838 33156623430 33090460100 33042109608 32999667097 33111199056 3333366667 32982135568 33144273501 56831006063 33108905993 33124668910 33126313979 33069028435
result:
ok 20 lines