oj.uz

Submission #705229

# Submission time Handle Problem Language Result Execution time Memory
705229 2023-03-03T16:02:54 Z danikoynov Catfish Farm (IOI22_fish) C++17
9 / 100
 556 ms 71420 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];
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);
        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 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 ++)
            {
                best = max(best, max(dp[i - 2][j][0], dp[i - 2][j][1]));
                dp[i][j][1] = max(best + get_sum(i - 1, 0, j - 1), dp[i][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 --)
            {
                best = max(best, max(dp[i - 2][j][0], dp[i - 2][j][1]) + get_sum(i - 1, 0, j - 1));
                dp[i][j][1] = max(best, dp[i][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:87: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]
   87 |         for (int i = 0; i < col[0].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:92: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]
   92 |             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 89 ms 35236 KB Output is correct
2 Correct 104 ms 39260 KB Output is correct
3 Correct 41 ms 30784 KB Output is correct
4 Correct 36 ms 30796 KB Output is correct
5 Correct 433 ms 71420 KB Output is correct
6 Correct 556 ms 67764 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 159 ms 44940 KB Output is correct
3 Correct 209 ms 52392 KB Output is correct
4 Correct 92 ms 35204 KB Output is correct
5 Correct 115 ms 39204 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 7 ms 10452 KB Output is correct
9 Correct 6 ms 10364 KB Output is correct
10 Correct 40 ms 30796 KB Output is correct
11 Correct 34 ms 30716 KB Output is correct
12 Correct 101 ms 38784 KB Output is correct
13 Correct 143 ms 44136 KB Output is correct
14 Correct 104 ms 37096 KB Output is correct
15 Correct 105 ms 40824 KB Output is correct
16 Correct 91 ms 37044 KB Output is correct
17 Correct 111 ms 40924 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 30796 KB Output is correct
2 Runtime error 65 ms 62248 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10416 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10388 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Incorrect 9 ms 12884 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10416 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10388 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Incorrect 9 ms 12884 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10416 KB Output is correct
2 Correct 6 ms 10580 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10388 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Incorrect 9 ms 12884 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '7818664569'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 30796 KB Output is correct
2 Runtime error 65 ms 62248 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 89 ms 35236 KB Output is correct
2 Correct 104 ms 39260 KB Output is correct
3 Correct 41 ms 30784 KB Output is correct
4 Correct 36 ms 30796 KB Output is correct
5 Correct 433 ms 71420 KB Output is correct
6 Correct 556 ms 67764 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 159 ms 44940 KB Output is correct
9 Correct 209 ms 52392 KB Output is correct
10 Correct 92 ms 35204 KB Output is correct
11 Correct 115 ms 39204 KB Output is correct
12 Correct 6 ms 10452 KB Output is correct
13 Correct 6 ms 10452 KB Output is correct
14 Correct 7 ms 10452 KB Output is correct
15 Correct 6 ms 10364 KB Output is correct
16 Correct 40 ms 30796 KB Output is correct
17 Correct 34 ms 30716 KB Output is correct
18 Correct 101 ms 38784 KB Output is correct
19 Correct 143 ms 44136 KB Output is correct
20 Correct 104 ms 37096 KB Output is correct
21 Correct 105 ms 40824 KB Output is correct
22 Correct 91 ms 37044 KB Output is correct
23 Correct 111 ms 40924 KB Output is correct
24 Correct 37 ms 30796 KB Output is correct
25 Runtime error 65 ms 62248 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -