Submission #679786

#	Time	Username	Problem	Language	Result	Execution time	Memory
679786		amir	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	212 KiB

Main

/*
<< in the name of Allah >>
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' ;
const int maxn = 3e3 + 3 ;
ll dp[maxn] ;
ll a[maxn] ;
ll ghol[maxn] ;
ll n , q ;

ll Abs(ll x){
	if (x < 0) x = 0-x ;
	return x ;
}

void solve(){
	//for (int i = 1; i <= n ; i++) cout << a[i] << " " ;
	//cout << '\n' ;
	if (a[n] >= a[n-1]){
		int j = n-1 ;
		while (a[j] <= a[n] && j > 0){
			ghol[j] = n ;
			j-- ;
		}
	}
	else if (a[n] <= a[n-1]){
		int j = n-1 ;
		while (a[j] <= a[n] && j > 0){
			ghol[j] = n ;
			j-- ;
		}
	}
	for (int i = n-1 ; i > 1 ; i--){
		if (a[i] >= a[i-1] && a[i] > a[i+1]){
			int j = i-1 ;
			while (a[j] <= a[i] && j > 0){
				ghol[j] = i ;
				j-- ;
			}
		}
		else if (a[i] <= a[i-1] && a[i] < a[i+1]){
			int j = i-1 ;
			while (a[j] >= a[i] && j > 0){
				ghol[j] = i ;
				j-- ;
			}
		}
	}
	//for (int i = 1; i <= n ; i++) cout << ghol[i] << " " ;
	//cout << '\n' ;
	dp[n] = 0 ;
	dp[n+1] = 0 ;
	for (int i = n-1 ; i > 0 ; i--){
		ll x = Abs(a[ghol[i]]-a[i]) ;
		dp[i] = max(dp[i+1] , (x+dp[ghol[i]+1])) ;
		if (ghol[i] > i){
			ll y = Abs(a[ghol[i]-1]-a[i]) ;
			dp[i] = max(dp[i] , (y+dp[ghol[i]])) ;
		}
	}
	cout << dp[1] << '\n' ;
}


int main()
{
    /*ios::sync_with_stdio(false) ; 
	cin.tie(NULL) ;
	cout.tie(NULL) ;*/
	cin>> n >> q ;
	for (int i = 1;i <= n ; i++) cin >> a[i] ;
	while (q--){
		ll l , r , tt ;
		cin >> l >> r >> tt ;
		for (int i = l ; i <= r ; i++) a[i] += tt ;
		solve() ;
	}
	
	
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55