Submission #1161431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161431		The_Samurai	메기 농장 (IOI22_fish)	C++17	52 / 100	975 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];
    }
    int max_x = *max_element(X.begin(), X.end()) + 4;
    max_x = min(max_x, n);


    vector dp(max_x, 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 < max_x; i++) {
        ll mx = -1e18, mx2 = -1e18, mx3 = -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));

            if (i > 1) {
                maxs(mx3, dp[i - 2][j].ff);
                maxs(dp[i][j].ss, mx3 + pre[i - 1][j]);
            }





            

        }

        mx = -1e18;
        for (int j = 0; j <= n and i > 2; j++) {
            maxs(mx, dp[i - 3][j].ff + pre[i - 2][j]);
        }
        for (int j = 0; j <= n; j++) maxs(dp[i][j].ss, mx + pre[i - 1][j]);

        mx = -1e18, mx2 = -1e18, mx3 = -1e18;
        for (int j = n; j >= 0; j--) {
            maxs(dp[i][j].ff, mx - pre[i][j]);
            maxs(dp[i][j].ss, mx2);
            maxs(mx, dp[i - 1][j].ff + pre[i][j]);
            maxs(mx2, dp[i - 1][j].ff);

            if (i > 1) {
                maxs(mx3, dp[i - 2][j].ff + pre[i - 1][j]);
                maxs(dp[i][j].ss, mx3);
            }
            
            maxs(dp[i][j].ff, dp[i][j].ss);
            // maxlash esdan chiqmasin
        }
    }
    ll ans = 0;
    for (int i = 0; i < max_x; i++) {
        for (int j = 0; j < n; j++) maxs(ans, dp[i][j].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: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16