oj.uz

Submission #940632

# Submission time Handle Problem Language Result Execution time Memory
940632 2024-03-07T12:16:15 Z Ghetto Catfish Farm (IOI22_fish) C++17
0 / 100
 44 ms 12884 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 300 + 5, MAX_M = 3e5 + 5;
const lint INF = 5e18;

int n, m;
int x[MAX_M], y[MAX_M];
lint w[MAX_M];

lint val[MAX_N][13];
lint val_sum[MAX_N][13];
lint find_val_sum(int i, int l, int r) {
    if (r > l) return 0;
    return val_sum[i][r] - ((l == 0) ? 0 : val_sum[i][l - 1]);
}
void precomp() {
    for (int i = 0; i < m; i++) val[x[i]][y[i]] = w[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= 8; j++)
            val_sum[i][j] = val[i][j] + ((j == 0) ? 0 : val_sum[i][j - 1]);
}

unordered_map<int, unordered_map<int, lint>> dp[MAX_N];
void init2() {
    for (int i = -1; i <= 8; i++) dp[0][i][-1] = 0;
}

void init1() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 8; j++) val[i][j] = 0;
        for (int j = -1; j <= 8; j++)
            for (int k = -1; k <= 8; k++)
                dp[i][j][k] = -INF; 
    }
}

lint max_weights(int tmp_n, int tmp_m, vector<int> tmp_x, vector<int> tmp_y, vector<int> tmp_w) {
    n = tmp_n; 
    m = tmp_m;
    init1();
    for (int i = 0; i < m; i++) {
        x[i] = tmp_x[i];
        y[i] = tmp_y[i];
        w[i] = tmp_w[i];
    }

    precomp();
    init2();
    lint ans = -INF;
    for (int i = 1; i < n; i++) {
        for (int cur_y = -1; cur_y <= 8; cur_y++) {
            for (int prev_y1 = -1; prev_y1 <= 8; prev_y1++) {
                
                for (int prev_y2 = -1; prev_y2 <= 8; prev_y2++) {
                    if (i == 1 && prev_y2 != -1) continue;

                    int lo = max(prev_y1, prev_y2) + 1;
                    int hi = cur_y;
                    dp[i][cur_y][prev_y1] = max(dp[i][cur_y][prev_y1], find_val_sum(i - 1, lo, hi) + dp[i - 1][prev_y1][prev_y2]);
                }
                // cout << i << " " << cur_y << " " << prev_y1 << ": " << dp[i][cur_y][prev_y1] << endl; 
                if (i != n - 1) continue;

                lint new_ans = dp[i][cur_y][prev_y1] + ((prev_y1 > cur_y) ? find_val_sum(i, cur_y + 1, prev_y1): 0);
                ans = max(ans, new_ans);
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 7516 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 44 ms 12884 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 3676 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 1 ms 2396 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 3676 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 7516 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -