답안 #825278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825278	2023-08-14T16:38:16 Z	PixelCat	메기 농장 (IOI22_fish)	C++17	52 / 100	723 ms	221216 KB

fish

#include "fish.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second 
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

inline void chmax(int &x, int val) { x = max(x, val); }

const int MAXN = 3000;
const int INF = 1e15;

int n, m;
int pre[MAXN + 10][MAXN + 10];
int dp1[MAXN + 10][MAXN + 10];
int dp2[MAXN + 10][MAXN + 10];

long long max_weights(i32 N, i32 M, vector<i32> X, vector<i32> Y,
                      vector<i32> W) {
    n = N;
    m = M;

    memset(pre, 0, sizeof(pre));
    For(i, 0, m - 1) {
        X[i]++; Y[i]++;
        pre[X[i]][Y[i]] += W[i];
    }
    For(i, 1, n) For(j, 1, n) {
        pre[i][j] += pre[i][j - 1];
    }

    For(i, 0, n + 1) For(j, 0, n + 1) {
        dp1[i][j] = dp2[i][j] = -INF;
    }
    dp2[0][0] = 0;

    For(i, 1, n + 1) {
        int mx = -INF;
        For(j, 1, n) {
            chmax(mx, dp1[i - 1][j] - pre[i - 1][j]);
            chmax(mx, dp2[i - 1][j] - pre[i - 1][j]);

            dp1[i][j] = dp2[i - 1][0];
            chmax(dp1[i][j], mx);
            dp1[i][j] += pre[i - 1][j];
        }
        mx = -INF;
        Forr(j, n, 0) {
            chmax(mx, dp2[i - 1][j]);

            dp2[i][j] = dp1[i - 1][j];
            chmax(dp2[i][j], mx - pre[i - 1][j]);
            dp2[i][j] += pre[i][j];
        }
    }

    int ans = 0;
    For(j, 0, n) chmax(ans, dp2[n + 1][j]);
    return ans;
}

/*

5 4
0 2 5
1 1 2
4 4 1
3 3 3

8

*/

Subtask #1
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	681 ms	149148 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	71200 KB	Output is correct
2	Runtime error	703 ms	153124 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	723 ms	144168 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	71244 KB	Output is correct
2	Correct	24 ms	71188 KB	Output is correct
3	Correct	24 ms	71252 KB	Output is correct
4	Correct	25 ms	71212 KB	Output is correct
5	Correct	25 ms	71240 KB	Output is correct
6	Correct	25 ms	71244 KB	Output is correct
7	Correct	25 ms	71236 KB	Output is correct
8	Correct	25 ms	71152 KB	Output is correct
9	Correct	25 ms	72804 KB	Output is correct
10	Correct	27 ms	75128 KB	Output is correct
11	Correct	26 ms	72700 KB	Output is correct
12	Correct	28 ms	74992 KB	Output is correct
13	Correct	26 ms	71848 KB	Output is correct
14	Correct	27 ms	75092 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	71244 KB	Output is correct
2	Correct	24 ms	71188 KB	Output is correct
3	Correct	24 ms	71252 KB	Output is correct
4	Correct	25 ms	71212 KB	Output is correct
5	Correct	25 ms	71240 KB	Output is correct
6	Correct	25 ms	71244 KB	Output is correct
7	Correct	25 ms	71236 KB	Output is correct
8	Correct	25 ms	71152 KB	Output is correct
9	Correct	25 ms	72804 KB	Output is correct
10	Correct	27 ms	75128 KB	Output is correct
11	Correct	26 ms	72700 KB	Output is correct
12	Correct	28 ms	74992 KB	Output is correct
13	Correct	26 ms	71848 KB	Output is correct
14	Correct	27 ms	75092 KB	Output is correct
15	Correct	28 ms	74968 KB	Output is correct
16	Correct	28 ms	72020 KB	Output is correct
17	Correct	36 ms	76876 KB	Output is correct
18	Correct	36 ms	76876 KB	Output is correct
19	Correct	37 ms	76860 KB	Output is correct
20	Correct	36 ms	76816 KB	Output is correct
21	Correct	37 ms	76768 KB	Output is correct
22	Correct	48 ms	78504 KB	Output is correct
23	Correct	29 ms	75408 KB	Output is correct
24	Correct	32 ms	76160 KB	Output is correct
25	Correct	26 ms	75084 KB	Output is correct
26	Correct	28 ms	75348 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	71244 KB	Output is correct
2	Correct	24 ms	71188 KB	Output is correct
3	Correct	24 ms	71252 KB	Output is correct
4	Correct	25 ms	71212 KB	Output is correct
5	Correct	25 ms	71240 KB	Output is correct
6	Correct	25 ms	71244 KB	Output is correct
7	Correct	25 ms	71236 KB	Output is correct
8	Correct	25 ms	71152 KB	Output is correct
9	Correct	25 ms	72804 KB	Output is correct
10	Correct	27 ms	75128 KB	Output is correct
11	Correct	26 ms	72700 KB	Output is correct
12	Correct	28 ms	74992 KB	Output is correct
13	Correct	26 ms	71848 KB	Output is correct
14	Correct	27 ms	75092 KB	Output is correct
15	Correct	28 ms	74968 KB	Output is correct
16	Correct	28 ms	72020 KB	Output is correct
17	Correct	36 ms	76876 KB	Output is correct
18	Correct	36 ms	76876 KB	Output is correct
19	Correct	37 ms	76860 KB	Output is correct
20	Correct	36 ms	76816 KB	Output is correct
21	Correct	37 ms	76768 KB	Output is correct
22	Correct	48 ms	78504 KB	Output is correct
23	Correct	29 ms	75408 KB	Output is correct
24	Correct	32 ms	76160 KB	Output is correct
25	Correct	26 ms	75084 KB	Output is correct
26	Correct	28 ms	75348 KB	Output is correct
27	Correct	121 ms	212760 KB	Output is correct
28	Correct	84 ms	92532 KB	Output is correct
29	Correct	197 ms	221144 KB	Output is correct
30	Correct	237 ms	221140 KB	Output is correct
31	Correct	220 ms	221140 KB	Output is correct
32	Correct	101 ms	88760 KB	Output is correct
33	Correct	232 ms	221064 KB	Output is correct
34	Correct	224 ms	221216 KB	Output is correct
35	Correct	146 ms	216804 KB	Output is correct
36	Correct	208 ms	221108 KB	Output is correct

Subtask #7
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	723 ms	144168 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	681 ms	149148 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

답안 #825278

Compilation message