QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#223396	#7339. A Really Odd Sequence	ehab_rafat	AC ✓	221ms	27132kb	C++14	894b	2023-10-22 01:48:09	2023-10-22 01:48:09

Judging History

This is the latest submission verdict.

[2023-10-22 01:48:09]
Judged

Verdict: AC
Time: 221ms
Memory: 27132kb

Show

[2023-10-22 01:48:09]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define LSB(i) ((i) & (-i))
#define ll long long
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,1,-1,-1,1,-1,1};
const int MOD = 1e9+7;
const int inf = 1e9+1; 


#define int ll

const int N = 1e6+1;
int dp[N][2], A[N];
int n;

void solve(int testCase)  {
     cin >> n;
    for(int i = 1; i <= n; ++i) cin >> A[i];
    dp[0][0] = dp[0][1] = 0;
    for(int i = 1; i <= n; ++i){
        dp[i][0] = max(dp[i-1][1]+A[i], A[i]);
        if(i > 1) dp[i][1] = dp[i-1][0] + A[i];
    }
    int ans = -1e18;
    for(int i = 1; i <= n; ++i) ans = max(ans, dp[i][0]);
    cout << ans << '\n';
}   

int32_t main(){
    fastio();  
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; ++i){
        solve(i);
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5788kb

input:

1
4
8 -7 9 1

output:

result:

ok 1 number(s): "10"

Test #2:

score: 0

Accepted

time: 221ms

memory: 27132kb

input:

59056
10
0 1 1 0 1 0 1 1 1 0
10
-1 -1 -1 1 0 0 1 0 0 1
10
1 0 0 1 1 1 -1 -1 0 1
10
-1 1 -1 1 0 1 1 0 -1 1
10
1 0 0 1 -1 0 -1 -1 -1 1
10
1 1 1 0 0 -1 -1 1 0 0
10
-1 1 0 0 1 -1 -1 0 -1 -1
10
1 -1 0 0 0 -1 -1 -1 -1 -1
10
0 0 0 1 1 0 0 1 -1 1
10
0 -1 0 0 1 0 1 1 1 0
10
0 0 0 0 1 -1 1 -1 -1 -1
10
-1 0 1 ...

output:

result:

ok 59056 numbers