oj.uz

Submission #1057369

# Submission time Handle Problem Language Result Execution time Memory
1057369 2024-08-13T18:26:29 Z aykhn Catfish Farm (IOI22_fish) C++17
20 / 100
 133 ms 116288 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);
        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:34: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]
   34 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:39: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]
   39 |             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:40: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]
   40 |             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: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 (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
      |                    ~~~^~~~~~~~~~~~~~~
fish.cpp:47: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]
   47 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:52: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]
   52 |             while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:53: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]
   53 |             while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:55: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]
   55 |             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:57: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]
   57 |             while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:58: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]
   58 |             while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:60: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]
   60 |             long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
      |                            ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:67: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]
   67 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:72: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]
   72 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63928 KB Output is correct
2 Correct 40 ms 66072 KB Output is correct
3 Correct 9 ms 52060 KB Output is correct
4 Correct 8 ms 52112 KB Output is correct
5 Incorrect 133 ms 116288 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 10 ms 52056 KB Output is correct
2 Correct 70 ms 80660 KB Output is correct
3 Correct 112 ms 85924 KB Output is correct
4 Correct 34 ms 63924 KB Output is correct
5 Correct 43 ms 65988 KB Output is correct
6 Correct 7 ms 52060 KB Output is correct
7 Correct 8 ms 52112 KB Output is correct
8 Correct 7 ms 52060 KB Output is correct
9 Correct 8 ms 52060 KB Output is correct
10 Correct 8 ms 52056 KB Output is correct
11 Correct 7 ms 52100 KB Output is correct
12 Correct 42 ms 71060 KB Output is correct
13 Correct 50 ms 74384 KB Output is correct
14 Correct 39 ms 66568 KB Output is correct
15 Correct 42 ms 67380 KB Output is correct
16 Correct 37 ms 66372 KB Output is correct
17 Correct 42 ms 68744 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 51880 KB Output is correct
2 Correct 7 ms 52108 KB Output is correct
3 Incorrect 86 ms 73812 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 8 ms 52056 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 7 ms 52112 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52112 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 7 ms 51912 KB Output is correct
9 Correct 7 ms 52168 KB Output is correct
10 Correct 9 ms 52572 KB Output is correct
11 Correct 8 ms 52124 KB Output is correct
12 Correct 8 ms 52316 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 7 ms 52312 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 7 ms 52112 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52112 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 7 ms 51912 KB Output is correct
9 Correct 7 ms 52168 KB Output is correct
10 Correct 9 ms 52572 KB Output is correct
11 Correct 8 ms 52124 KB Output is correct
12 Correct 8 ms 52316 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 7 ms 52312 KB Output is correct
15 Correct 7 ms 52148 KB Output is correct
16 Incorrect 9 ms 52408 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 8 ms 52056 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 7 ms 52112 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52112 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 7 ms 52060 KB Output is correct
8 Correct 7 ms 51912 KB Output is correct
9 Correct 7 ms 52168 KB Output is correct
10 Correct 9 ms 52572 KB Output is correct
11 Correct 8 ms 52124 KB Output is correct
12 Correct 8 ms 52316 KB Output is correct
13 Correct 7 ms 52168 KB Output is correct
14 Correct 7 ms 52312 KB Output is correct
15 Correct 7 ms 52148 KB Output is correct
16 Incorrect 9 ms 52408 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 9 ms 51880 KB Output is correct
2 Correct 7 ms 52108 KB Output is correct
3 Incorrect 86 ms 73812 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 34 ms 63928 KB Output is correct
2 Correct 40 ms 66072 KB Output is correct
3 Correct 9 ms 52060 KB Output is correct
4 Correct 8 ms 52112 KB Output is correct
5 Incorrect 133 ms 116288 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -