Submission #625842

#	Time	Username	Problem	Language	Result	Execution time	Memory
625842		ETK	메기 농장 (IOI22_fish)	C++17	100 / 100	130 ms	15392 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
const int N = 2e5 + 5;
#define inf 2e18
ll max_weights(int n,int m,vi X,vi Y,vi W){
    vector <vector<pii>> vec(n);
    rep(i,0,m)vec[X[i]].pb({Y[i],W[i]});
    vector <ll> f,g,lstf,lstg,Mx(n,-inf);
    rep(x,0,n){
        sort(ALL(vec[x]));
        int m = sz(vec[x]);
        swap(f,lstf),swap(g,lstg);
        f = g = vector <ll> (m,-inf);
        int j = sz(lstf) - 1;
        ll mxlst = -inf,mxcur = -inf;
        if(x){
            per(i,m - 1,0){
                int y = vec[x][i].fi,w = vec[x][i].se;
                f[i] = max(mxcur,0ll) + w;
                if(x > 1)f[i] = max(f[i],Mx[x - 2] + w);
                while(j >= 0 && vec[x - 1][j].fi > y){
                    mxlst = max(mxlst,lstf[j]);
                    j--; 
                }
                f[i] = max(f[i],mxlst + w);
                mxcur = max(mxcur,f[i]);
            }
        }
        if(sz(lstf))mxlst = *max_element(ALL(lstf));
        ll mxlstg = -inf,mxcurg = -inf;
        if(x < n - 1){
            j = 0;
            rep(i,0,m){
                int y = vec[x][i].fi,w = vec[x][i].se;
                g[i] = max(mxcurg,0ll) + w;
                if(x >= 2)g[i] = max(g[i],Mx[x - 2] + w);
                //no pier is on x when considering mxlstf
                g[i] = max(g[i],mxlst + w);
                while(j < sz(lstg) && vec[x - 1][j].fi < y){
                    mxlstg = max(mxlstg,lstg[j]);
                    j++;
                }
                g[i] = max(g[i],mxlstg + w);
                mxcurg = max(mxcurg,g[i]);
            }
        }
        if(x)Mx[x] = Mx[x - 1];
        //the maximum answer we can get in the first x columns
        Mx[x] = max(Mx[x],max(mxcur,mxcurg));
    }
    return Mx[n - 1];
}

• 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