Submission #59487047

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<int,int> P;
constexpr ll mod = 998244353;
typedef modint998244353 mi;

using S=long long;
S op(S x,S y){
    return max(x,y);
}
S e(){
    return LLONG_MIN;
}

int l[501],r[501];
ll v[501];

int main(){
    int w,n;
    cin>>w>>n;
    rep(i,n)cin>>l[i]>>r[i]>>v[i];

    vector<ll>val(w+1,-1e18);
    val[0]=0;
    segtree<S,op,e> dp(val);

    rep(i,n){
        for(int j=w;j>=l[i];j--){
            int R=max(0,j-l[i]+1),L=max(0,j-r[i]);
            ll new_val=dp.prod(L,R)+v[i];
            dp.set(j,max(dp.get(j),new_val));
        }
    }

    cout<<max(-1ll,dp.get(w))<<endl;

}

Submission Info

Judge Result