oj.uz

답안 #679775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679775 2023-01-09T07:54:15 Z amir Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 1 ms 212 KB 
/*
<< 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] ;
int 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--){
		int l , r , x ;
		cin >> l >> r >> x ;
		for (int i = l ;i <= r ; i++) a[i] += x ;
		solve() ;
	}
	
	
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -