Submission #68920138

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i ++)
#define per(i, s, t) for(int i = (s); i >= (t); i --)
template<typename T, typename T2>
inline void chmin(T &x, T2 &&y) { x = min(x, y); }
template<typename T, typename T2>
inline void chmax(T &x, T2 &&y) { x = max(x, y); }
typedef long long ll;

template<int N, int M, typename _T, _T inf>
struct fyl
{
    int n, m, fst[N], nxt[M << 1], to[M << 1], h = 2; _T w[M << 1], c[M << 1];

    void add(int x, int y, _T z, _T q)
    {
        nxt[h] = fst[x], fst[x] = h, to[h] = y, w[h] = z, c[h] = q, h ++;
    }

    void adde(int x, int y, _T z, _T c) {add(x, y, z, c);add(y, x, 0, -c);}

    int S, T, cur[N]; _T ans, dep[N];
    bool vis[N];
    _T find(int x, _T lim)
    {
        if(x == T) return lim;
        _T sum = 0; vis[x] = 1;
        for(int ii = cur[x], i = to[ii]; ii && sum < lim; ii = nxt[ii], i = to[ii])
        {
            cur[x] = ii;
            if(vis[i] || dep[i] != dep[x] - c[ii] || !w[ii]) continue;
            _T f = find(i, min(w[ii], lim - sum));
            if(!f) dep[i] = -1;
            w[ii] -= f, w[ii ^ 1] += f, sum += f, ans += f * c[ii];
        } vis[x] = 0;
        return sum;
    }

    bool inq[N];
    bool spfa()
    {
        queue<int> q;q.push(T);
        memset(dep, 0x3f, sizeof dep);
        memset(inq, 0, sizeof inq);
        dep[T] = 0;cur[T] = fst[T];
        while(!q.empty())
        {
            int t = q.front();q.pop();
            inq[t] = 0;
            for(int ii = fst[t], i = to[ii]; ii; ii = nxt[ii], i = to[ii])
            {
                if(!w[ii ^ 1] || dep[i] <= dep[t] + c[ii ^ 1]) continue;
                dep[i] = dep[t] + c[ii ^ 1];
                cur[i] = fst[i];
                if(!inq[i]) q.push(i), inq[i] = 1;
            }
        }
        if(dep[S] > inf) return false;
        return true;
    }

    _T dinic()
    {
        _T ans = 0;
        while(spfa()) ans += find(S, inf);
        return ans;
    }

    void clear()
    {
        memset(fst, 0, sizeof fst);
        memset(nxt, 0, sizeof nxt);
        h = 2, ans = 0;
    }
} ;
const int inf = 1e9;
const int N = 305, M = N * 4;
fyl<N, M, int, inf> g;

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

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m; rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) cin >> l[i] >> r[i];
    g.S = n + 1, g.T = n + 2;
    a[n + 1] = 1e9;
    int s = 0;
    rep(i, 1, n)
    {
        int d = a[i + 1] - a[i];
        if(d >= 0)
            g.adde(g.S, i, d + 1, 0);
        else g.adde(i, g.T, -d - 1, 0), s += -d - 1;
        g.adde(i, g.T, 1, 0), s ++;
    }
    rep(i, 1, m) if(l[i] > 1)
        g.adde(r[i], l[i] - 1, inf, 1);
    if(g.dinic() != s) return cout << -1, 0;
    else cout << g.ans;

    return 0;
}

Submission Info

Judge Result