oj.uz

Submission #1057386

# Submission time Handle Problem Language Result Execution time Memory
1057386 2024-08-13T18:35:43 Z aykhn Catfish Farm (IOI22_fish) C++17
20 / 100
 200 ms 164176 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() ? 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() ? 0 : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
            pre[1][i].push_back(max((pre[1][i].empty() ? 0 : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
        }
        for (int j = (int)ind[i].size() - 1; j >= 0; j--)
        {
            suf[0][i].push_back(max((suf[0][i].empty() ? 0 : suf[0][i].back()), dp[1][i][j]));
            suf[1][i].push_back(max((suf[1][i].empty() ? 0 : suf[0][i].back()), max(dp[0][i][j], dp[1][i][j])));
        }
        reverse(suf[0][i].begin(), suf[0][i].end());
        reverse(suf[1][i].begin(), suf[1][i].end());
    }
    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++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 76764 KB Output is correct
2 Correct 77 ms 81852 KB Output is correct
3 Correct 7 ms 52056 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Incorrect 200 ms 164176 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 8 ms 52056 KB Output is correct
2 Correct 115 ms 104772 KB Output is correct
3 Correct 126 ms 130288 KB Output is correct
4 Correct 54 ms 76728 KB Output is correct
5 Correct 62 ms 81844 KB Output is correct
6 Correct 7 ms 52060 KB Output is correct
7 Correct 7 ms 52104 KB Output is correct
8 Correct 7 ms 52056 KB Output is correct
9 Correct 8 ms 52060 KB Output is correct
10 Correct 7 ms 52060 KB Output is correct
11 Correct 8 ms 51888 KB Output is correct
12 Correct 62 ms 84608 KB Output is correct
13 Correct 73 ms 91040 KB Output is correct
14 Correct 56 ms 78504 KB Output is correct
15 Correct 66 ms 83216 KB Output is correct
16 Correct 58 ms 78780 KB Output is correct
17 Correct 64 ms 81972 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 51920 KB Output is correct
3 Incorrect 66 ms 81164 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 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 7 ms 52116 KB Output is correct
4 Correct 7 ms 52100 KB Output is correct
5 Correct 7 ms 52056 KB Output is correct
6 Correct 9 ms 52060 KB Output is correct
7 Correct 8 ms 52116 KB Output is correct
8 Correct 7 ms 52096 KB Output is correct
9 Correct 8 ms 52316 KB Output is correct
10 Correct 10 ms 52828 KB Output is correct
11 Correct 8 ms 52372 KB Output is correct
12 Correct 8 ms 52736 KB Output is correct
13 Correct 7 ms 52116 KB Output is correct
14 Correct 8 ms 52568 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 7 ms 52116 KB Output is correct
4 Correct 7 ms 52100 KB Output is correct
5 Correct 7 ms 52056 KB Output is correct
6 Correct 9 ms 52060 KB Output is correct
7 Correct 8 ms 52116 KB Output is correct
8 Correct 7 ms 52096 KB Output is correct
9 Correct 8 ms 52316 KB Output is correct
10 Correct 10 ms 52828 KB Output is correct
11 Correct 8 ms 52372 KB Output is correct
12 Correct 8 ms 52736 KB Output is correct
13 Correct 7 ms 52116 KB Output is correct
14 Correct 8 ms 52568 KB Output is correct
15 Correct 9 ms 52060 KB Output is correct
16 Incorrect 8 ms 52912 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 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 7 ms 52116 KB Output is correct
4 Correct 7 ms 52100 KB Output is correct
5 Correct 7 ms 52056 KB Output is correct
6 Correct 9 ms 52060 KB Output is correct
7 Correct 8 ms 52116 KB Output is correct
8 Correct 7 ms 52096 KB Output is correct
9 Correct 8 ms 52316 KB Output is correct
10 Correct 10 ms 52828 KB Output is correct
11 Correct 8 ms 52372 KB Output is correct
12 Correct 8 ms 52736 KB Output is correct
13 Correct 7 ms 52116 KB Output is correct
14 Correct 8 ms 52568 KB Output is correct
15 Correct 9 ms 52060 KB Output is correct
16 Incorrect 8 ms 52912 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 7 ms 52060 KB Output is correct
2 Correct 7 ms 51920 KB Output is correct
3 Incorrect 66 ms 81164 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 58 ms 76764 KB Output is correct
2 Correct 77 ms 81852 KB Output is correct
3 Correct 7 ms 52056 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Incorrect 200 ms 164176 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -