#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define pb push_back
#define int long long
#define f first
#define s second
#define pll pair<long long, long long>
int mem[5005], a[5005], d[5005];
bool samesign(int a, int b){
if((a<=0 and b<=0) or (a>0 and b>0))return true;
return false;
}
signed main(){
int n,q;cin>>n>>q;
for(int i=0;i<n;i++){
cin>>a[i];
if(i>=1)d[i]=a[i]-a[i-1];
}
for(int i=0;i<q;i++){
int l,r,c;cin>>l>>r>>c;
l--,r--;
d[l]+=c;
d[r+1]-=c;
//~ cout<<endl;
//~ for(int j=0; j<n;j++)cout<<d[j]<<" ";
//~ cout<<endl;
fill(mem,mem+n+1,0);
mem[1]=abs(d[1]);
for(int j=2;j<n;j++){
if(samesign(d[j-1], d[j])){
mem[j]=mem[j-1]+abs(d[j]);
}
else{
mem[j]=max(mem[j-2]+abs(d[j]),mem[j-1]);
}
}
cout<<mem[n-1]<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |