제출 #1141610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141610		sayan	Sjeckanje (COCI21_sjeckanje)	C++20	15 / 110	186 ms	444 KiB

Main

#include <bits/stdc++.h>
#define Sayan ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define sz() size()
#define F first
#define S second
#define pb push_back
#define yes cout << "YES\n"
#define no cout << "NO\n"
using namespace std ;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const ll N = 200+5;
const ll inf = 1e18;
const int mod = 1e9+7; // 998244353;
//////////////////////////////////////////////////////
ll TEST=0;
ll n , q;
map<ll,ll>mp;
ll a[N] , dp[N] , lz[N*4];
pair<ll , ll> t[N*4];
//////////////////////////////////////////////////////
struct delai{
	// ll l,r;
};
// void push(ll tl,ll tr,ll v){
	// t[v+v].F+=lz[v];
	// t[v+v+1].F+=lz[v];
	// t[v+v].S+=lz[v];
	// t[v+v+1].S+=lz[v];
	// lz[v+v]+=lz[v];
	// lz[v+v+1]+=lz[v];
	// lz[v]=0;
// }
// void build(ll v=1,ll tl=1,ll tr=n){
	// if(tl==tr){
		// t[v]={a[tl],a[tl]};
		// return ;
	// }
	// ll tm=(tl+tr)/2;
	// build(v+v,tl,tm);
	// build(v+v+1,tm+1,tr);
	// t[v].F=min(t[v+v].F,t[v+v+1].F);
	// t[v].S=max(t[v+v].S,t[v+v+1].S);
// }
// ll get(ll l,ll r,ll ok,ll v=1,ll tl=1,ll tr=n){
	// push(tl,tr,v);
	// if(l<=tl && tr<=r){
		// if(ok==1)return t[v].F;
		// else return t[v].S;
	// }
	// if(tr<l or r<tl){
		// if(ok==1)return inf;
		// else return 0;
	// }
	// ll tm=(tl+tr)/2;
	// if(ok==1)return min(get(l,r,ok,v+v,tl,tm),get(l,r,ok,v+v+1,tm+1,tr));
	// else return max(get(l,r,ok,v+v,tl,tm),get(l,r,ok,v+v+1,tm+1,tr));
// }
// void upd(ll l,ll r,ll sum,ll v=1,ll tl=1,ll tr=n){
	// push(tl,tr,v);
	// if(l<=tl && tr<=r){
		// t[v].F+=sum;
		// t[v].S+=sum;
		// lz[v]+=sum;
		// return;
	// }
	// if(tr<l or r<tl){
		// return ;
	// }
	// ll tm=(tl+tr)/2;
	// upd(l,r,sum,v+v,tl,tm);
	// upd(l,r,sum,v+v+1,tm+1,tr);
	// t[v].F=min(t[v+v].F,t[v+v+1].F);
	// t[v].S=max(t[v+v].S,t[v+v+1].S);
// }
//////////////////////////////////////////////////////
void solve(){
	cin >> n >> q;
	for(ll i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	for(ll i = 1 ; i <= n ; i++){
		dp[i]=-inf;
	}
	// build();
	while(q--){
		ll l,r,sum;
		cin>>l>>r>>sum;
		// upd(l,r,sum);
		for(ll i=l;i<=r;i++)a[i]+=sum;
		ll ans=0;
		for(ll i=1;i<=n;i++)dp[i]=-inf;
		for(ll i=1;i<=n;i++){
			for(ll j=i;j>=1;j--){
				ll mn=inf;
				ll mx=-inf;
				for(ll k=j;k<=i;k++){
					mn=min(mn,a[k]);
					mx=max(mx,a[k]);
				}
				dp[i]=max(dp[i],mx-mn+dp[j-1]);
			}
			ans=max(ans,dp[i]);
		}
		cout<<ans<<"\n";
	}
}
signed main () {
	Sayan;
	ll t=1;
	if(TEST){
		cin>>t;	
	}
	while(t--)solve();
}

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