oj.uz

답안 #991872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991872 2024-06-03T10:05:11 Z thinknoexit 메기 농장 (IOI22_fish) C++17
15 / 100
 929 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);
            }
            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);
                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 18 ms 11512 KB Output is correct
2 Correct 22 ms 13524 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Runtime error 929 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 36 ms 17596 KB Output is correct
3 Correct 49 ms 20172 KB Output is correct
4 Correct 18 ms 11772 KB Output is correct
5 Correct 22 ms 13512 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 5 ms 9428 KB Output is correct
12 Correct 21 ms 14344 KB Output is correct
13 Correct 26 ms 16084 KB Output is correct
14 Correct 22 ms 14324 KB Output is correct
15 Correct 24 ms 15820 KB Output is correct
16 Correct 21 ms 14324 KB Output is correct
17 Correct 29 ms 15820 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 21 ms 22360 KB Output is correct
3 Correct 33 ms 22096 KB Output is correct
4 Correct 31 ms 21552 KB Output is correct
5 Correct 40 ms 26192 KB Output is correct
6 Correct 39 ms 25424 KB Output is correct
7 Correct 44 ms 26196 KB Output is correct
8 Correct 38 ms 26196 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 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 1 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 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 1 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 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 1 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 348 KB Output is correct
2 Correct 21 ms 22360 KB Output is correct
3 Correct 33 ms 22096 KB Output is correct
4 Correct 31 ms 21552 KB Output is correct
5 Correct 40 ms 26192 KB Output is correct
6 Correct 39 ms 25424 KB Output is correct
7 Correct 44 ms 26196 KB Output is correct
8 Correct 38 ms 26196 KB Output is correct
9 Runtime error 864 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 11512 KB Output is correct
2 Correct 22 ms 13524 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Runtime error 929 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -