Submission #633171

#	Time	Username	Problem	Language	Result	Execution time	Memory
633171		JeanBombeur	Catfish Farm (IOI22_fish)	C++17	100 / 100	209 ms	43196 KiB

fish

#include "fish.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

//  <|°_°|>

//  M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int MAX_ROWS = (1e5 + 1);

vector <long long> DP_Built[MAX_ROWS];
vector <long long> DP_Free[MAX_ROWS];

vector <pair <int, long long>> CatFishs[MAX_ROWS];

long long max_weights(int nbRows, int nbCatfishs, vector <int> Col, vector <int> Row,
                      vector <int> Weight) {
    
    for (int i = 0; i < nbCatfishs; i ++)
    {
        CatFishs[Col[i] + 1].push_back({Row[i], Weight[i]});
    }
    for (int i = 0; i <= nbRows; i ++)
    {
        CatFishs[i].push_back({-1, 0});
        if (i)
            CatFishs[i].push_back({MAX_ROWS, 0});
        sort(CatFishs[i].begin(), CatFishs[i].end());
        DP_Built[i].resize(CatFishs[i].size());
        DP_Free[i].resize(CatFishs[i].size());
    }
    DP_Built[0] = {0};
    DP_Free[0] = {0};
    for (int i = 1; i <= nbRows; i ++)
    {
        long long maxiFree = - (1LL << 60);
        long long maxiBuilt = - (1LL << 60);
        int prev = 0;
        int sz = CatFishs[i - 1].size();
        int curSz = CatFishs[i].size();
        for (int fish = 0; fish < curSz - 1; fish ++)
        {
            while (prev < sz && CatFishs[i - 1][prev].first < CatFishs[i][fish + 1].first)
            {
                maxiBuilt = max(maxiBuilt, DP_Built[i - 1][prev]);
                maxiFree = max(maxiFree, DP_Free[i - 1][prev]);
                maxiFree += CatFishs[i - 1][prev ++].second;
            }
            DP_Built[i][fish] = max(maxiBuilt, maxiFree);
            DP_Free[i][fish + 1] = max(maxiBuilt, maxiFree);
        }
        maxiBuilt = - (1LL << 60);
        prev = sz - 1;
        for (int fish = curSz - 2; fish >= 0; fish --)
        {
            while (prev && CatFishs[i - 1][prev].first > CatFishs[i][fish + 1].first)
                maxiBuilt = max(maxiBuilt, DP_Built[i - 1][-- prev]);
            maxiBuilt += CatFishs[i][fish + 1].second;
            DP_Built[i][fish] = max(DP_Built[i][fish], maxiBuilt);
        }
        prev = 1;
        maxiFree = 0;
        for (int fish = 1; fish < curSz; fish ++)
        {
            maxiBuilt = - (1LL << 60);
            while (prev < sz && CatFishs[i - 1][prev + 1].first <= CatFishs[i][fish].first)
                maxiBuilt = max(maxiBuilt, DP_Built[i - 1][prev ++]);
            maxiFree += CatFishs[i][fish - 1].second;
            DP_Free[i][fish] = max(DP_Free[i][fish], maxiBuilt + maxiFree);
        }
    }
    long long ans = 0;
    for (long long a : DP_Built[nbRows])
        ans = max(ans, a);
    return ans;
}

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