oj.uz

답안 #379310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379310 2021-03-18T00:49:02 Z limabeans Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 4288 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



int n,q;
ll a[maxn];

ll solve() {
    ll dp0 = 0;
    ll dp1 = 0;
    
    ll diff0 = 0;
    for (int i=2; i<=n; i++) {
	ll diff = a[i]-a[i-1];
	if (diff0*diff>=0) {
	    ll _dp0 = max(dp0,dp1);
	    ll _dp1 = max(dp1,dp0)+abs(diff);
	    dp0 = _dp0;
	    dp1 = _dp1;
	} else {
	    ll _dp0 = max(dp0,dp1);
	    ll _dp1 = dp0+abs(diff);
	    dp0 = _dp0;
	    dp1 = _dp1;
	}
	diff0 = diff;
    }
    return max(dp0, dp1);
}

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

    cin>>n>>q;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    while (q--) {
	int l,r,dx;
	cin>>l>>r>>dx;
	for (int i=l; i<=r; i++) {
	    a[i] += dx;
	}
	cout<<solve()<<"\n";
    }
    
    
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 31 ms 512 KB Output is correct
8 Correct 31 ms 492 KB Output is correct
9 Correct 30 ms 640 KB Output is correct
10 Correct 31 ms 492 KB Output is correct
11 Correct 34 ms 508 KB Output is correct
12 Correct 20 ms 492 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 31 ms 512 KB Output is correct
8 Correct 31 ms 492 KB Output is correct
9 Correct 30 ms 640 KB Output is correct
10 Correct 31 ms 492 KB Output is correct
11 Correct 34 ms 508 KB Output is correct
12 Correct 20 ms 492 KB Output is correct
13 Execution timed out 2078 ms 4288 KB Time limit exceeded
14 Halted 0 ms 0 KB -