oj.uz

Submission #1113322

# Submission time Handle Problem Language Result Execution time Memory
1113322 2024-11-16T11:20:30 Z kiethm07 Sjeckanje (COCI21_sjeckanje) C++11
55 / 110
 2000 ms 8896 KB 
#include <bits/stdc++.h>

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);
const int N = 2e5 + 5;

ll a[N];
ll d[N];
ll dp[N][2];
int n,q;

ll brute(){
    dp[0][0] = dp[0][1] = 0;
    dp[1][0] = dp[1][1] = 0;
    if (d[1] > 0) dp[1][0] = d[1];
    else dp[1][1] = -d[1];
    for (int i = 2; i < n; i++){
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        if (d[i] > 0){
            dp[i][0] = max(dp[i][0], dp[i - 1][0] + d[i]);
            dp[i][0] = max(dp[i][0], max(dp[i - 2][0], dp[i - 2][1]) + d[i]);
        }
        else{
            dp[i][1] = max(dp[i][1], dp[i - 1][1] - d[i]);
            dp[i][1] = max(dp[i][1], max(dp[i - 2][0], dp[i - 2][1]) - d[i]);
        }
    }
    return max(dp[n - 1][0], dp[n - 1][1]);
}

void solve(){
    while(q--){
        int l,r,x;
        cin >> l >> r >> x;
        d[l - 1] += x;
        d[r] -= x;
        cout << brute() << "\n";
    }
}

int main(){-
    #define TEXT "a"
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen(TEXT".inp","r")){
        freopen(TEXT".inp","r",stdin);
        freopen(TEXT".out","w",stdout);
    }
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:57:12: warning: value computed is not used [-Wunused-value]
   57 | int main(){-
      |            ^
   58 |     #define TEXT "a"
      |     ~~~~~~~~~~~~~~~~
   59 |     cin.tie(0) -> sync_with_stdio(0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 34 ms 684 KB Output is correct
8 Correct 33 ms 676 KB Output is correct
9 Correct 31 ms 688 KB Output is correct
10 Correct 29 ms 568 KB Output is correct
11 Correct 30 ms 760 KB Output is correct
12 Correct 32 ms 592 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 34 ms 684 KB Output is correct
8 Correct 33 ms 676 KB Output is correct
9 Correct 31 ms 688 KB Output is correct
10 Correct 29 ms 568 KB Output is correct
11 Correct 30 ms 760 KB Output is correct
12 Correct 32 ms 592 KB Output is correct
13 Execution timed out 2057 ms 8896 KB Time limit exceeded
14 Halted 0 ms 0 KB -