提出 #65470405

---

ソースコード 拡げる

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
typedef long long ll;
const int N = 3e5 + 5;

int n, m;
int l[N], r[N], s[N];

ll dist[N];
vector<int> adj[N];

void test_case() {
    cin >> n >> m;
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> s[i];
        s[i] -= (r[i] - l[i] + 1);
        adj[l[i] - 1].push_back(i);

        if (s[i] < 0) {
            cout << -1 << endl;
            return;
        }
    }
    ans = n;
    for (int i = n; i >= 0; i--) {
        for (int j = 0; j <= n; j++) {
            dist[j] = 0;
        }
        dist[i] = 0;
        for (int j = i; j <= n; j++) {
            for (auto &u : adj[j]) {
                dist[r[u]] = max(dist[r[u]], s[u] + dist[j]);
            }
            if(j+1<=n){
                dist[j+1]=max(dist[j+1], dist[j]);
            }
        }
        for (auto &u : adj[i]) {
            if (dist[r[u]] > s[u]) {
                cout << -1 << endl;
                return;
            }
        }
    }
    cout << ans + dist[n] << endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

提出情報

ジャッジ結果