Submission #1161411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161411		The_Samurai	Catfish Farm (IOI22_fish)	C++17	35 / 100	1104 ms	2162688 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second

void maxs(ll &a, ll b) {
    if (a < b) a = b;
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for (int i = 0; i < m; i++) Y[i]++;
    vector pre(n, vector(n + 1, 0ll));
    for (int i = 0; i < m; i++) pre[X[i]][Y[i]] += W[i];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j++) pre[i][j] += pre[i][j - 1];
    }

    vector dp(n, vector(n + 1, make_pair(0ll, 0ll)));
    // dp[i][j] - birinchi i'ta qatorni hisobga osak ohirgi qatorni boyi j bosa max javob
    // ff - o'zinikini qo'shilgan, ss - o'ziniki qo'shilmagan
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= j and i > 0; k++) {
                maxs(dp[i][j].ss, dp[i - 1][k].ss + pre[i - 1][j] - pre[i - 1][k]);
                maxs(dp[i][j].ss, dp[i - 1][k].ff);
            }
            for (int k = j + 1; k <= n and i > 0; k++) {
                maxs(dp[i][j].ff, dp[i - 1][k].ff + pre[i][k] - pre[i][j]);
                maxs(dp[i][j].ss, dp[i - 1][k].ff);
            }
            for (int k = 0; k <= n and i > 1; k++) {
                maxs(dp[i][j].ss, dp[i - 2][k].ff + pre[i - 1][max(j, k)]);
            }
            for (int k = 0; k <= n and i > 2; k++) {
                maxs(dp[i][j].ss, dp[i - 3][k].ff + pre[i - 2][k] + pre[i - 1][j]);
            }
            maxs(dp[i][j].ff, dp[i][j].ss);

            // maxlash esdan chiqmasin
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) maxs(ans, dp[n - 1][i].ff);
    return ans;
}

// g++ -o fish -O2 fish.cpp grader.cpp -std=c++20 && .\fish < input.txt > output.txt

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