oj.uz

Submission #392671

# Submission time Handle Problem Language Result Execution time Memory
392671 2021-04-21T13:00:09 Z Mamnoon_Siam Sjeckanje (COCI21_sjeckanje) C++17
15 / 110
 2000 ms 428 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

const int N = 3003;

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

int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d", &n, &q);
  for(int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
  }
  while(q--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    for(int i = l; i <= r; ++i)
      a[i] += x;
    for(int i = n; i >= 1; --i) {
      dp[i] = max(a[i] - a[n], a[n] - a[i]);
      for(int j = i+1; j <= n; ++j) {
        dp[i] = max(dp[i], dp[j] + a[i] - a[j-1]);
        dp[i] = max(dp[i], dp[j] + a[j-1] - a[i]);
      }
    }
    printf("%lld\n", dp[1]);
  }
  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Compilation message

Main.cpp: In function 'int main(int, const char**)':
Main.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |   scanf("%d %d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     scanf("%d %d %d", &l, &r, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Output is correct
2 Correct 10 ms 308 KB Output is correct
3 Correct 12 ms 204 KB Output is correct
4 Correct 11 ms 204 KB Output is correct
5 Correct 12 ms 308 KB Output is correct
6 Correct 10 ms 204 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Output is correct
2 Correct 10 ms 308 KB Output is correct
3 Correct 12 ms 204 KB Output is correct
4 Correct 11 ms 204 KB Output is correct
5 Correct 12 ms 308 KB Output is correct
6 Correct 10 ms 204 KB Output is correct
7 Execution timed out 2068 ms 428 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 204 KB Output is correct
2 Correct 10 ms 308 KB Output is correct
3 Correct 12 ms 204 KB Output is correct
4 Correct 11 ms 204 KB Output is correct
5 Correct 12 ms 308 KB Output is correct
6 Correct 10 ms 204 KB Output is correct
7 Execution timed out 2068 ms 428 KB Time limit exceeded
8 Halted 0 ms 0 KB -