Editorial for Bedao Grand Contest 01 - SEQGAME


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define maxn 100007
#define long long long
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }

int n,m;
long a[maxn];
long f[maxn],g[maxn];
int L[maxn],R[maxn],D[maxn];

void enter(){
    cin>>n>>m;

    forinc(i,1,m) cin>>L[i]>>R[i]>>D[i];
}

long max(const long &x,const long &y,const long &z){
    return max(x,max(y,z));
}

void solve(){
    forinc(i,1,m) a[L[i]]+=D[i],a[R[i]+1]-=D[i];

    forinc(i,1,n) a[i]+=a[i-1];

    forinc(i,1,n) f[i]=max(f[i-1],a[i]);

    fordec(i,n,1) g[i]=max(a[i],g[i+1]);

    long ans=2e18;

    forinc(i,1,m) ans = min(ans,max(f[L[i]-1],f[n]-D[i],g[R[i]+1]));

    cout<<ans;
}

signed main()
{
    checkfile("SEQGAME");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    enter();
    solve();

    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.