Submission #796529

#	Time	Username	Problem	Language	Result	Execution time	Memory
796529		adrilen	메기 농장 (IOI22_fish)	C++17	0 / 100	32 ms	8508 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;


vector <arr> fish[maxn];


ll dp[maxn][maxn][maxn] = { 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 = 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++) {
        for (int y = 1; y < (int)fish[i].size(); i++)
        {
            fish[i][y][1] += fish[i][y - 1][1];
        }
    }

    int h = 8;

    // Making the starting column start in the right place
    for (int x = 2; x <= n; 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), (1ll << 62)}) - 1))[1] - 
                    (*(upper_bound(fish[x - 1].begin(), fish[x - 1].end(), arr{f, (1ll << 62)}) - 1))[1]);

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

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


    ll output = 0;
    for (int s = 0; s < n; s++) for (int f = 0; f < n; f++) output = max(output, dp[n][s][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