Submission #682401

#	Time	Username	Problem	Language	Result	Execution time	Memory
682401		sharaelong	Catfish Farm (IOI22_fish)	C++17	100 / 100	318 ms	76584 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 3e5 + 1;

vector<ll> dp[MAX_N];
vector<ll> up[MAX_N];
vector<ll> down[MAX_N];
vector<ll> sum[MAX_N];
vector<int> h[MAX_N];

// f(rom), j'th block of x=i place
ll ps(int i, int j, int f) {
    int H = h[i][j] - 1;
    int idx = upper_bound(h[f].begin(), h[f].end(), H) - h[f].begin();
    // cout << "ps: " << i << ' ' << j << ' ' << f << ' ' << sum[f][idx] << endl;
    return sum[f][idx];
}

// ub() is minimum exceeding h
int ub(int i, int j, int f) {
    int H = h[i][j];
    int idx = upper_bound(h[f].begin(), h[f].end(), H) - h[f].begin();
    // cout << "ub: " << i << ' ' << j << ' ' << f << ' ' << idx << endl;
    return idx;
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i=0; i<m; ++i) h[X[i]].push_back(Y[i]);
    for (int i=0; i<n; ++i) {
        h[i].push_back(n);
        sort(h[i].begin(), h[i].end());
        int sz = h[i].size() + 1;
        dp[i].resize(sz, 0);
        up[i].resize(sz, 0);
        down[i].resize(sz, 0);
        sum[i].resize(sz, 0);
    }
    
    for (int i=0; i<m; ++i) {
        int y = lower_bound(h[X[i]].begin(), h[X[i]].end(), Y[i]) - h[X[i]].begin() + 1;
        sum[X[i]][y] = W[i];
    }
    for (int i=0; i<n; ++i) {
        for (int j=1; j<h[i].size(); ++j) {
            sum[i][j] += sum[i][j-1];
        }
    }

    // i = 1
    {
        int N = h[1].size(), n1 = h[0].size();
        vector<ll> ps1(n1+1, 0), ps2(n1);
        ps2[0] = up[0][0];
        for (int j=n1-1; j>=0; --j) ps1[j] = max(ps1[j+1], dp[0][j] + ps(0, j, 1));
        for (int j=1; j<n1; ++j) ps2[j] = max(ps2[j-1], up[0][j] - sum[0][j]);
        
        for (int j=0; j<N; ++j) {
            down[1][j] = ps1[ub(1, j, 0)] - sum[1][j];
            if (ub(1, j, 0) > 0) up[1][j] = ps2[ub(1, j, 0)-1] + ps(1, j, 0);
            dp[1][j] = max(down[1][j], up[1][j]);
            // cout << j << ' ' << down[1][j] << ' ' << up[1][j] << endl;
        }
    }
    for (int i=2; i<n; ++i) {
        int N = h[i].size(), n1 = h[i-1].size(), n2 = h[i-2].size();
        vector<ll> ps1(n1+1, 0), ps2(n1), ps3(n2), ps4(n2+1, 0);
        ps2[0] = up[i-1][0];
        ps3[0] = dp[i-2][0];
        for (int j=n1-1; j>=0; --j) ps1[j] = max(ps1[j+1], dp[i-1][j] + ps(i-1, j, i));
        for (int j=1; j<n1; ++j) ps2[j] = max(ps2[j-1], up[i-1][j] - sum[i-1][j]);
        for (int j=1; j<n2; ++j) ps3[j] = max(ps3[j-1], dp[i-2][j]);
        for (int j=n2-1; j>=0; --j) ps4[j] = max(ps4[j+1], dp[i-2][j] + ps(i-2, j, i-1));
        
        for (int j=0; j<N; ++j) {
            down[i][j] = ps1[ub(i, j, i-1)] - sum[i][j];
            up[i][j] = ps4[ub(i, j, i-2)];
            if (ub(i, j, i-1) > 0) up[i][j] = max(up[i][j], ps2[ub(i, j, i-1)-1] + ps(i, j, i-1));
            if (ub(i, j, i-2) > 0) up[i][j] = max(up[i][j], ps3[ub(i, j, i-2)-1] + ps(i, j, i-1));
            dp[i][j] = max(down[i][j], up[i][j]);
        }
    }

    ll ans = *max_element(dp[n-1].begin(), dp[n-1].end());
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j=1; j<h[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~

• 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