oj.uz

Submission #370334

# Submission time Handle Problem Language Result Execution time Memory
370334 2021-02-23T19:49:46 Z Traduttore Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 5740 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define F first
#define S second
#define pb push_back
#define ld long double
#define int ll
#define pll pair <ll,ll>
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define TIME 1.0*clock()/CLOCKS_PER_SEC
using namespace std;
using namespace __gnu_pbds;
mt19937_64 gen(time(0));
int n,q;
vector <int> a;
void init() {
    cin>>n>>q;
    a.resize(n);
    for (int i = 0;i < n;i++)
        cin>>a[i];
}
ll ans = 0;
void output() {
    cout<<ans<<'\n';
}
int dp[(int)(1e6) ^ 1][(int)(2)];
void solve() {
    while (q--)
    {
        int l,r,x;
        cin>>l>>r>>x;
        --l;
        --r;
        for (int j = l;j <= r;j++)
            a[j]+=x;
        ans = 0;
        for (int i = 0;i < n;i++)
            {
                dp[i][0] = dp[i][1] = 0;
            }
        for (int i = 1;i < n;i++)
        {
           if (a[i] == a[i - 1]) {
                dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
           dp[i][1] = max(dp[i - 1][0],dp[i - 1][1]);
           }
           else if (a[i] > a[i - 1]) {
            dp[i][0] = max(dp[i][0], max(dp[i - 1][1],dp[i - 1][0] + abs(a[i] - a[i - 1])));
            dp[i][1] = max(dp[i - 1][0],dp[i - 1][1]);
           }
           else {
            dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
            dp[i][1] = max(dp[i][1], max(dp[i - 1][0],dp[i - 1][1] + abs(a[i] - a[i - 1])));
           }
        }
        for (int i = 0;i < n;i++)
            ans = max({ans,dp[i][0],dp[i][1]});
        output();
    }
}
int32_t main() {
    srand(time(0));
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
IOS;
int test;
test = 1;
while (test--) {
    init();
    solve();
}
exit(0);}
/*2 3 3 4*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 75 ms 592 KB Output is correct
8 Correct 76 ms 492 KB Output is correct
9 Correct 74 ms 492 KB Output is correct
10 Correct 72 ms 492 KB Output is correct
11 Correct 71 ms 492 KB Output is correct
12 Correct 71 ms 492 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 75 ms 592 KB Output is correct
8 Correct 76 ms 492 KB Output is correct
9 Correct 74 ms 492 KB Output is correct
10 Correct 72 ms 492 KB Output is correct
11 Correct 71 ms 492 KB Output is correct
12 Correct 71 ms 492 KB Output is correct
13 Execution timed out 2079 ms 5740 KB Time limit exceeded
14 Halted 0 ms 0 KB -