Submission #632023

#	Time	Username	Problem	Language	Result	Execution time	Memory
632023		timreizin	Catfish Farm (IOI22_fish)	C++17	6 / 100	136 ms	16236 KiB

fish

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "fish.h"

#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

using ll = long long;

ll solve(vector<vector<pair<int, ll>>> &fish, int n)
{
    ll res = 0;
    vector<vector<ll>> dp0(fish.size()), dp1(fish.size());
    ll sum = 0;
    for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
    for (int i = 0; i < fish.size(); ++i)
    {
        fish[i].emplace_back(n, 0);
        dp0[i].resize(fish[i].size());
        ll mx = 0;
        if (i != 0)
        {
            for (int j = 0; j < fish[i - 1].size(); ++j)
            {
                mx = max(mx, dp1[i - 1][j]);
            }
            fill(dp0[i].begin(), dp0[i].end(), mx);
            mx = 0;
        }
        for (int j = 0, k = 0; j < fish[i].size(); ++j)
        {
            if (i != 0)
            {
                while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
                {
                    mx = max(mx, dp0[i - 1][k]);
                    mx += fish[i - 1][k].second;
                    ++k;
                }
            }
            dp0[i][j] = max(mx, dp0[i][j]);
        }
        dp1 = dp0;
        if (i != 0)
        {
            ll mx = 0;
            for (int j = (int)fish[i].size() - 1, k = (int)fish[i - 1].size() - 1; j >= 0; --j)
            {
                 while (k >= 0 && fish[i - 1][k].first > fish[i][j].first)
                 {
                     mx = max(mx, dp1[i - 1][k]);
                     --k;
                 }
                mx += fish[i][j].second;
                dp1[i][j] = max(dp1[i][j], mx);
                res = max(dp1[i][j], res);
            }
        }
    }
    return res;
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
    vector<tuple<int, int, ll>> xyw(m);
    for (int i = 0; i < m; ++i) xyw[i] = {X[i], Y[i], W[i]};
    sort(xyw.begin(), xyw.end());
    ll res = 0;
    vector<vector<pair<int, ll>>> tos;
    int prevX = -1;
    ll sum = 0;
    vector<ll> a(n);
    for (auto [x, y, w] : xyw)
    {
        a[x] = w;
        sum += w;
        if (x > prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
            //res += solve(tos, n);
            tos.clear();
            tos.push_back(vector<pair<int, ll>>());
            prevX = x - 1;
        }
        if (x == prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
        }
        tos.back().emplace_back(y, w);
        prevX = x;
    }
    if (prevX != n - 1) tos.push_back(vector<pair<int, ll>>());
    res += solve(tos, n);
    //assert(res <= sum);
    return res;
}
/*
5 6
4 2 1
2 0 2
2 2 4
2 4 8
4 3 16
2 1 32
*/

/*
5 5
0 0 4
1 0 8
2 0 5
3 0 1
4 0 9
*/

Compilation message (stderr)

fish.cpp: In function 'll solve(std::vector<std::vector<std::pair<int, long long int> > >&, int)':
fish.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
      |                     ~~^~~~~~~~~~~~~
fish.cpp:18:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
      |                                                           ~~^~~~~~~~~~~~~~~~
fish.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < fish.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
fish.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int j = 0; j < fish[i - 1].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:33:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j = 0, k = 0; j < fish[i].size(); ++j)
      |                                ~~^~~~~~~~~~~~~~~~
fish.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
      |                        ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 6 / 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