Submission #796569

#	Time	Username	Problem	Language	Result	Execution time	Memory
796569		adrilen	Catfish Farm (IOI22_fish)	C++17	0 / 100	1094 ms	13596 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
using arr = array<ll, 2>;
constexpr int maxn = 305, maxm = 3e5;
int n, m;

constexpr int maxh = 302;

vector <arr> fish[maxn];


ll dp[maxn][maxh][maxh] = { 0 }; // Pos, pos - 2 column, pos - 1 column


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    n = N, m = M;

    for (int &i: X) i++;
    for (int &i : Y) i++;


    for (int i = 0; i < maxn; i++) fish[i].push_back({0, 0});

    for (int i = 0; i < m; i++)
    {
        fish[X[i]].push_back(arr{Y[i], W[i]});
    }

    
    for (int i = 0; i <= n; i++) sort(fish[i].begin(), fish[i].end());

    for (int i = 1; i <= n; i++) {
        // cout << "x: " << i << "\t";
        for (int y = 1; y < (int)fish[i].size(); y++)
        {
            fish[i][y][1] += fish[i][y - 1][1];
            // cout << fish[i][y][1] << " ";
        }
        // cout << "\n";
    }
    // cout << "\n\n\n";
    int h = maxh;
    h = min(n + 1, h);

    ll output = 0;

    // Making the starting column start in the right place
    for (int x = 2; x <= n + 1; x++)
    {
        // cout << "x: " << x << "\n";
        for (int s = 0; s < h; s++)         // Our new arm
        {
            // cout << "s: " << s << "\t";
            for (int f = 0; f < h; f++)     // Older arms
            {
                // dp[x][s][f] = max(dp[x - 1][f][y] + fish in column pos - 1 caught)

                for (int y = 0; y < h; y++)     
                {
                     
                    dp[x][s][f] = max(dp[x][s][f], dp[x - 1][f][y] + 
                    (*(upper_bound(fish[x - 1].begin(), fish[x - 1].end(), arr{max(s, y) + 1, -1}) - 1))[1] - 
                    (*(upper_bound(fish[x - 1].begin(), fish[x - 1].end(), arr{min(f, max(s, y)) + 1, -1}) - 1))[1]);

                    if (x == 2) break;
                }
                // cout << dp[x][s][f] << " ";
            }
            // cout << "\n";

            if (x == n + 1) 
            {
                break;
            }
        }

        // cout << "\n\n";
    }

    for (int f = 0; f < n; f++) output = max(output, dp[n + 1][0][f]);
    
    return output;
}

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