제출 #940632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940632		Ghetto	메기 농장 (IOI22_fish)	C++17	0 / 100	44 ms	12884 KiB

fish

#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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16