oj.uz

Submission #1069879

# Submission time Handle Problem Language Result Execution time Memory
1069879 2024-08-22T09:36:18 Z n1k Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 11092 KB 
#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

void solve(){
	int n, q; cin >> n >> q;
	vector<ll> a(n);
	for(int i=0; i<n; i++) cin >> a[i];
	auto get = [&](vector<ll> a){
		vector<ll> dp(n+1);
		for(int i=0; i<n; i++){
			ll mn=a[i], mx = a[i];
			for(int j=i; j<n; j++){
				mn = min(mn, a[j]);
				mx = max(mx, a[j]);
				dp[j+1]=max(dp[j+1], dp[i]+mx - mn);
			}
		}
		return dp[n];
	};
	auto fast = [&](vector<ll> a){
		vector<ll> d, dp(n+1);
		for(int i=0; i+1<n; i++){
			d.push_back(a[i+1] - a[i]);
		}
		for(int i=0; i<d.size(); i++){
			// not pick
			dp[i+1] = max(dp[i+1], dp[i]);
			// pick
			int sgn = (i+1 == d.size() ? 0 : signbit(d[i]) != signbit(d[i+1]));
			dp[i+1+sgn] = max(dp[i+1+sgn], dp[i] + abs(d[i]));
		}
		return dp[d.size()];
	};
	while(q--){
		ll l, r, add;
		cin>>l>>r>>add;
		l--, r--;
		for(int i=l; i<=r;i++) a[i]+=add;
		cout<<fast(a)<<endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t=1; //cin >> t;
	while(t--) solve();
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=0; i<d.size(); i++){
      |                ~^~~~~~~~~
Main.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    int sgn = (i+1 == d.size() ? 0 : signbit(d[i]) != signbit(d[i+1]));
      |               ~~~~^~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:19:7: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   19 |  auto get = [&](vector<ll> a){
      |       ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 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 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 108 ms 592 KB Output is correct
8 Correct 110 ms 668 KB Output is correct
9 Correct 100 ms 672 KB Output is correct
10 Correct 104 ms 676 KB Output is correct
11 Correct 103 ms 656 KB Output is correct
12 Correct 78 ms 688 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 108 ms 592 KB Output is correct
8 Correct 110 ms 668 KB Output is correct
9 Correct 100 ms 672 KB Output is correct
10 Correct 104 ms 676 KB Output is correct
11 Correct 103 ms 656 KB Output is correct
12 Correct 78 ms 688 KB Output is correct
13 Execution timed out 2071 ms 11092 KB Time limit exceeded
14 Halted 0 ms 0 KB -