Submission #1189260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189260		Boycl07	Catfish Farm (IOI22_fish)	C++20	100 / 100	154 ms	48216 KiB

fish

#include "fish.h"

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const ll LINF = 1e3;
const ll K = 1e2 + 3;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int N = 2e5 + 3;
const int M = 15;
const int LIM = 14348907 + 3;
const ll INF = 1e18;

vector<int> ind[N];
vector<ll> dp_inc[N];
vector<ll> dp_dec[N];
vector<pll> points[N];

ll get_sum(int x, int y)
{
    int u = upper_bound(all(points[x]), make_pair(1ll * y, INF)) - points[x].begin() - 1;
    if(u < 0) return 0;
    return points[x][u].second;
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{

    rep(i, m)
        points[X[i - 1] + 1].pb({Y[i - 1] + 1, W[i - 1]});

    forn(i, 0, n + 1)
    {
        sort(all(points[i]));
        for(int j = 1; j < sz(points[i]); ++j) points[i][j].second += points[i][j - 1].second;

        for(int j = 0; j < sz(points[i]); ++j) ind[i].pb(points[i][j].first - 1);
        ind[i].pb(0);
        ind[i].pb(n + 1);
        sort(all(ind[i]));
        ind[i].resize(unique(all(ind[i])) - ind[i].begin());

        dp_inc[i].assign(sz(ind[i]), -INF);
        dp_dec[i].assign(sz(ind[i]), -INF);
     }
     dp_inc[0][0] = dp_dec[0][0] = 0;


    for(int i = 1; i <= n + 1; ++i)
    {
        ll pref = 0;
//        cout << "increasing:\n";
        for(int j = 0, k = 0; j < sz(ind[i]); ++j)
        {
            int col = ind[i][j];
            while(k < sz(ind[i - 1]) && ind[i - 1][k] <= col)
            {
                maximize(pref, dp_inc[i - 1][k] - get_sum(i - 1, ind[i - 1][k]));
                ++k;
            }
            dp_inc[i][j] = max(get_sum(i - 1, ind[i][j]) + pref, dp_dec[i - 1][0]);
//            cout << i << " " << ind[i][j] << " " << dp_inc[i][j] << endl;
        }

        ll suf = 0;
//        cout << "decreasing:\n";
        for(int j = sz(ind[i]) - 1, k = sz(ind[i - 1]) - 1; j >= 0; --j)
        {
            int col = ind[i][j];
            while(k >= 0 && ind[i - 1][k] >= col)
            {
                maximize(suf, max(dp_inc[i - 1][k], dp_dec[i - 1][k]) + get_sum(i, ind[i - 1][k]));
                --k;
            }
            dp_dec[i][j] = suf - get_sum(i, ind[i][j]);
//            cout << i << " " << ind[i][j] << " " << dp_dec[i][j] << endl;
        }
    }
    return max(dp_inc[n + 1][0], dp_dec[n + 1][0]);
}

• 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