Submission #1058549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058549		aykhn	Catfish Farm (IOI22_fish)	C++17	100 / 100	575 ms	380732 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];
*/
int A[9] = {0, 0, 0, -1, -1, -1, 1, 1, 1};
int B[9] = {0, -1, 1, 0, -1, 1, 0, -1, 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 = 1; i <= N; i++) ind[i] = {1};
    for (int i = 0; i < M; i++)
    {
        X[i]++, Y[i]++;
        for (int j = 0; j < 9; j++)
        {
            int x = X[i] + A[j], y = Y[i] + B[j];
            if (min(x, y) >= 1 && max(x, y) <= N)
            {
                ind[x].push_back(y);
            }
        }
        val[X[i]].push_back({Y[i], W[i]});
    }
    for (int i = 1; i <= N; i++)
    {
        sort(ind[i].begin(), ind[i].end());
        ind[i].resize(unique(ind[i].begin(), ind[i].end()) - ind[i].begin());
        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() ? 0LL : lft[i].back()));
            rig[i].push_back((rig[i].empty() ? 0LL : rig[i].back()));
            in[i].push_back((in[i].empty() ? 0LL : 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:50: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]
   50 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:55: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]
   55 |             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:56: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]
   56 |             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:57: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]
   57 |             while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
      |                    ~~~^~~~~~~~~~~~~~~
fish.cpp:64: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]
   64 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:69: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]
   69 |             while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:70: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]
   70 |             while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:72: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]
   72 |             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:74: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]
   74 |             while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:75: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]
   75 |             while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:77: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]
   77 |             long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
      |                            ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:84: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]
   84 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:89: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]
   89 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:98: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]
   98 |             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: 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