Submission #1114336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114336		Mike_Vu	Catfish Farm (IOI22_fish)	C++17	100 / 100	121 ms	32616 KiB

fish

#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e5+5;
const ll INF = (ll)3e18+7;
int n, m;
vector<pii> a[maxn];
vector<ll> dp1[maxn], dp0[maxn];
ll ans = 0;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    for (int i= 0 ;i < m ;i++) {
        int x = X[i]+1, y = Y[i]+1, w = W[i];
        a[x].pb({y, w});
    }
    for (int i = 1; i <= n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    ll ma10, ma11, ma0;
    ma10 = ma11 = ma0 = 0;
    //dp
    for (int pos= 1; pos <= n; pos++) {
        //init
        dp1[pos].assign((int)a[pos].size(), -INF);
        dp0[pos].assign((int)a[pos].size(), -INF);
        int len = (int)a[pos].size();
        //inc -> 0
        if (pos < n) {
            int j = -1;
            ll malas = 0;
            for (int i = 0; i < len; i++) {
                dp0[pos][i] = max(ma10, ma0);
                if (i > 0) maximize(dp0[pos][i], dp0[pos][i-1]);
                if (pos > 1) {
                    while (j+1 < (int)a[pos-1].size() && a[pos-1][j+1].fi < a[pos][i].fi) {
                        ++j;
                        maximize(malas, dp0[pos-1][j]);
                    }
                    if (j > -1 && a[pos-1][j].fi < a[pos][i].fi) {
                        maximize(dp0[pos][i], malas);
                    }
                }
                dp0[pos][i] += a[pos][i].se;
            }
        }
        //dec -> 1
        if (pos > 1) {
            int j = (int)a[pos-1].size();
            ll malas = 0;
            for (int i = len-1; i >= 0; i--) {
                dp1[pos][i] = max(ma11, ma0);
                if (i < len-1) maximize(dp1[pos][i], dp1[pos][i+1]);
                while (j-1 >= 0 && a[pos-1][j-1].fi > a[pos][i].fi) {
                    --j;
                    maximize(malas, dp1[pos-1][j]);
                }
                if (j < (int)a[pos-1].size() && a[pos-1][j].fi > a[pos][i].fi) {
                    maximize(dp1[pos][i], malas);
                }
                dp1[pos][i] += a[pos][i].se;
            }
        }
        //update ma
        for (int i = 0; i < len; i++) {
            maximize(ma10, dp1[pos][i]);
            maximize(ans, dp1[pos][i]);
            maximize(ans, dp0[pos][i]);
        }
        if (pos > 1) {
            for (int i = 0; i < (int)a[pos-1].size(); i++) {
                maximize(ma11, dp1[pos-1][i]);
                maximize(ma0, dp0[pos-1][i]);
            }
        }
    }
//    for (int pos = 1; pos <= n; pos++) {
//        cout << "curpos " << pos << "\n";
//        for (int i= 0; i < (int)a[pos].size(); i++) {
//            cout << a[pos][i].fi << ' ' << a[pos][i].se << ' ' << (dp0[pos][i] <= -INF ? -1 : dp0[pos][i]) << ' ' << (dp1[pos][i] <= -INF ? -1 : dp1[pos][i]) << "\n";
//        }
//    }
    return ans;
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, M;
    vector<int> X, Y, W;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        X.pb(x);
        Y.pb(y);
        W.pb(w);
    }
    cout << max_weights(N, M, X, Y, W);
}
#endif // mikevui
/*
3 3
2 1 5
1 2 1
1 0 2
6

5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16