이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const int maxN = 2e5 + 5;
const ll inf = 1e18;
int n, q, vis[maxN][2];
ll a[maxN], dp[maxN][2];
ll DP(const int idx,
const bool cut) {
if (idx >= n)
return 0;
if (vis[idx][cut] != q) {
vis[idx][cut] = q;
dp[idx][cut] = -inf;
if (cut) {
maxi(dp[idx][cut], DP(idx + 1, false) + abs(a[idx] - a[idx + 1]));
} else {
if (idx == 1 || (a[idx] - a[idx - 1]) * (a[idx + 1] - a[idx]) >= 0)
maxi(dp[idx][cut], DP(idx + 1, false) + abs(a[idx] - a[idx + 1]));
maxi(dp[idx][cut], DP(idx + 1, true));
}
}
return dp[idx][cut];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
fort(i, 1, n)
cin >> a[i];
memset(vis, -1, sizeof(vis));
while (q--) {
int l, r;
ll x;
cin >> l >> r >> x;
fort(i, l, r)
a[i] += x;
cout << DP(1, false) << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |