oj.uz

Submission #705232

# Submission time Handle Problem Language Result Execution time Memory
705232 2023-03-03T16:14:47 Z danikoynov Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 747740 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10, smalln = 3010;

vector < pair < int, int > > col[maxn];
vector < int > state[maxn];
 unordered_set < int >  state_set[maxn];
vector < vector < ll > > dp[maxn];
unordered_map < int, ll > val[maxn];
ll pref[smalln][smalln];

ll get_sum(int col, int left, int right)
{
    if (left > right)
        return 0;
    ll sum = pref[col][right];
    if (left > 0)
        sum = sum - pref[col][left - 1];
    return sum;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W)
{
    bool all_even = true, small_x = true;
    for (int i = 0; i < M; i ++)
    {
        if (X[i] % 2 != 0)
            all_even = false;
        if (X[i] > 1)
            small_x = false;
    }

    for (int i = 0; i < M; i ++)
    {
        col[X[i]].push_back({Y[i], W[i]});
    }

    for (int i = 0; i < N; i ++)
        sort(col[i].begin(), col[i].end());

    for (int i = 0; i < M; i ++)
    {
        if (X[i] != 0)
            state_set[X[i] - 1].insert(Y[i] + 1);
        if (X[i] != N - 1)
        state_set[X[i] + 1].insert(Y[i] + 1);
    }

    for (int i = 0; i < N; i ++)
    {
        state_set[i].insert(0);
        state_set[i].insert(N);
    }
    for (int i = 0; i < N; i ++)
    {
        for (auto it : state_set[i])
            state[i].push_back(it);
        sort(state[i].begin(), state[i].end());
    }

    if (all_even)
    {
        ll sum = 0;
        for (int i = 0; i < M; i ++)
            sum = sum + W[i];
        return sum;

    }
    else if (small_x)
    {

        ll zero = 0, one = 0;
        for (int i = 0; i < M; i ++)
        {
            if (X[i] == 0)
                zero += W[i];
            else
                one += W[i];
        }
        if (N == 2)
            return max(zero, one);

        int to = 0;
        ll cur = 0, ans = 0;
        for (int i = 0; i < col[0].size(); i ++)
        {
            if (cur + one > ans)
                ans = cur + one;
            cur += col[0][i].second;
            while(to < col[1].size() && col[1][to].first <= col[0][i].first)
            {
                one -= col[1][to].second;
                to ++;
            }
        }
        if (cur + one > ans)
            ans = cur + one;
        return ans;

    }

    for (int i = 0; i < M; i ++)
        val[X[i]][Y[i]] = W[i];

    /**for (int i = 0; i < N; i ++, cout << endl)
        for (int j = 0; j < N; j ++)
        cout << val[i][j] << " ";*/


    for (int i = 0; i < N; i ++)
    {
        pref[i][0] = val[i][0];
        for (int j = 1; j <= N; j ++)
        {
            pref[i][j] = pref[i][j - 1] + val[i][j];
        }
    }

    for (int i = 0; i < N; i ++)
    {
        dp[i].resize(state[i].size());
        for (int j = 0; j < state[i].size(); j ++)
        {
            dp[i][j].resize(2);
        }
    }

    for (int j = 0; j < state[1].size(); j ++)
        dp[1][j][0] = dp[1][j][1] = 0;
    for (int i = 1; i < N; i ++)
    {

        ll so_far = 0, to = 0;
        for (int j = 0; j < state[i].size(); j ++)
        {
            if (j > 0)
                dp[i][j][1] = dp[i][j - 1][1] + get_sum(i - 1, state[i][j - 1], state[i][j] - 1);
            while(to < state[i - 1].size() && state[i - 1][to] <= state[i][j])
            {
                ///cout << i << " " << j << " :: " << state[i - 1][to] << " " << state[i][j] << endl;
                so_far = max(so_far, dp[i - 1][to][1] + get_sum(i - 1, state[i - 1][to], state[i][j] - 1));
                to ++;
            }
            dp[i][j][1] = max(dp[i][j][1], so_far);
        }

        so_far = 0;
        to = (int)(state[i - 1].size()) - 1;
        for (int j = (int)(state[i].size()) - 1; j >= 0; j --)
        {
            if (j + 1 < state[i].size())
                dp[i][j][0] = dp[i][j + 1][0] + get_sum(i, state[i][j], state[i][j + 1] - 1);
            while(to >= 0 && state[i - 1][to] >= state[i][j])
            {
                ///cout << i << " " << j << " ::: " << to << endl;
                so_far = max(so_far, max(dp[i - 1][to][0], dp[i - 1][to][1]) + get_sum(i, state[i][j], state[i - 1][to] - 1));
                to --;
            }
            dp[i][j][0] = max(dp[i][j][0], so_far);
        }


        if (i > 1)
        {

            so_far = 0;
            to = 0;
            for (int j = 0; j < state[i].size(); j ++)
            {
                while(to < state[i - 2].size() && state[i - 2][to] <= state[i][j])
                {
                    so_far = max(so_far, max(dp[i - 2][to][0], dp[i - 2][to][1]));
                    to ++;
                }
                dp[i][j][1] = max(so_far + get_sum(i - 1, 0, state[i][j] - 1), dp[i][j][1]);
            }
            so_far = 0;
            to = (int)(state[i - 2].size()) - 1;
            for (int j = (int)(state[i].size()) - 1; j >= 0; j --)
            {
                while(to >= 0 && state[i - 2][to] >= state[i][j])
                {
                    so_far = max(so_far, max(dp[i - 2][to][0], dp[i - 2][to][1]) + get_sum(i - 1, 0, state[i - 2][to] - 1));
                    to --;
                }
                dp[i][j][1] = max(so_far, dp[i][j][1]);
            }
        }
    }

    /**cout << "-----------" << endl;
    for (int i = 0; i < N; i ++, cout << endl)
        for (int j = 0; j < state[i].size(); j ++)
        cout << dp[i][j][0] << " ";
    cout << "-----------" << endl;
    for (int i = 0; i < N; i ++, cout << endl)
        for (int j = 0; j < state[i].size(); j ++)
        cout << dp[i][j][1] << " ";*/
    ll ans = 0;
    for (int j = 0; j < state[N - 1].size(); j ++)
        for (int t = 0; t < 2; t ++)
            ans = max(ans, dp[N - 1][j][t]);


    return ans;

}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < col[0].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             while(to < col[1].size() && col[1][to].first <= col[0][i].first)
      |                   ~~~^~~~~~~~~~~~~~~
