oj.uz

Submission #978793

# Submission time Handle Problem Language Result Execution time Memory
978793 2024-05-09T17:16:46 Z mannshah1211 Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 5952 KB 
/**
 *    author: hashman
 *    created:
**/

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using Int = long long;

const Int inf = 1e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, tt;
  cin >> n >> tt;
  vector<Int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  while (tt--) {
    int l, r, x;
    cin >> l >> r >> x;
    for (int j = l; j <= r; j++) {
      a[j] += x;
    }
    vector<Int> dp(n + 1);
    Int mxsub = -inf, mxadd = -inf;
    for (int j = 1; j <= n; j++) {
      mxsub = max(mxsub, dp[j - 1] - a[j]);
      mxadd = max(mxadd, dp[j - 1] + a[j]);
      dp[j] = max(dp[j], mxsub + a[j]);
      dp[j] = max(dp[j], mxadd - a[j]);
    }
    cout << dp[n] << '\n';
  }
}

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 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 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 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 35 ms 616 KB Output is correct
8 Correct 36 ms 560 KB Output is correct
9 Correct 35 ms 604 KB Output is correct
10 Correct 35 ms 604 KB Output is correct
11 Correct 35 ms 604 KB Output is correct
12 Correct 36 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 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 35 ms 616 KB Output is correct
8 Correct 36 ms 560 KB Output is correct
9 Correct 35 ms 604 KB Output is correct
10 Correct 35 ms 604 KB Output is correct
11 Correct 35 ms 604 KB Output is correct
12 Correct 36 ms 604 KB Output is correct
13 Execution timed out 2084 ms 5952 KB Time limit exceeded
14 Halted 0 ms 0 KB -