Submission #1036904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036904		_8_8_	Catfish Farm (IOI22_fish)	C++17	100 / 100	698 ms	209860 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 12;
typedef long long ll;
int n,m;
vector<vector<vector<ll>>> dp(N);
vector<int> g[N],in[N],t[N];
map<int,int> a[N];
long long max_weights(int nn, int mm,vector<int> X, vector<int> Y,vector<int> W) {
    n = nn;
    m = mm;
    for(int i = 0;i < m;i++) {
        X[i]++;
        Y[i]++;
        g[X[i]].push_back(Y[i]);
        a[X[i]][Y[i]] = W[i];
    }
    for(int i = 0;i <= n;i++) {
        for(int j:g[i]) {
            in[i].push_back(j - 1);
            in[i].push_back(j);
        }
        for(int j:g[i+1]) { 
            in[i].push_back(j);
        }
        for(int j:g[i-1]) {
            in[i].push_back(j);
        }
        in[i].push_back(0);
        sort(in[i].begin(),in[i].end());
        in[i].resize(unique(in[i].begin(),in[i].end()) - in[i].begin());
        dp[i].resize((int)in[i].size());
        for(int j = 0;j < (int)in[i].size();j++) {
            t[i].push_back((a[i].count(in[i][j]) ? a[i][in[i][j]] : 0));
            dp[i][j].resize(2);
        }
    }
    //0 : L > R
    //1 : L < R
    for(int i = 2;i <= n;i++) {
        int j1 = 0;
        ll mx = -1e18,p_ = 0,_p = 0;
        for(int j = 0;j < (int)in[i].size();j++) {
            _p += a[i - 1][in[i][j]];
            while(j1 < (int)in[i - 1].size() && in[i - 1][j1] <= in[i][j]) {
                p_ += (a[i - 1].count(in[i - 1][j1]) ? a[i - 1][in[i - 1][j1]] : 0);
                mx = max(mx,dp[i - 1][j1][1] - p_);
                j1++;
            }
            dp[i][j][1] = max(dp[i - 1][0][0],_p + mx);
        }
        j1 = (int)in[i - 1].size() - 1;
        mx = -1e18;
        p_ = 0,_p = 0;
        for(int j = (int)in[i].size() - 1;j >= 0;j--) {
            while(j1 >= 0 && in[i - 1][j1] >= in[i][j]) {
                mx = max(mx,max(dp[i - 1][j1][0],dp[i - 1][j1][1]) - _p);
                _p += (a[i].count(in[i - 1][j1]) ? a[i][in[i - 1][j1]] : 0);
                j1--;
            }
            dp[i][j][0] = p_ + mx;
            p_ += t[i][j];
        }
    }
    ll res = 0;
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j < (int)in[i].size();j++) {
            res = max({res,dp[i][j][0],dp[i][j][1]});
        }
    }
    return res;
}

• 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