fish.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int j = 0; j < state[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int j = 0; j < state[1].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for (int j = 0; j < state[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:143:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             while(to < state[i - 1].size() && state[i - 1][to] <= state[i][j])
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             if (j + 1 < state[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:173:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             for (int j = 0; j < state[i].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:175:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |                 while(to < state[i - 2].size() && state[i - 2][to] <= state[i][j])
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:205:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |     for (int j = 0; j < state[N - 1].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 42632 KB Output is correct
2 Correct 122 ms 46580 KB Output is correct
3 Correct 51 ms 38584 KB Output is correct
4 Correct 52 ms 38612 KB Output is correct
5 Correct 495 ms 78632 KB Output is correct
6 Correct 546 ms 75292 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 163 ms 52296 KB Output is correct
3 Correct 213 ms 59480 KB Output is correct
4 Correct 99 ms 42668 KB Output is correct
5 Correct 114 ms 46588 KB Output is correct
6 Correct 10 ms 18316 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 12 ms 18312 KB Output is correct
10 Correct 53 ms 38652 KB Output is correct
11 Correct 53 ms 38648 KB Output is correct
12 Correct 114 ms 46216 KB Output is correct
13 Correct 135 ms 51444 KB Output is correct
14 Correct 103 ms 44436 KB Output is correct
15 Correct 115 ms 48184 KB Output is correct
16 Correct 110 ms 44412 KB Output is correct
17 Correct 128 ms 48184 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 38616 KB Output is correct
2 Execution timed out 1118 ms 747740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18196 KB Output is correct
4 Correct 11 ms 18308 KB Output is correct
5 Correct 11 ms 18272 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 11 ms 18244 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 17 ms 20180 KB Output is correct
10 Correct 21 ms 24652 KB Output is correct
11 Correct 13 ms 20228 KB Output is correct
12 Correct 21 ms 24676 KB Output is correct
13 Correct 14 ms 18852 KB Output is correct
14 Correct 21 ms 24548 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18196 KB Output is correct
4 Correct 11 ms 18308 KB Output is correct
5 Correct 11 ms 18272 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 11 ms 18244 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 17 ms 20180 KB Output is correct
10 Correct 21 ms 24652 KB Output is correct
11 Correct 13 ms 20228 KB Output is correct
12 Correct 21 ms 24676 KB Output is correct
13 Correct 14 ms 18852 KB Output is correct
14 Correct 21 ms 24548 KB Output is correct
15 Correct 21 ms 24456 KB Output is correct
16 Correct 14 ms 19336 KB Output is correct
17 Correct 56 ms 32804 KB Output is correct
18 Correct 58 ms 32264 KB Output is correct
19 Correct 61 ms 32460 KB Output is correct
20 Correct 56 ms 31596 KB Output is correct
21 Correct 53 ms 31556 KB Output is correct
22 Correct 86 ms 38844 KB Output is correct
23 Correct 30 ms 26580 KB Output is correct
24 Correct 53 ms 31104 KB Output is correct
25 Correct 23 ms 24596 KB Output is correct
26 Correct 33 ms 26276 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18260 KB Output is correct
3 Correct 11 ms 18196 KB Output is correct
4 Correct 11 ms 18308 KB Output is correct
5 Correct 11 ms 18272 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 11 ms 18244 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 17 ms 20180 KB Output is correct
10 Correct 21 ms 24652 KB Output is correct
11 Correct 13 ms 20228 KB Output is correct
12 Correct 21 ms 24676 KB Output is correct
13 Correct 14 ms 18852 KB Output is correct
14 Correct 21 ms 24548 KB Output is correct
15 Correct 21 ms 24456 KB Output is correct
16 Correct 14 ms 19336 KB Output is correct
17 Correct 56 ms 32804 KB Output is correct
18 Correct 58 ms 32264 KB Output is correct
19 Correct 61 ms 32460 KB Output is correct
20 Correct 56 ms 31596 KB Output is correct
21 Correct 53 ms 31556 KB Output is correct
22 Correct 86 ms 38844 KB Output is correct
23 Correct 30 ms 26580 KB Output is correct
24 Correct 53 ms 31104 KB Output is correct
25 Correct 23 ms 24596 KB Output is correct
26 Correct 33 ms 26276 KB Output is correct
27 Correct 740 ms 492172 KB Output is correct
28 Correct 313 ms 86604 KB Output is correct
29 Execution timed out 1073 ms 551932 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 38616 KB Output is correct
2 Execution timed out 1118 ms 747740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 42632 KB Output is correct
2 Correct 122 ms 46580 KB Output is correct
3 Correct 51 ms 38584 KB Output is correct
4 Correct 52 ms 38612 KB Output is correct
5 Correct 495 ms 78632 KB Output is correct
6 Correct 546 ms 75292 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 163 ms 52296 KB Output is correct
9 Correct 213 ms 59480 KB Output is correct
10 Correct 99 ms 42668 KB Output is correct
11 Correct 114 ms 46588 KB Output is correct
12 Correct 10 ms 18316 KB Output is correct
13 Correct 11 ms 18260 KB Output is correct
14 Correct 11 ms 18260 KB Output is correct
15 Correct 12 ms 18312 KB Output is correct
16 Correct 53 ms 38652 KB Output is correct
17 Correct 53 ms 38648 KB Output is correct
18 Correct 114 ms 46216 KB Output is correct
19 Correct 135 ms 51444 KB Output is correct
20 Correct 103 ms 44436 KB Output is correct
21 Correct 115 ms 48184 KB Output is correct
22 Correct 110 ms 44412 KB Output is correct
23 Correct 128 ms 48184 KB Output is correct
24 Correct 55 ms 38616 KB Output is correct
25 Execution timed out 1118 ms 747740 KB Time limit exceeded
26 Halted 0 ms 0 KB -