oj.uz

Submission #1057397

# Submission time Handle Problem Language Result Execution time Memory
1057397 2024-08-13T18:43:31 Z aykhn Catfish Farm (IOI22_fish) C++17
20 / 100
 221 ms 164804 KB 
#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() ? 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 76088 KB Output is correct
2 Correct 65 ms 81032 KB Output is correct
3 Correct 11 ms 52060 KB Output is correct
4 Correct 8 ms 52108 KB Output is correct
5 Incorrect 221 ms 164804 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 105 ms 103504 KB Output is correct
3 Correct 133 ms 127364 KB Output is correct
4 Correct 61 ms 76084 KB Output is correct
5 Correct 66 ms 80872 KB Output is correct
6 Correct 7 ms 52060 KB Output is correct
7 Correct 8 ms 52060 KB Output is correct
8 Correct 8 ms 51880 KB Output is correct
9 Correct 7 ms 51884 KB Output is correct
10 Correct 8 ms 52060 KB Output is correct
11 Correct 8 ms 52060 KB Output is correct
12 Correct 58 ms 85280 KB Output is correct
13 Correct 71 ms 90352 KB Output is correct
14 Correct 53 ms 77736 KB Output is correct
15 Correct 68 ms 81520 KB Output is correct
16 Correct 63 ms 78500 KB Output is correct
17 Correct 67 ms 81356 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 52060 KB Output is correct
2 Correct 8 ms 51864 KB Output is correct
3 Incorrect 61 ms 79720 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52060 KB Output is correct
4 Correct 6 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 7 ms 52056 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 6 ms 52116 KB Output is correct
9 Correct 7 ms 52140 KB Output is correct
10 Correct 9 ms 53000 KB Output is correct
11 Correct 9 ms 52460 KB Output is correct
12 Correct 8 ms 52568 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 9 ms 52572 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52060 KB Output is correct
4 Correct 6 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 7 ms 52056 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 6 ms 52116 KB Output is correct
9 Correct 7 ms 52140 KB Output is correct
10 Correct 9 ms 53000 KB Output is correct
11 Correct 9 ms 52460 KB Output is correct
12 Correct 8 ms 52568 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 9 ms 52572 KB Output is correct
15 Correct 7 ms 52060 KB Output is correct
16 Incorrect 8 ms 52828 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '314050587306'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52060 KB Output is correct
4 Correct 6 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 7 ms 52056 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 6 ms 52116 KB Output is correct
9 Correct 7 ms 52140 KB Output is correct
10 Correct 9 ms 53000 KB Output is correct
11 Correct 9 ms 52460 KB Output is correct
12 Correct 8 ms 52568 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 9 ms 52572 KB Output is correct
15 Correct 7 ms 52060 KB Output is correct
16 Incorrect 8 ms 52828 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '314050587306'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 52060 KB Output is correct
2 Correct 8 ms 51864 KB Output is correct
3 Incorrect 61 ms 79720 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 76088 KB Output is correct
2 Correct 65 ms 81032 KB Output is correct
3 Correct 11 ms 52060 KB Output is correct
4 Correct 8 ms 52108 KB Output is correct
5 Incorrect 221 ms 164804 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -