Submission #629804

#	Time	Username	Problem	Language	Result	Execution time	Memory
629804		spacewalker	Catfish Farm (IOI22_fish)	C++17	52 / 100	858 ms	2097152 KiB

fish

#include "fish.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000;

/*
    to make life easier, the value of a pier is (wt of fish behind/in front) - (wt of fish on pier)
    the path can be in a few states;
        - back-facing (pier at x=i that catches some fish at i-1)
        - front-facing (pier at x=i-1 that catches some fish at i)
    
    a back-facing path at y=h can move to
        - a back-facing path at some higher/same y value
        - a front-facing path at the same y value (do NOT count the - value of this pier, and ADD it to cancel the - of the ff path)

    a front-facing path at y=h can move to
        - a front-facing path at some lower/(same) y value
        - a back-facing path at some lower/same y value (do NOT count the + value of the first back-facing pier)
        - a back-facing path at a higher/(same) y value (do NOT count the + value of this pier)
        - stasis

    stasis can move to any back-facing path, or to stasis

    start the x-coordinates at 1; starting state is stasis at x=0
    pad 2 columns to the right; end state is stasis on last column

    then dp to get max weight path from start to end state
*/

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    vector<vector<ll>> weights(N + 3, vector<ll>(N));
    for (int i = 0; i < M; ++i) {
        weights[X[i] + 1][Y[i]] = W[i];
    }
    vector<vector<ll>> columnSum = weights;
    for (int xc = 0; xc < columnSum.size(); ++xc) {
        for (int yc = 1; yc < N; ++yc) {
            columnSum[xc][yc] += columnSum[xc][yc-1];
        }
    }
    // needs xc > 0
    auto pierValue = [&] (int xc, int yc, int c1, int c2) {
        return c1 * columnSum[xc-1][yc] + c2 * columnSum[xc][yc];
    };
    vector<ll> stasisOpt(N + 3, -INF);
    vector<vector<ll>> backFaceOpt(N+3, vector<ll>(N, -INF)), frontFaceOpt(N+3, vector<ll>(N, -INF));
    // mod = -pierValue(xc, yc, 1, 0) is added to the entries
    vector<ll> nxtBackFaceModPrefMax(N, -INF), nxtBackFaceSufMax(N, -INF), nxtFrontFacePrefMax(N, -INF);
    stasisOpt[N+2] = 0;
    for (int xc = N+1; xc >= 0; --xc) {
        ll &s = stasisOpt[xc];
        for (int yc = 0; yc < N; ++yc) {
            ll &b = backFaceOpt[xc][yc], &f = frontFaceOpt[xc][yc];
            if (0 < xc && xc <= N) {
                // find value for the back-facing path here
                b = max(b, frontFaceOpt[xc+1][yc] + pierValue(xc, yc, 1, 1));
                /*
                for (int nyc = yc; nyc < N; ++nyc) {
                    b = max(b, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, 1, -1));
                }
                */
                b = max(b, nxtBackFaceSufMax[yc] + pierValue(xc, yc, 1, -1));
            }
            if (2 <= xc && xc <= N + 1) {
                // find value for the front-facing path here
                f = max(f, stasisOpt[xc+1] + pierValue(xc, yc, -1, 1));
                /*
                for (int nyc = 0; nyc <= yc; ++nyc) {
                    f = max(f, frontFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 1));
                    f = max(f, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 1) - pierValue(xc+1, nyc, 1, 0));
                }
                */
                f = max(f, nxtFrontFacePrefMax[yc] + pierValue(xc, yc, -1, 1));
                f = max(f, nxtBackFaceModPrefMax[yc] + pierValue(xc, yc, -1, 1));
                /*
                for (int nyc = yc; nyc < N; ++nyc) {
                    f = max(f, backFaceOpt[xc+1][nyc] + pierValue(xc, yc, -1, 0));
                }
                */
                f = max(f, nxtBackFaceSufMax[yc] + pierValue(xc, yc, -1, 0));
            }
        }
        // find value for the stasis path here
        s = max(s, stasisOpt[xc+1]);
        for (int nyc = 0; nyc < N; ++nyc) {
            s = max(s, backFaceOpt[xc+1][nyc]);
        }
        // compute the prefix/suffix max arrays
        if (xc > 0) {
            nxtFrontFacePrefMax = frontFaceOpt[xc];
            for (int i = 1; i < N; ++i) nxtFrontFacePrefMax[i] = max(nxtFrontFacePrefMax[i-1], nxtFrontFacePrefMax[i]);
            nxtBackFaceModPrefMax = backFaceOpt[xc];
            for (int i = 0; i < N; ++i) nxtBackFaceModPrefMax[i] -= pierValue(xc, i, 1, 0);
            for (int i = 1; i < N; ++i) nxtBackFaceModPrefMax[i] = max(nxtBackFaceModPrefMax[i-1], nxtBackFaceModPrefMax[i]);
            nxtBackFaceSufMax = backFaceOpt[xc];
            for (int i = N - 2; i >= 0; --i) nxtBackFaceSufMax[i] = max(nxtBackFaceSufMax[i+1], nxtBackFaceSufMax[i]);
        }
    }
    return stasisOpt[0];
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int xc = 0; xc < columnSum.size(); ++xc) {
      |                      ~~~^~~~~~~~~~~~~~~~~~

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