Submission #858575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858575	2023-10-08T22:28:24 Z	LucaIlie	Catfish Farm (IOI22_fish)	C++17	35 / 100	1000 ms	1908968 KB

fish

#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].push_back( y - 1 );
               // possibleY[x].push_back( y );
                possibleY[x - 1].push_back( y );
                //possibleY[x - 1].push_back( y - 1 );
                possibleY[x + 1].push_back( y );
               // possibleY[x + 1].push_back( y - 1 );
            //}
        }
    }

    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	Execution timed out	1124 ms	1750968 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6504 KB	Output is correct
2	Execution timed out	1171 ms	1854796 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1168 ms	1908968 KB	Time limit exceeded
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	6488 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	6488 KB	Output is correct
9	Correct	18 ms	15964 KB	Output is correct
10	Correct	104 ms	27724 KB	Output is correct
11	Correct	16 ms	15976 KB	Output is correct
12	Correct	103 ms	27476 KB	Output is correct
13	Correct	3 ms	11096 KB	Output is correct
14	Correct	102 ms	27476 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	6488 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	6488 KB	Output is correct
9	Correct	18 ms	15964 KB	Output is correct
10	Correct	104 ms	27724 KB	Output is correct
11	Correct	16 ms	15976 KB	Output is correct
12	Correct	103 ms	27476 KB	Output is correct
13	Correct	3 ms	11096 KB	Output is correct
14	Correct	102 ms	27476 KB	Output is correct
15	Correct	101 ms	27680 KB	Output is correct
16	Correct	4 ms	11096 KB	Output is correct
17	Correct	134 ms	28756 KB	Output is correct
18	Correct	113 ms	28756 KB	Output is correct
19	Correct	114 ms	28748 KB	Output is correct
20	Correct	114 ms	28496 KB	Output is correct
21	Correct	117 ms	28756 KB	Output is correct
22	Correct	123 ms	29780 KB	Output is correct
23	Correct	105 ms	27888 KB	Output is correct
24	Correct	124 ms	28364 KB	Output is correct
25	Correct	106 ms	27696 KB	Output is correct
26	Correct	105 ms	27888 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	6488 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	6488 KB	Output is correct
9	Correct	18 ms	15964 KB	Output is correct
10	Correct	104 ms	27724 KB	Output is correct
11	Correct	16 ms	15976 KB	Output is correct
12	Correct	103 ms	27476 KB	Output is correct
13	Correct	3 ms	11096 KB	Output is correct
14	Correct	102 ms	27476 KB	Output is correct
15	Correct	101 ms	27680 KB	Output is correct
16	Correct	4 ms	11096 KB	Output is correct
17	Correct	134 ms	28756 KB	Output is correct
18	Correct	113 ms	28756 KB	Output is correct
19	Correct	114 ms	28748 KB	Output is correct
20	Correct	114 ms	28496 KB	Output is correct
21	Correct	117 ms	28756 KB	Output is correct
22	Correct	123 ms	29780 KB	Output is correct
23	Correct	105 ms	27888 KB	Output is correct
24	Correct	124 ms	28364 KB	Output is correct
25	Correct	106 ms	27696 KB	Output is correct
26	Correct	105 ms	27888 KB	Output is correct
27	Execution timed out	1078 ms	227472 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1168 ms	1908968 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1124 ms	1750968 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #858575

Compilation message