oj.uz

Submission #858576

# Submission time Handle Problem Language Result Execution time Memory
858576 2023-10-08T22:29:11 Z LucaIlie Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 247164 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3002;
const int MAX_M = 3e5;
const long long INF = 1e18;
int costCell[MAX_N][MAX_N];
long long dp[MAX_N][MAX_N], dpLower[MAX_N][MAX_N], spX[MAX_N][MAX_N];
vector<int> possibleY[MAX_N];

long long max_weights( int n, int m, vector <int> X, vector <int> Y, vector <int> W ) {

    for ( int i = 0; i < m; i++ ) {
        X[i]++;
        Y[i]++;
        costCell[X[i]][Y[i]] = W[i];
    }

    for ( int x = 1; x <= n; x++ ) {
        for ( int y = 1; y <= n; y++ ) {
            if ( costCell[x][y] ) {
                possibleY[x - 1].push_back( y );
                possibleY[x + 1].push_back( y );
            }
        }
    }

    possibleY[0].clear();
    possibleY[n + 1].clear();
    for ( int x = 0; x <= n + 1; x++ )
        possibleY[x].push_back( 0 );
    for ( int x = 1; x <= n; x++ ) {
        sort( possibleY[x].begin(), possibleY[x].end() );
        possibleY[x].resize( unique( possibleY[x].begin(), possibleY[x].end() ) - possibleY[x].begin() );
    }

    for ( int x = 1; x <= n; x++ ) {
        for ( int y = 1; y <= n; y++ )
            spX[x][y] = spX[x][y - 1] + costCell[x][y];
    }

    dp[0][0] = dpLower[0][0] = 0;
    for ( int x = 1; x <= n + 1; x++ ) {
        for ( int crtY: possibleY[x] ) {
            dp[x][crtY] = dpLower[x][crtY] = -INF;
            for ( int prevY: possibleY[x - 1] ) {
                if ( prevY <= crtY ) {
                    dpLower[x][crtY] = max( dpLower[x][crtY], dpLower[x - 1][prevY] + spX[x - 1][crtY] - spX[x - 1][prevY] );
                    dp[x][crtY] = max( dp[x][crtY], dpLower[x - 1][prevY] + spX[x - 1][crtY] - spX[x - 1][prevY] );
                }
                if ( prevY >= crtY )
                    dp[x][crtY] = max( dp[x][crtY], dp[x - 1][prevY] + spX[x][prevY] - spX[x][crtY] );
            }
            if ( x >= 2 ) {
                for ( int prevY: possibleY[x - 2] ) {
                    if ( prevY <= crtY ) {
                        dpLower[x][crtY] = max( dpLower[x][crtY], dp[x - 2][prevY] + spX[x - 1][crtY] );
                        dp[x][crtY] = max( dp[x][crtY], dp[x - 2][prevY] + spX[x - 1][crtY] );
                    }
                    if ( prevY >= crtY ) {
                        dpLower[x][crtY] = max( dpLower[x][crtY], dp[x - 2][prevY] + spX[x - 1][prevY] );
                        dp[x][crtY] = max( dp[x][crtY], dp[x - 2][prevY] + spX[x - 1][prevY] );
                    }
                }
            }
        }
    }

    return dp[n + 1][0];
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 698 ms 29408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Runtime error 731 ms 36364 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 738 ms 5152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 15448 KB Output is correct
10 Correct 5 ms 26460 KB Output is correct
11 Correct 2 ms 15452 KB Output is correct
12 Correct 4 ms 26456 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 4 ms 26460 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 15448 KB Output is correct
10 Correct 5 ms 26460 KB Output is correct
11 Correct 2 ms 15452 KB Output is correct
12 Correct 4 ms 26456 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 4 ms 26460 KB Output is correct
15 Correct 4 ms 26488 KB Output is correct
16 Correct 4 ms 11100 KB Output is correct
17 Correct 73 ms 27936 KB Output is correct
18 Correct 68 ms 27984 KB Output is correct
19 Correct 50 ms 27996 KB Output is correct
20 Correct 42 ms 28160 KB Output is correct
21 Correct 41 ms 28244 KB Output is correct
22 Correct 124 ms 29780 KB Output is correct
23 Correct 11 ms 26716 KB Output is correct
24 Correct 42 ms 27476 KB Output is correct
25 Correct 4 ms 26712 KB Output is correct
26 Correct 10 ms 26776 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 15448 KB Output is correct
10 Correct 5 ms 26460 KB Output is correct
11 Correct 2 ms 15452 KB Output is correct
12 Correct 4 ms 26456 KB Output is correct
13 Correct 2 ms 11100 KB Output is correct
14 Correct 4 ms 26460 KB Output is correct
15 Correct 4 ms 26488 KB Output is correct
16 Correct 4 ms 11100 KB Output is correct
17 Correct 73 ms 27936 KB Output is correct
18 Correct 68 ms 27984 KB Output is correct
19 Correct 50 ms 27996 KB Output is correct
20 Correct 42 ms 28160 KB Output is correct
21 Correct 41 ms 28244 KB Output is correct
22 Correct 124 ms 29780 KB Output is correct
23 Correct 11 ms 26716 KB Output is correct
24 Correct 42 ms 27476 KB Output is correct
25 Correct 4 ms 26712 KB Output is correct
26 Correct 10 ms 26776 KB Output is correct
27 Correct 67 ms 247164 KB Output is correct
28 Correct 719 ms 72656 KB Output is correct
29 Execution timed out 1059 ms 151864 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 738 ms 5152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 698 ms 29408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -