Submission #940612

#	Time	Username	Problem	Language	Result	Execution time	Memory
940612		Ghetto	Catfish Farm (IOI22_fish)	C++17	9 / 100	31 ms	16952 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 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];
void precomp() {
    for (int i = 0; i < m; i++)
        val[x[i]] = w[i];
}

lint dp[MAX_N];
bool seen[MAX_N];
lint find_dp(int i) {
    assert(i >= -1);
    if (i == -1) return 0;
    if (i == 0) return val[0];
    if (seen[i]) return dp[i];

    lint leave = find_dp(i - 1);
    lint leave_prev = val[i] + find_dp(i - 2);
    lint take_prev = (i == 1 || i == n - 1) ? -INF : val[i] + val[i - 1] + find_dp(i - 3);
    dp[i] = max({leave, leave_prev, take_prev});

    seen[i] = true;
    return dp[i];
}

void init() {
    for (int i = 0; i < n; i++) {
        seen[i] = false;
        dp[i] = -INF;
        val[i] = 0;
    }
}

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;
    init();
    for (int i = 0; i < m; i++) {
        x[i] = tmp_x[i];
        y[i] = tmp_y[i];
        w[i] = tmp_w[i];
    }

    precomp();

    lint ans = find_dp(n - 1);
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16