oj.uz

Submission #705213

# Submission time Handle Problem Language Result Execution time Memory
705213 2023-03-03T15:16:08 Z danikoynov Catfish Farm (IOI22_fish) C++17
61 / 100
 795 ms 333544 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];
 set < int >  state_set[maxn];
ll dp[smalln][smalln][2];
ll val[smalln][smalln], pref[smalln][smalln];

ll get_sum(int col, int left, int right)
{
    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);
    }

    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 j = 0; j <= N; j ++)
        dp[1][j][0] = dp[1][j][1] = 0;

    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 = 1; i < N; i ++)
    {

        dp[i][0][1] = dp[i - 1][0][1];
        for (int j = 1; j <= N; j ++)
        {
            dp[i][j][1] = max(dp[i][j - 1][1] + val[i - 1][j - 1], dp[i - 1][j][1]);
        }
        dp[i][N][0] = max(dp[i - 1][N][0], dp[i - 1][N][1]);
        for (int j = N - 1; j >= 0; j --)
        {
            dp[i][j][0] = max(dp[i][j + 1][0] + val[i][j], max(dp[i - 1][j][0], dp[i - 1][j][1]));
        }

        if (i > 1)
        {

            ll best = max(dp[i - 2][0][0], dp[i - 2][0][1]);
            for (int j = 1; j <= N; j ++)
            {
                dp[i][j][1] = max(best + get_sum(i - 1, 0, j - 1), dp[i][j][1]);
                best = max(best, max(dp[i - 2][j][0], dp[i - 2][j][1]));
            }
            best = max(dp[i - 2][N][0], dp[i - 2][N][1]) + get_sum(i - 1, 0, N - 1);
            for (int j = N; j > 0; j --)
            {
                dp[i][j][1] = max(best, dp[i][j][1]);
                best = max(best, max(dp[i - 2][j][0], dp[i - 2][j][1]) + get_sum(i - 1, 0, j - 1));
            }
        }

        for (int j = 0; j <= N; j ++)
        {
            if (state_set[i].find(j) == state_set[i].end())
                dp[i][j][0] = dp[i][j][1] = 0;
            //else
              // cout << i << " " << j << " " << dp[i][j][0] << endl;
        }
    }

    /**cout << "-----------" << endl;
    for (int i = 0; i < N; i ++, cout << endl)
        for (int j = 0; j <= N; j ++)
        cout << dp[i][j][0] << " ";
    cout << "-----------" << endl;
    for (int i = 0; i < N; i ++, cout << endl)
        for (int j = 0; j <= N; j ++)
        cout << dp[i][j][1] << " ";*/
    ll ans = 0;
    for (int j = 0; j <= N; 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:86: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]
   86 |         for (int i = 0; i < col[0].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:91: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]
   91 |             while(to < col[1].size() && col[1][to].first <= col[0][i].first)
      |                   ~~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 27584 KB Output is correct
2 Correct 108 ms 30552 KB Output is correct
3 Correct 24 ms 22100 KB Output is correct
4 Correct 23 ms 22092 KB Output is correct
5 Correct 549 ms 62672 KB Output is correct
6 Correct 466 ms 64328 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 201 ms 38388 KB Output is correct
3 Correct 297 ms 43772 KB Output is correct
4 Correct 83 ms 27592 KB Output is correct
5 Correct 96 ms 30360 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 24 ms 22160 KB Output is correct
11 Correct 28 ms 22112 KB Output is correct
12 Correct 111 ms 31752 KB Output is correct
13 Correct 149 ms 35484 KB Output is correct
14 Correct 97 ms 29656 KB Output is correct
15 Correct 126 ms 31900 KB Output is correct
16 Correct 99 ms 29632 KB Output is correct
17 Correct 111 ms 31844 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22236 KB Output is correct
2 Runtime error 42 ms 44844 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9704 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9740 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 15700 KB Output is correct
11 Correct 8 ms 12136 KB Output is correct
12 Correct 9 ms 15592 KB Output is correct
13 Correct 7 ms 10724 KB Output is correct
14 Correct 9 ms 15572 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9704 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9740 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 15700 KB Output is correct
11 Correct 8 ms 12136 KB Output is correct
12 Correct 9 ms 15592 KB Output is correct
13 Correct 7 ms 10724 KB Output is correct
14 Correct 9 ms 15572 KB Output is correct
15 Correct 9 ms 15444 KB Output is correct
16 Correct 7 ms 10836 KB Output is correct
17 Correct 48 ms 20356 KB Output is correct
18 Correct 40 ms 19760 KB Output is correct
19 Correct 42 ms 20420 KB Output is correct
20 Correct 39 ms 19976 KB Output is correct
21 Correct 40 ms 19996 KB Output is correct
22 Correct 78 ms 24356 KB Output is correct
23 Correct 17 ms 17400 KB Output is correct
24 Correct 34 ms 19880 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 16 ms 16852 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9704 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 7 ms 9740 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 15700 KB Output is correct
11 Correct 8 ms 12136 KB Output is correct
12 Correct 9 ms 15592 KB Output is correct
13 Correct 7 ms 10724 KB Output is correct
14 Correct 9 ms 15572 KB Output is correct
15 Correct 9 ms 15444 KB Output is correct
16 Correct 7 ms 10836 KB Output is correct
17 Correct 48 ms 20356 KB Output is correct
18 Correct 40 ms 19760 KB Output is correct
19 Correct 42 ms 20420 KB Output is correct
20 Correct 39 ms 19976 KB Output is correct
21 Correct 40 ms 19996 KB Output is correct
22 Correct 78 ms 24356 KB Output is correct
23 Correct 17 ms 17400 KB Output is correct
24 Correct 34 ms 19880 KB Output is correct
25 Correct 10 ms 15572 KB Output is correct
26 Correct 16 ms 16852 KB Output is correct
27 Correct 207 ms 234576 KB Output is correct
28 Correct 257 ms 54352 KB Output is correct
29 Correct 671 ms 259784 KB Output is correct
30 Correct 759 ms 308640 KB Output is correct
31 Correct 781 ms 309096 KB Output is correct
32 Correct 338 ms 53508 KB Output is correct
33 Correct 793 ms 333520 KB Output is correct
34 Correct 795 ms 333544 KB Output is correct
35 Correct 368 ms 251644 KB Output is correct
36 Correct 749 ms 277052 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22236 KB Output is correct
2 Runtime error 42 ms 44844 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 27584 KB Output is correct
2 Correct 108 ms 30552 KB Output is correct
3 Correct 24 ms 22100 KB Output is correct
4 Correct 23 ms 22092 KB Output is correct
5 Correct 549 ms 62672 KB Output is correct
6 Correct 466 ms 64328 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 201 ms 38388 KB Output is correct
9 Correct 297 ms 43772 KB Output is correct
10 Correct 83 ms 27592 KB Output is correct
11 Correct 96 ms 30360 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 24 ms 22160 KB Output is correct
17 Correct 28 ms 22112 KB Output is correct
18 Correct 111 ms 31752 KB Output is correct
19 Correct 149 ms 35484 KB Output is correct
20 Correct 97 ms 29656 KB Output is correct
21 Correct 126 ms 31900 KB Output is correct
22 Correct 99 ms 29632 KB Output is correct
23 Correct 111 ms 31844 KB Output is correct
24 Correct 26 ms 22236 KB Output is correct
25 Runtime error 42 ms 44844 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -