oj.uz

답안 #705226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705226 2023-03-03T15:55:42 Z danikoynov 메기 농장 (IOI22_fish) C++17
9 / 100
 1000 ms 790204 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])
            {
                so_far = max(so_far, dp[i - 1][to][0] + 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:172:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |             for (int j = 0; j < state[i].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:174: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]
  174 |                 while(to < state[i - 2].size() && state[i - 2][to] <= state[i][j])
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:204:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     for (int j = 0; j < state[N - 1].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 43344 KB Output is correct
2 Correct 104 ms 47500 KB Output is correct
3 Correct 48 ms 38668 KB Output is correct
4 Correct 53 ms 38532 KB Output is correct
5 Correct 473 ms 79336 KB Output is correct
6 Correct 603 ms 75824 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 164 ms 53148 KB Output is correct
3 Correct 220 ms 60900 KB Output is correct
4 Correct 120 ms 43280 KB Output is correct
5 Correct 107 ms 47492 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 11 ms 18316 KB Output is correct
8 Correct 10 ms 18252 KB Output is correct
9 Correct 10 ms 18316 KB Output is correct
10 Correct 38 ms 38648 KB Output is correct
11 Correct 41 ms 38532 KB Output is correct
12 Correct 141 ms 46940 KB Output is correct
13 Correct 133 ms 52384 KB Output is correct
14 Correct 96 ms 44984 KB Output is correct
15 Correct 112 ms 49100 KB Output is correct
16 Correct 111 ms 45120 KB Output is correct
17 Correct 120 ms 49044 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38616 KB Output is correct
2 Execution timed out 1126 ms 790204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18344 KB Output is correct
3 Correct 11 ms 18228 KB Output is correct
4 Correct 11 ms 18312 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 16 ms 18316 KB Output is correct
7 Correct 13 ms 18212 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Incorrect 14 ms 20232 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18344 KB Output is correct
3 Correct 11 ms 18228 KB Output is correct
4 Correct 11 ms 18312 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 16 ms 18316 KB Output is correct
7 Correct 13 ms 18212 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Incorrect 14 ms 20232 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 11 ms 18344 KB Output is correct
3 Correct 11 ms 18228 KB Output is correct
4 Correct 11 ms 18312 KB Output is correct
5 Correct 13 ms 18316 KB Output is correct
6 Correct 16 ms 18316 KB Output is correct
7 Correct 13 ms 18212 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Incorrect 14 ms 20232 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '216366270048'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 38616 KB Output is correct
2 Execution timed out 1126 ms 790204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 43344 KB Output is correct
2 Correct 104 ms 47500 KB Output is correct
3 Correct 48 ms 38668 KB Output is correct
4 Correct 53 ms 38532 KB Output is correct
5 Correct 473 ms 79336 KB Output is correct
6 Correct 603 ms 75824 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 164 ms 53148 KB Output is correct
9 Correct 220 ms 60900 KB Output is correct
10 Correct 120 ms 43280 KB Output is correct
11 Correct 107 ms 47492 KB Output is correct
12 Correct 11 ms 18260 KB Output is correct
13 Correct 11 ms 18316 KB Output is correct
14 Correct 10 ms 18252 KB Output is correct
15 Correct 10 ms 18316 KB Output is correct
16 Correct 38 ms 38648 KB Output is correct
17 Correct 41 ms 38532 KB Output is correct
18 Correct 141 ms 46940 KB Output is correct
19 Correct 133 ms 52384 KB Output is correct
20 Correct 96 ms 44984 KB Output is correct
21 Correct 112 ms 49100 KB Output is correct
22 Correct 111 ms 45120 KB Output is correct
23 Correct 120 ms 49044 KB Output is correct
24 Correct 37 ms 38616 KB Output is correct
25 Execution timed out 1126 ms 790204 KB Time limit exceeded
26 Halted 0 ms 0 KB -