제출 #1161412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161412		The_Samurai	Catfish Farm (IOI22_fish)	C++17	35 / 100	1101 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++) {
        ll mx = -1e18, mx2 = -1e18;
        for (int j = 0; j <= n; j++) {
            maxs(mx, dp[i - 1][j].ss - pre[i - 1][j]);
            maxs(mx2, dp[i - 1][j].ff);
            maxs(dp[i][j].ss, max(mx + pre[i - 1][j], mx2));




            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