oj.uz

Submission #705206

# Submission time Handle Problem Language Result Execution time Memory
705206 2023-03-03T15:05:45 Z danikoynov Catfish Farm (IOI22_fish) C++17
61 / 100
 322 ms 296184 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];
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());

    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 = 1; j < N; j ++)
        {
            if ((i == 0 || val[i - 1][j - 1] == 0) &&
                (i == N - 1 || val[i + 1][j - 1] == 0))
            {

                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:65: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]
   65 |         for (int i = 0; i < col[0].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:70: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]
   70 |             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 29 ms 5708 KB Output is correct
2 Correct 36 ms 6136 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 121 ms 12308 KB Output is correct
6 Correct 123 ms 13976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 64 ms 8048 KB Output is correct
3 Correct 74 ms 9088 KB Output is correct
4 Correct 29 ms 5652 KB Output is correct
5 Correct 38 ms 6092 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 29 ms 5708 KB Output is correct
13 Correct 38 ms 6136 KB Output is correct
14 Correct 32 ms 5420 KB Output is correct
15 Correct 34 ms 5764 KB Output is correct
16 Correct 30 ms 5564 KB Output is correct
17 Correct 33 ms 5752 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 8 ms 5152 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 6 ms 8528 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 5 ms 8428 KB Output is correct
13 Correct 2 ms 3680 KB Output is correct
14 Correct 5 ms 8404 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 6 ms 8528 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 5 ms 8428 KB Output is correct
13 Correct 2 ms 3680 KB Output is correct
14 Correct 5 ms 8404 KB Output is correct
15 Correct 5 ms 8420 KB Output is correct
16 Correct 3 ms 3668 KB Output is correct
17 Correct 20 ms 10184 KB Output is correct
18 Correct 21 ms 10244 KB Output is correct
19 Correct 19 ms 10572 KB Output is correct
20 Correct 20 ms 10636 KB Output is correct
21 Correct 19 ms 10532 KB Output is correct
22 Correct 33 ms 13056 KB Output is correct
23 Correct 8 ms 9452 KB Output is correct
24 Correct 15 ms 10212 KB Output is correct
25 Correct 5 ms 8428 KB Output is correct
26 Correct 8 ms 9064 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 4 ms 4928 KB Output is correct
10 Correct 6 ms 8528 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 5 ms 8428 KB Output is correct
13 Correct 2 ms 3680 KB Output is correct
14 Correct 5 ms 8404 KB Output is correct
15 Correct 5 ms 8420 KB Output is correct
16 Correct 3 ms 3668 KB Output is correct
17 Correct 20 ms 10184 KB Output is correct
18 Correct 21 ms 10244 KB Output is correct
19 Correct 19 ms 10572 KB Output is correct
20 Correct 20 ms 10636 KB Output is correct
21 Correct 19 ms 10532 KB Output is correct
22 Correct 33 ms 13056 KB Output is correct
23 Correct 8 ms 9452 KB Output is correct
24 Correct 15 ms 10212 KB Output is correct
25 Correct 5 ms 8428 KB Output is correct
26 Correct 8 ms 9064 KB Output is correct
27 Correct 173 ms 226932 KB Output is correct
28 Correct 89 ms 34100 KB Output is correct
29 Correct 273 ms 229040 KB Output is correct
30 Correct 284 ms 271312 KB Output is correct
31 Correct 302 ms 275776 KB Output is correct
32 Correct 114 ms 33464 KB Output is correct
33 Correct 322 ms 296184 KB Output is correct
34 Correct 299 ms 296172 KB Output is correct
35 Correct 218 ms 234396 KB Output is correct
36 Correct 276 ms 242732 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 8 ms 5152 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 29 ms 5708 KB Output is correct
2 Correct 36 ms 6136 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 121 ms 12308 KB Output is correct
6 Correct 123 ms 13976 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 64 ms 8048 KB Output is correct
9 Correct 74 ms 9088 KB Output is correct
10 Correct 29 ms 5652 KB Output is correct
11 Correct 38 ms 6092 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 1 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 29 ms 5708 KB Output is correct
19 Correct 38 ms 6136 KB Output is correct
20 Correct 32 ms 5420 KB Output is correct
21 Correct 34 ms 5764 KB Output is correct
22 Correct 30 ms 5564 KB Output is correct
23 Correct 33 ms 5752 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Runtime error 8 ms 5152 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -