oj.uz

답안 #705220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
705220 2023-03-03T15:44:58 Z danikoynov 메기 농장 (IOI22_fish) C++17
9 / 100
 1000 ms 837832 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)
{
    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])
            {
                so_far = max(so_far, dp[i - 1][to][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]);
                to --;
            }
            dp[i][j][0] = max(dp[i][j][0], so_far);
        }


        if (i > 1)
        {

            so_far = 0;
            to = 0;
            for (int j = 1; 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]), 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 <= 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 < 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:88: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]
   88 |         for (int i = 0; i < col[0].size(); i ++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:93: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]
   93 |             while(to < col[1].size() && col[1][to].first <= col[0][i].first)
      |                   ~~~^~~~~~~~~~~~~~~
fish.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int j = 0; j < state[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int j = 0; j < state[1].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int j = 0; j < state[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:141: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]
  141 |             while(to < state[i - 1].size() && state[i - 1][to] <= state[i][j])
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             if (j + 1 < state[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:169:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |             for (int j = 1; j < state[i].size(); j ++)
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:171: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]
  171 |                 while(to < state[i - 2].size() && state[i - 2][to] <= state[i][j])
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:201:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for (int j = 0; j < state[N - 1].size(); j ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 42624 KB Output is correct
2 Correct 110 ms 46632 KB Output is correct
3 Correct 37 ms 38608 KB Output is correct
4 Correct 39 ms 38608 KB Output is correct
5 Correct 461 ms 78688 KB Output is correct
6 Correct 568 ms 75012 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18260 KB Output is correct
2 Correct 156 ms 52240 KB Output is correct
3 Correct 223 ms 60176 KB Output is correct
4 Correct 85 ms 42688 KB Output is correct
5 Correct 109 ms 46744 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 9 ms 18260 KB Output is correct
8 Correct 10 ms 18260 KB Output is correct
9 Correct 10 ms 18312 KB Output is correct
10 Correct 43 ms 38548 KB Output is correct
11 Correct 39 ms 38532 KB Output is correct
12 Correct 100 ms 46132 KB Output is correct
13 Correct 125 ms 51484 KB Output is correct
14 Correct 97 ms 44364 KB Output is correct
15 Correct 115 ms 48380 KB Output is correct
16 Correct 94 ms 44484 KB Output is correct
17 Correct 106 ms 48300 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 38592 KB Output is correct
2 Execution timed out 1124 ms 837832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 18216 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 18216 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 18216 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 38592 KB Output is correct
2 Execution timed out 1124 ms 837832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 42624 KB Output is correct
2 Correct 110 ms 46632 KB Output is correct
3 Correct 37 ms 38608 KB Output is correct
4 Correct 39 ms 38608 KB Output is correct
5 Correct 461 ms 78688 KB Output is correct
6 Correct 568 ms 75012 KB Output is correct
7 Correct 10 ms 18260 KB Output is correct
8 Correct 156 ms 52240 KB Output is correct
9 Correct 223 ms 60176 KB Output is correct
10 Correct 85 ms 42688 KB Output is correct
11 Correct 109 ms 46744 KB Output is correct
12 Correct 10 ms 18260 KB Output is correct
13 Correct 9 ms 18260 KB Output is correct
14 Correct 10 ms 18260 KB Output is correct
15 Correct 10 ms 18312 KB Output is correct
16 Correct 43 ms 38548 KB Output is correct
17 Correct 39 ms 38532 KB Output is correct
18 Correct 100 ms 46132 KB Output is correct
19 Correct 125 ms 51484 KB Output is correct
20 Correct 97 ms 44364 KB Output is correct
21 Correct 115 ms 48380 KB Output is correct
22 Correct 94 ms 44484 KB Output is correct
23 Correct 106 ms 48300 KB Output is correct
24 Correct 38 ms 38592 KB Output is correct
25 Execution timed out 1124 ms 837832 KB Time limit exceeded
26 Halted 0 ms 0 KB -