Submission #874313

#	Time	Username	Problem	Language	Result	Execution time	Memory
874313		ngjabach	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	67 ms	17964 KiB

Main

// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=1e18+7;
struct ask{
    int x,y;
    ll z;
};
ll arr[N];
int q,n;
vector<ask>queries;
namespace sub1{
    ll a[205],dp[205],minis[205][205],maxis[205][205];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<=n;++i){
                maxis[i][i]=a[i];
                minis[i][i]=a[i];
                for(int j=i+1;j<=n;++j){
                    maxis[i][j]=max(maxis[i][j-1],a[j]);
                    minis[i][j]=min(minis[i][j-1],a[j]);
                }
            }
            dp[0]=0;
            for(int i=1;i<=n;++i){
                dp[i]=-INF;
                for(int j=1;j<=i;++j) dp[i]=max(dp[i],dp[j-1]+maxis[j][i]-minis[j][i]);
            }
            ans.pb(dp[n]);
        }
        return ans;
    }
}
namespace sub2{
    ll a[3005],dp[3005][2],d[3005];
    vector<ll>ans;
    vector<ll>solve(){
        ans.clear();
        int x,y; ll z;
        for(int i=1;i<=n;++i) a[i]=arr[i];
        for(int t=0;t<q;++t){
            x=queries[t].x; y=queries[t].y; z=queries[t].z;
            for(int i=x;i<=y;++i) a[i]+=z;
            for(int i=1;i<n;++i) d[i]=a[i]-a[i+1];
            dp[0][0]=0; dp[0][1]=0; d[n]=0;
            for(int i=1;i<n;++i){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=max(dp[i-1][0],dp[i-1][1]*(d[i]*d[i-1]>=0))+abs(d[i]);
            }
//            cout<<"a: "; for(int i=1;i<=n;++i) cout<<a[i]<<" "; cout<<endl;
//            cout<<"d: "; for(int i=1;i<=n;++i) cout<<d[i]<<" "; cout<<endl;
//            cout<<"dp"<<endl;
//            for(int j=0;j<2;++j) for(int i=1;i<=n;++i) cout<<dp[i][j]<<" "; cout<<endl;
            ans.pb(max(dp[n-1][0],dp[n-1][1]));
        }
        return ans;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("RECIPE.inp","r",stdin);
//    freopen("RECIPE.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=0;i<q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        queries.pb({x,y,z});
    }
    vector<ll>ans;
//    if(n<=200 and q<=200) ans=sub1::solve();
//    else if(n<=3000 and q<=3000) 
    ans=sub2::solve();
    for(ll &tmp:ans) cout<<tmp<<endl;
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/

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