oj.uz

답안 #991873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991873 2024-06-03T10:06:42 Z thinknoexit 메기 농장 (IOI22_fish) C++17
15 / 100
 934 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N, m = M;
    int r = 0, c = 0;
    for (int i = 0;i < m;i++) {
        r = max(r, X[i] + 1);
        c = max(c, Y[i] + 1);
    }
    c++;
    r = min(n, r + 1);
    vector<vector<int>> a(r + 1, vector<int>(c + 1, 0));
    vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(r + 1, vector<ll>(c + 1, 0ll)));
    for (int i = 0;i < m;i++) {
        a[X[i] + 1][Y[i] + 1] = W[i];
    }
    ll mx;
    for (int i = 2;i <= r;i++) {
        // (0)
        mx = 0;
        for (int j = 0;j <= c;j++) {
            mx = max(mx + a[i - 1][j], dp[0][i - 1][j]);
            dp[0][i][j] = mx;
        }
        if (i >= 3) { // i - 2
            ll sum = 0;
            mx = 0;
            for (int j = 0;j <= c;j++) {
                mx = max({ mx, dp[0][i - 2][j], dp[1][i - 2][j] });
                sum += a[i - 1][j];
                dp[0][i][j] = max(dp[0][i][j], mx + sum);
                dp[1][i][j] = max(dp[1][i][j], mx + sum);
            }
            mx = 0;
            for (int j = c;j >= 0;j--) {
                mx = max({ mx, max(dp[0][i - 2][j], dp[1][i - 2][j]) + sum });
                dp[0][i][j] = max(dp[0][i][j], mx);
                dp[1][i][j] = max(dp[1][i][j], mx);
                sum -= a[i - 1][j];
            }
        }
        // (1)
        mx = 0;
        for (int j = c;j >= 0;j--) {
            dp[1][i][j] = mx;
            mx = max({ mx + a[i][j], dp[0][i - 1][j], dp[1][i - 1][j] });
        }
    }
    ll ans = 0;
    for (int i = 1;i <= r;i++) {
        for (int j = 0;j <= c;j++) {
            ans = max({ ans, dp[0][i][j], dp[1][i][j] });
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11760 KB Output is correct
2 Correct 25 ms 13256 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 5 ms 9452 KB Output is correct
5 Runtime error 934 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 35 ms 14804 KB Output is correct
3 Correct 43 ms 16672 KB Output is correct
4 Correct 19 ms 10232 KB Output is correct
5 Correct 30 ms 11732 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 9424 KB Output is correct
12 Correct 21 ms 12836 KB Output is correct
13 Correct 25 ms 14548 KB Output is correct
14 Correct 21 ms 12824 KB Output is correct
15 Correct 25 ms 14292 KB Output is correct
16 Correct 23 ms 12836 KB Output is correct
17 Correct 24 ms 14284 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 22 ms 22108 KB Output is correct
3 Correct 31 ms 21072 KB Output is correct
4 Correct 34 ms 20796 KB Output is correct
5 Correct 43 ms 24660 KB Output is correct
6 Correct 53 ms 24660 KB Output is correct
7 Correct 42 ms 24656 KB Output is correct
8 Correct 41 ms 24656 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 22 ms 22108 KB Output is correct
3 Correct 31 ms 21072 KB Output is correct
4 Correct 34 ms 20796 KB Output is correct
5 Correct 43 ms 24660 KB Output is correct
6 Correct 53 ms 24660 KB Output is correct
7 Correct 42 ms 24656 KB Output is correct
8 Correct 41 ms 24656 KB Output is correct
9 Runtime error 932 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11760 KB Output is correct
2 Correct 25 ms 13256 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 5 ms 9452 KB Output is correct
5 Runtime error 934 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -