oj.uz

답안 #849919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
849919 2023-09-15T14:42:53 Z gun_gan Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

int N, Q;
ll A[MX], dp[MX][2];

ll calc() {
      for(int i = 0; i <= N; i++) dp[i][0] = dp[i][1] = 0;

      vector<array<ll,3>> v;

      for(int i = 1; i + 1 <= N; i++) {
            if(A[i + 1] >= A[i]) {
                  int j = i;
                  ll sum = 0;
                  while(j + 1 <= N && A[j + 1] >= A[j]) {
                        sum += A[j + 1] - A[j];
                        j++;
                  }
                  v.push_back({A[i + 1] - A[i], A[j] - A[j - 1], sum});
                  i = j - 1;
            } else {
                  int j = i;
                  ll sum = 0;
                  while(j + 1 <= N && A[j + 1] < A[j]) {
                        sum += A[j] - A[j + 1];
                        j++;
                  }
                  v.push_back({A[i] - A[i + 1], A[j - 1] - A[j], sum});
                  i = j - 1;
            }
      }

      dp[0][0] = v[0][2];
      dp[0][1] = v[0][2] - v[0][1];
      for(int i = 1; i < v.size(); i++) {
            dp[i][0] = max(dp[i - 1][0] + v[i][2] - v[i][0], dp[i - 1][1] + v[i][2]);
            dp[i][1] = max(dp[i - 1][0] + v[i][2] - v[i][0] - v[i][1], dp[i - 1][1] + v[i][2] - v[i][1]);
      }

      return dp[v.size() - 1][0];
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> Q;

      for(int i = 1; i <= N; i++) cin >> A[i];

      for(int i = 1; i <= Q; i++) {
            ll l, r, x;
            cin >> l >> r >> x;

            for(int j = l; j <= r; j++) A[j] += x;

            cout << calc() << '\n';
      }
}

Compilation message

Main.cpp: In function 'll calc()':
Main.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |       for(int i = 1; i < v.size(); i++) {
      |                      ~~^~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -