Submission #1234736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234736		Ghulam_Junaid	Catfish Farm (IOI22_fish)	C++20	9 / 100	94 ms	27720 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"
// #include "grader.cpp"
using namespace std;

typedef long long ll;

vector<pair<int, int>> vec[(int)2e5 + 10];
int sm(int i, int p){
    int res = 0;
    for (auto [pos, val] : vec[i])
        if (pos <= p)
            res += val;
    return res;
}

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    vector<int> poss[n + 5];
    for (int i = 0; i < m; i ++)
        vec[x[i] + 1].push_back({y[i] + 1, w[i]});

    ll dp[n + 1][5][2] = {};
    for (int i = 0; i < 5; i ++)
        poss[0].push_back(0);
    for (int i = 1; i <= n; i ++){
        poss[i].push_back(0);
        for (auto P : vec[i - 1])
            poss[i].push_back(P.first);
        for (auto P : vec[i + 1])
            poss[i].push_back(P.first);
        while (poss[i].size() < 5) poss[i].push_back(0);
        sort(poss[i].begin(), poss[i].end());
    }

    for (int k = 0; k < 5; k ++)
        for (auto [p, v] : vec[2])
            if (p <= poss[1][k])
                dp[1][k][0]++, dp[1][k][1]++;
    
    for (int i = 2; i <= n; i ++){
        for (int ik = 0; ik < 5; ik ++){
            int k = poss[i][ik];
            for (int ipk = 0; ipk < 5; ipk ++){
                int pk = poss[i - 1][ipk];
                if (k >= pk) dp[i][ik][0] = max(dp[i][ik][0], dp[i - 1][ipk][0] - sm(i, pk) + sm(i - 1, k) - sm(i - 1, pk) + sm(i + 1, k));
                else dp[i][ik][1] = max(dp[i][ik][1], max(dp[i - 1][ipk][0], dp[i - 1][ipk][1]) - sm(i, k) + sm(i + 1, k));
            }
            for (int ipk = 0; ipk < 5; ipk ++){
                int pk = poss[i - 2][ipk];
                dp[i][ik][0] = max(dp[i][ik][0], max(dp[i - 2][ipk][0], dp[i - 2][ipk][1]) - sm(i - 1, pk) + sm(i - 1, max(pk, k)) + sm(i + 1, k));
            }

            // cout << i << " " << k << " : " << dp[i][ik][0] << ", " << dp[i][ik][1] << endl;
        }
    }

    ll ans = 0;
    for (int k = 0; k < 5; k ++) 
        ans = max(ans, max(dp[n][k][0], dp[n][k][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