답안 #732557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732557	2023-04-29T05:59:44 Z	math_rabbit_1028	메기 농장 (IOI22_fish)	C++17	52 / 100	1000 ms	297680 KB

fish

#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

long long zero[3030], full[3030], dp[2][3030][3030], grid[3030][3030], sum[3030][3030];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for (int i = 0; i < M; i++) {
        X[i] += 1;
        Y[i] += 1;
        grid[X[i]][Y[i]] = W[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) sum[i][j] = sum[i][j - 1] + grid[i][j];
    }
    for (int j = 1; j < N; j++) dp[0][0][j] = dp[1][0][j] = -1e18;
    full[0] = -1e18;
    for (int i = 2; i <= N + 1; i++) {
        for (int k = 1; k < N; k++) zero[i] = max(zero[i], dp[1][i - 1][k] + sum[i][k]);
        zero[i] = max(zero[i], zero[i - 1]);
        zero[i] = max(zero[i], full[i - 1] + sum[i][N]);

        for (int k = 1; k < N; k++) full[i] = max(full[i], dp[0][i - 1][k] + sum[i - 1][N] - sum[i - 1][k]);
        full[i] = max(full[i], full[i - 1]);
        full[i] = max(full[i], zero[i - 2] + sum[i - 1][N]);
        full[i] = max(full[i], full[i - 2] + sum[i - 1][N]);
        for (int l = 1; l < N; l++) full[i] = max(full[i], dp[1][i - 2][l] + sum[i - 1][N]);

        long long val0 = 0, val1 = 0;
        for (int k = 1; k < N; k++) {
            val0 = max(val0, dp[0][i - 1][k] - sum[i - 1][k]);
            val1 = max(val1, dp[1][i - 1][k] + sum[i][k]);
        }
        for (int j = 1; j < N; j++) {
            dp[0][i][j] = max(dp[0][i][j], val0 + sum[i - 1][j]);
            dp[1][i][j] = max(dp[1][i][j], val1 - sum[i][j]);
            dp[1][i][j] = max(dp[1][i][j], full[i - 1] + sum[i][N] - sum[i][j]);
            dp[0][i][j] = max(dp[0][i][j], zero[i - 2] + sum[i - 1][j]);
            dp[0][i][j] = max(dp[0][i][j], full[i - 2] + sum[i - 1][N]);
        }
        long long val2 = 0;
        for (int j = 1; j < N; j++) {
            val2 = max(val2, dp[1][i - 2][j]);
            dp[0][i][j] = max(dp[0][i][j], val2 + sum[i - 1][j]);
        }
        long long val3 = 0;
        for (int j = N - 1; j >= 1; j--) {
            val3 = max(val3, dp[1][i - 2][j] + sum[i - 1][j]);
            dp[0][i][j] = max(dp[0][i][j], val3);
        }
    }
    long long res = 0;
    res = zero[N + 1];
    return res;
}

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1060 ms	102104 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	1078 ms	101180 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1075 ms	94536 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	6 ms	7252 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	7 ms	7240 KB	Output is correct
13	Correct	1 ms	1620 KB	Output is correct
14	Correct	5 ms	7232 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	6 ms	7252 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	7 ms	7240 KB	Output is correct
13	Correct	1 ms	1620 KB	Output is correct
14	Correct	5 ms	7232 KB	Output is correct
15	Correct	6 ms	7220 KB	Output is correct
16	Correct	2 ms	1604 KB	Output is correct
17	Correct	18 ms	9032 KB	Output is correct
18	Correct	19 ms	8916 KB	Output is correct
19	Correct	18 ms	9412 KB	Output is correct
20	Correct	18 ms	9420 KB	Output is correct
21	Correct	19 ms	9408 KB	Output is correct
22	Correct	31 ms	11604 KB	Output is correct
23	Correct	8 ms	8276 KB	Output is correct
24	Correct	13 ms	9080 KB	Output is correct
25	Correct	5 ms	7236 KB	Output is correct
26	Correct	7 ms	7892 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	6 ms	7252 KB	Output is correct
11	Correct	2 ms	3284 KB	Output is correct
12	Correct	7 ms	7240 KB	Output is correct
13	Correct	1 ms	1620 KB	Output is correct
14	Correct	5 ms	7232 KB	Output is correct
15	Correct	6 ms	7220 KB	Output is correct
16	Correct	2 ms	1604 KB	Output is correct
17	Correct	18 ms	9032 KB	Output is correct
18	Correct	19 ms	8916 KB	Output is correct
19	Correct	18 ms	9412 KB	Output is correct
20	Correct	18 ms	9420 KB	Output is correct
21	Correct	19 ms	9408 KB	Output is correct
22	Correct	31 ms	11604 KB	Output is correct
23	Correct	8 ms	8276 KB	Output is correct
24	Correct	13 ms	9080 KB	Output is correct
25	Correct	5 ms	7236 KB	Output is correct
26	Correct	7 ms	7892 KB	Output is correct
27	Correct	220 ms	226148 KB	Output is correct
28	Correct	81 ms	34956 KB	Output is correct
29	Correct	299 ms	229676 KB	Output is correct
30	Correct	343 ms	272512 KB	Output is correct
31	Correct	324 ms	273296 KB	Output is correct
32	Correct	95 ms	30692 KB	Output is correct
33	Correct	347 ms	297564 KB	Output is correct
34	Correct	340 ms	297680 KB	Output is correct
35	Correct	258 ms	233668 KB	Output is correct
36	Correct	318 ms	242764 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1075 ms	94536 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1060 ms	102104 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

답안 #732557

Compilation message