oj.uz

Submission #705167

# Submission time Handle Problem Language Result Execution time Memory
705167 2023-03-03T13:20:41 Z danikoynov Catfish Farm (IOI22_fish) C++17
44 / 100
 107 ms 13980 KB 
#include "fish.h"

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

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

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]));
        }
        for (int j = 0; j <= N; j ++)
        {
            /**for (int len = 0; len < j; len ++)
            {
                //cout << i << " " << j << " " << len << " " << get_sum(i - 1, len, j - 1) << endl;
                //cout << pref[i - 1][j - 1] << endl;
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][len][1] + get_sum(i - 1, len, j - 1));
            }*/

            /**dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1]);
            dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][0]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][0]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][1]);*/

            /**for (int len = j + 1; len <= N; len ++)
            {
                dp[i][j][0] = max(dp[i][j][0], max(dp[i - 1][len][0], dp[i - 1][len][1]) + get_sum(i, j, len - 1));
            }*/

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

    /**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 39 ms 6128 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 105 ms 12304 KB Output is correct
6 Correct 107 ms 13980 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 62 ms 8036 KB Output is correct
3 Correct 79 ms 9220 KB Output is correct
4 Correct 30 ms 5708 KB Output is correct
5 Correct 40 ms 6156 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 29 ms 5708 KB Output is correct
13 Correct 46 ms 6120 KB Output is correct
14 Correct 37 ms 5432 KB Output is correct
15 Correct 33 ms 5764 KB Output is correct
16 Correct 30 ms 5544 KB Output is correct
17 Correct 41 ms 5760 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 4 ms 5076 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 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 9 ms 4052 KB Output is correct
10 Correct 68 ms 5620 KB Output is correct
11 Correct 9 ms 4100 KB Output is correct
12 Correct 58 ms 5544 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 54 ms 5452 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 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 9 ms 4052 KB Output is correct
10 Correct 68 ms 5620 KB Output is correct
11 Correct 9 ms 4100 KB Output is correct
12 Correct 58 ms 5544 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 54 ms 5452 KB Output is correct
15 Correct 54 ms 5484 KB Output is correct
16 Correct 3 ms 3284 KB Output is correct
17 Correct 66 ms 6780 KB Output is correct
18 Correct 67 ms 6980 KB Output is correct
19 Correct 66 ms 7304 KB Output is correct
20 Correct 77 ms 7228 KB Output is correct
21 Correct 73 ms 7296 KB Output is correct
22 Correct 80 ms 9020 KB Output is correct
23 Correct 57 ms 5768 KB Output is correct
24 Correct 62 ms 6540 KB Output is correct
25 Correct 53 ms 5580 KB Output is correct
26 Correct 61 ms 5760 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 9 ms 4052 KB Output is correct
10 Correct 68 ms 5620 KB Output is correct
11 Correct 9 ms 4100 KB Output is correct
12 Correct 58 ms 5544 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 54 ms 5452 KB Output is correct
15 Correct 54 ms 5484 KB Output is correct
16 Correct 3 ms 3284 KB Output is correct
17 Correct 66 ms 6780 KB Output is correct
18 Correct 67 ms 6980 KB Output is correct
19 Correct 66 ms 7304 KB Output is correct
20 Correct 77 ms 7228 KB Output is correct
21 Correct 73 ms 7296 KB Output is correct
22 Correct 80 ms 9020 KB Output is correct
23 Correct 57 ms 5768 KB Output is correct
24 Correct 62 ms 6540 KB Output is correct
25 Correct 53 ms 5580 KB Output is correct
26 Correct 61 ms 5760 KB Output is correct
27 Runtime error 5 ms 5460 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Runtime error 4 ms 5076 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 39 ms 6128 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 105 ms 12304 KB Output is correct
6 Correct 107 ms 13980 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 62 ms 8036 KB Output is correct
9 Correct 79 ms 9220 KB Output is correct
10 Correct 30 ms 5708 KB Output is correct
11 Correct 40 ms 6156 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 29 ms 5708 KB Output is correct
19 Correct 46 ms 6120 KB Output is correct
20 Correct 37 ms 5432 KB Output is correct
21 Correct 33 ms 5764 KB Output is correct
22 Correct 30 ms 5544 KB Output is correct
23 Correct 41 ms 5760 KB Output is correct
24 Correct 2 ms 2644 KB Output is correct
25 Runtime error 4 ms 5076 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -