Submission #635500

#	Time	Username	Problem	Language	Result	Execution time	Memory
635500		OttoTheDino	Catfish Farm (IOI22_fish)	C++17	9 / 100	750 ms	133236 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,s,e)              for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)             for (ll i = s; i >= e; --i)
#define len(v)                  (ll)v.size()
#define pb                      push_back
#define all(v)                  v.begin(), v.end()
#define fi                      first
#define se                      second
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef pair<ll,ll> pll;
 
ll max_weights(int n, int m, vi X, vi Y, vi W) {
    bool done[n+5] = {};
    vector<ll> check[n+5], fish[n+5];
    unordered_map<ll,ll> w[n+5], dp[n+5][2];
 
    rep (i,0,m-1) {
        fish[X[i]+1].pb(Y[i]+1);
        w[X[i]+1][Y[i]+1] = W[i];
        check[X[i]+1].pb(Y[i]);
        if (Y[i]==0) done[X[i]+1] = 1;
    }
 
    rep (i,0,n) {
        if (i) check[i].pb(n);
        if (!done[i]) check[i].pb(0);
    }
 
    rep (i,1,n) {
 
        {
            //go bigger
            vector<pll> upd;
            set<ll> st;
            for (ll el : check[i]) upd.pb({el,1});
            for (ll el : fish[i-1]) upd.pb({el,0});
            for (ll el : check[i-1]) upd.pb({el,2});
            sort (all(upd));
            ll sum = 0;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) {
                    sum += w[i-1][y]; 
                }
                if (tp==1) {
                    ll res;
                    if (len(st)) {
                        res = sum+*st.rbegin();
                    }
                    else res = 0;
                    dp[i][0][y] = max(dp[i][0][y], res);
                    //cout << "1: " << i << " " << y << " " << dp[i][0][y] << endl;
                }
                if (tp==2) {
                    st.insert(dp[i-1][0][y]-sum);
                }
            }
        }
 
        {
            //go smaller
            vector<pll> upd;
            ll sum = 0, cur = 0;
            for (ll el : check[i]) upd.pb({el,3});
            for (ll el : fish[i+1]) {
                upd.pb({el, 0});
                sum += w[i+1][el]; 
            }
            for (ll el : fish[i]) {
                upd.pb({el, 1});
                cur += w[i][el];
            }
            for (ll el : check[i-1]) upd.pb ({el, 2});
            sort (all(upd));
            reverse(all(upd));
            set<ll> st;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) sum -= w[i+1][y]; 
                if (tp==1) cur -= w[i][y];
                if (tp==2) st.insert({dp[i-1][1][y]});
                if (tp==3) {
                    ll res = dp[i-1][0][n]+cur;
                    if (len(st)) res = max(res, *st.rbegin());
                    if (y==n) res = max(res, dp[i][0][n]+cur);
                    dp[i][1][y] = res-cur+sum;
                    //cout << "2: " << i << " " << y << " " << dp[i][1][y] << endl;
                    dp[i+1][0][y] = dp[i][1][y];
                }
            }
        }
    }
 
    ll ans = 0;
    for (ll y : check[n]) {
        ans = max(ans, dp[n][0][y]);
        ans = max(ans, dp[n][1][y]);
    }
 
    return ans;
}

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