oj.uz

Submission #629799

# Submission time Handle Problem Language Result Execution time Memory
629799 2022-08-15T07:43:52 Z spacewalker Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#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

    so ???? a dp here

    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
*/

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));
    stasisOpt[N+2] = 0;
    for (int xc = N+1; xc >= 0; --xc) {
        for (int yc = 0; yc < N; ++yc) {
            ll &b = backFaceOpt[xc][yc], &f = frontFaceOpt[xc][yc], &s = stasisOpt[xc];
            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));
                }
            }
            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));
                }
                for (int nyc = yc; nyc < N; ++nyc) {
                    f = max(f, backFaceOpt[xc+1][nyc] + 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]);
            }
            /*
            printf("%d %d: back %lld front %lld stasis %lld ", xc, yc, b, f, s);
            if (xc > 0) printf("(raw values) %lld %lld\n", columnSum[xc-1][yc], columnSum[xc][yc]);
            */
        }
    }
    return stasisOpt[0];
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 915 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 236 KB Output is correct
2 Runtime error 877 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 93 ms 3256 KB Output is correct
11 Correct 14 ms 980 KB Output is correct
12 Correct 108 ms 3224 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 93 ms 3208 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 93 ms 3256 KB Output is correct
11 Correct 14 ms 980 KB Output is correct
12 Correct 108 ms 3224 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 93 ms 3208 KB Output is correct
15 Correct 96 ms 3156 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 106 ms 5032 KB Output is correct
18 Correct 105 ms 5016 KB Output is correct
19 Correct 103 ms 4948 KB Output is correct
20 Correct 108 ms 5004 KB Output is correct
21 Correct 121 ms 4984 KB Output is correct
22 Correct 113 ms 6704 KB Output is correct
23 Correct 93 ms 3540 KB Output is correct
24 Correct 99 ms 4280 KB Output is correct
25 Correct 108 ms 3236 KB Output is correct
26 Correct 97 ms 3480 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 12 ms 980 KB Output is correct
10 Correct 93 ms 3256 KB Output is correct
11 Correct 14 ms 980 KB Output is correct
12 Correct 108 ms 3224 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 93 ms 3208 KB Output is correct
15 Correct 96 ms 3156 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 106 ms 5032 KB Output is correct
18 Correct 105 ms 5016 KB Output is correct
19 Correct 103 ms 4948 KB Output is correct
20 Correct 108 ms 5004 KB Output is correct
21 Correct 121 ms 4984 KB Output is correct
22 Correct 113 ms 6704 KB Output is correct
23 Correct 93 ms 3540 KB Output is correct
24 Correct 99 ms 4280 KB Output is correct
25 Correct 108 ms 3236 KB Output is correct
26 Correct 97 ms 3480 KB Output is correct
27 Execution timed out 1109 ms 282920 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 915 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -