Submission #1057395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057395		aykhn	Catfish Farm (IOI22_fish)	C++17	20 / 100	230 ms	164824 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 2e5 + 5;


long long mx[MXN];
vector<long long> lft[MXN], rig[MXN], in[MXN];
vector<long long> pre[2][MXN], suf[2][MXN];
vector<long long> dp[2][MXN];
vector<long long> ind[MXN];
vector<array<long long, 2>> val[MXN];

/*
0 = len[i] < len[i + 1];
1 = len[i] > len[i + 1];
*/
long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) 
{
    for (int i = 0; i < M; i++)
    {
        if (X[i] >= 1) ind[X[i]].push_back(Y[i] + 1);
        if (X[i] + 2 <= N) ind[X[i] + 2].push_back(Y[i] + 1);
        ind[X[i] + 1].push_back(Y[i] + 1);
        if (Y[i]) ind[X[i] + 1].push_back(Y[i]);
        val[X[i] + 1].push_back({Y[i] + 1, W[i]});
    }
    for (int i = 1; i <= N; i++) sort(ind[i].begin(), ind[i].end()), sort(val[i].begin(), val[i].end());
    for (int i = 1; i <= N; i++) 
    {
        int k1 = 0, k2 = 0, k3 = 0;
        for (int j = 0; j < ind[i].size(); j++)
        {
            lft[i].push_back((lft[i].empty() ? 0 : lft[i].back()));
            rig[i].push_back((rig[i].empty() ? 0 : rig[i].back()));
            in[i].push_back((in[i].empty() ? 0 : in[i].back()));
            while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
            while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
            while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        int k1 = 0, k2 = 0, k3 = 0, k4 = 0;
        for (int j = 0; j < ind[i].size(); j++)
        {
            dp[0][i].push_back(lft[i][j] + rig[i][j]);
            dp[1][i].push_back(lft[i][j] + rig[i][j]);
            if (i <= 1) continue;
            while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
            while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
            if (k1 - 1 >= 0) dp[0][i][j] = max(dp[0][i][j], pre[0][i - 1][k1 - 1] + (lft[i][j] + rig[i][j]));
            if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
            if (i <= 2) continue;
            while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
            while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
            long long A = (k3 - 1 >= 0 ? pre[1][i - 2][k3 - 1] : 0) + lft[i][j] + rig[i][j];
            long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
            dp[0][i][j] = max({dp[0][i][j], A, B});
            dp[1][i][j] = max({dp[1][i][j], A, B});
            if (i <= 3) continue;
            dp[0][i][j] = max(dp[0][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
            dp[1][i][j] = max(dp[1][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
        }
        for (int j = 0; j < ind[i].size(); j++)
        {
            dp[1][i][j] = max(dp[1][i][j], dp[0][i][j]);
            mx[i] = max({mx[i], dp[0][i][j], dp[1][i][j]});
        }
        for (int j = 0; j < ind[i].size(); j++) 
        {
            pre[0][i].push_back(max((pre[0][i].empty() ? 0LL : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
            pre[1][i].push_back(max((pre[1][i].empty() ? 0LL : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
        }
        suf[0][i].assign(ind[i].size(), 0);
        suf[1][i].assign(ind[i].size(), 0);
        for (int j = (int)ind[i].size() - 1; j >= 0; j--)
        {
            if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
            suf[0][i][j] = max(suf[0][i][j], dp[1][i][j]);
            suf[1][i][j] = max(suf[1][i][j], max(dp[0][i][j], dp[1][i][j]));
        }
    }
    long long ans = 0;
    for (int i = 1; i <= N; i++) 
    {
        for (long long &j : dp[0][i]) ans = max(ans, j);
        for (long long &j : dp[1][i]) ans = max(ans, j);
    }
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
      |                    ~~~^~~~~~~~~~~~~~~
fish.cpp:49:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:54:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:55:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:57:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
      |                 ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:60:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:62:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
      |                            ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:74:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
      |                 ~~~~~~^~~~~~~~~~~~~~~

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