oj.uz

Submission #920522

# Submission time Handle Problem Language Result Execution time Memory
920522 2024-02-02T17:13:27 Z myst6 Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 6024 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

// take multiple subsegments of the array, skipping element straight after
// 9 -2 3 -9 -5 -6 -7 -10 0 1 5 7 -10
// (9) - (-9 -5 -6 -7 -10) + (1 5 7)
// dp[0] => max when not taking last
// dp[1] => max score when taking last, and adding
// dp[2] => max score when taking last, and subbing
// can go from 0 => 0/1/2
//        from 1 => 1/0
//        from 2 => 2/0
// ndp[0] = max(dp[0], dp[1], dp[2])
// ndp[1] = max(dp[0], dp[1]) + diff[i]
// ndp[2] = max(dp[0], dp[2]) - diff[i]

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> A(n);
  for (int i=0; i<n; i++) cin >> A[i];
  vector<int> diff(n);
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    for (int i=l-1; i<=r-1; i++) {
      A[i] += x;
    }
    for (int i=1; i<n; i++) {
      diff[i] = A[i] - A[i-1];
    }
    array<int, 3> dp;
    dp[0] = dp[1] = dp[2] = 0;
    for (int i=1; i<n; i++) {
      array<int, 3> ndp;
      ndp[0] = max({dp[0], dp[1], dp[2]});
      ndp[1] = max(dp[0], dp[1]) + diff[i];
      ndp[2] = max(dp[0], dp[2]) - diff[i];
      swap(dp, ndp);
    }
    cout << max({dp[0], dp[1], dp[2]}) << "\n";
  }
  return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 63 ms 848 KB Output is correct
8 Correct 65 ms 604 KB Output is correct
9 Correct 66 ms 604 KB Output is correct
10 Correct 69 ms 596 KB Output is correct
11 Correct 63 ms 592 KB Output is correct
12 Correct 64 ms 604 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 63 ms 848 KB Output is correct
8 Correct 65 ms 604 KB Output is correct
9 Correct 66 ms 604 KB Output is correct
10 Correct 69 ms 596 KB Output is correct
11 Correct 63 ms 592 KB Output is correct
12 Correct 64 ms 604 KB Output is correct
13 Execution timed out 2029 ms 6024 KB Time limit exceeded
14 Halted 0 ms 0 KB -