oj.uz

Submission #468536

# Submission time Handle Problem Language Result Execution time Memory
468536 2021-08-28T16:42:15 Z mosiashvililuka Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 2000 ms 460 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],pas,dp[200009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	for(t=1; t<=tes; t++){
		cin>>c>>d>>e;
		for(i=c; i<=d; i++) f[i]+=e;
		pas=0;
		/*for(i=2; i<=a; i++){
			pas+=abs(f[i]-f[i-1]);
			if((i!=a&&f[i]>=f[i-1]&&f[i]>=f[i+1])||(i!=a&&f[i]<=f[i-1]&&f[i]<=f[i+1])){
				pas-=min(abs(f[i]-f[i-1]),abs(f[i]-f[i+1]));
			}
		}
		cout<<pas<<"\n";*/
		for(i=1; i<=a; i++){
			zx=f[i];xc=f[i];dp[i]=0;
			for(j=i; j>=1; j--){
				zx=min(zx,f[j]);xc=max(xc,f[j]);
				dp[i]=max(dp[i],dp[j-1]+xc-zx);
			}
		}
		cout<<dp[a]<<"\n";
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 9 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 9 ms 332 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 9 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 9 ms 332 KB Output is correct
7 Execution timed out 2080 ms 460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 9 ms 332 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 9 ms 332 KB Output is correct
7 Execution timed out 2080 ms 460 KB Time limit exceeded
8 Halted 0 ms 0 KB -