Submission #1073107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073107		fv3	Catfish Farm (IOI22_fish)	C++17	9 / 100	20 ms	7004 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, M;
vector<int> X, Y, W;
vector<ll> c, dp;

ll get_score(int l, int r)
{
    if (l < 0) return 0;
    if (l == r - 1)
        return dp[l] - c[r] - c[l];
    if (l == r - 2)
        return dp[l] - c[l+1];
    return dp[l];
}

ll max_weights(int N_, int M_, vector<int> X_, vector<int> Y_, vector<int> W_) 
{
    N = N_; M = M_;
    X = X_; Y = Y_; W = W_;

    c = vector<ll>(N+1);
    dp = vector<ll>(N);

    for (int i = 0; i < M; i++)
        c[X[i]] = W[i];

    dp[0] = c[1];
    for (int i = 1; i < N; i++)
    {
        dp[i] = c[i-1] + c[i+1] + max({get_score(i-3, i), get_score(i-2, i), get_score(i-1, i)});
    }

    ll mx = 0;
    for (int i = 0; i < N; i++)
        mx = max(mx, dp[i]);

    return mx;
}

• 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