oj.uz

답안 #1057394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057394 2024-08-13T18:41:03 Z aykhn 메기 농장 (IOI22_fish) C++17
20 / 100
 202 ms 166192 KB 
#include "fish.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 2e5 + 5;


long long mx[MXN];
vector<long long> lft[MXN], rig[MXN], in[MXN];
vector<long long> pre[2][MXN], suf[2][MXN];
vector<long long> dp[2][MXN];
vector<long long> ind[MXN];
vector<array<long long, 2>> val[MXN];

/*
0 = len[i] < len[i + 1];
1 = len[i] > len[i + 1];
*/
long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) 
{
    for (int i = 0; i < M; i++)
    {
        if (X[i] >= 1) ind[X[i]].push_back(Y[i] + 1);
        if (X[i] + 2 <= N) ind[X[i] + 2].push_back(Y[i] + 1);
        ind[X[i] + 1].push_back(Y[i] + 1);
        if (Y[i]) ind[X[i] + 1].push_back(Y[i]);
        val[X[i] + 1].push_back({Y[i] + 1, W[i]});
    }
    for (int i = 1; i <= N; i++) sort(ind[i].begin(), ind[i].end()), sort(val[i].begin(), val[i].end());
    for (int i = 1; i <= N; i++) 
    {
        int k1 = 0, k2 = 0, k3 = 0;
        for (int j = 0; j < ind[i].size(); j++)
        {
            lft[i].push_back((lft[i].empty() ? 0 : lft[i].back()));
            rig[i].push_back((rig[i].empty() ? 0 : rig[i].back()));
            in[i].push_back((in[i].empty() ? 0 : in[i].back()));
            while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
            while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
            while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
        }
    }
    for (int i = 1; i <= N; i++)
    {
        int k1 = 0, k2 = 0, k3 = 0, k4 = 0;
        for (int j = 0; j < ind[i].size(); j++)
        {
            dp[0][i].push_back(lft[i][j] + rig[i][j]);
            dp[1][i].push_back(lft[i][j] + rig[i][j]);
            if (i <= 1) continue;
            while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
            while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
            if (k1 - 1 >= 0) dp[0][i][j] = max(dp[0][i][j], pre[0][i - 1][k1 - 1] + (lft[i][j] + rig[i][j]));
            if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
            if (i <= 2) continue;
            while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
            while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
            long long A = (k3 - 1 >= 0 ? pre[1][i - 2][k3 - 1] : 0) + lft[i][j] + rig[i][j];
            long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
            dp[0][i][j] = max({dp[0][i][j], A, B});
            dp[1][i][j] = max({dp[1][i][j], A, B});
            if (i <= 3) continue;
            dp[0][i][j] = max(dp[0][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
            dp[1][i][j] = max(dp[1][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
        }
        for (int j = 0; j < ind[i].size(); j++)
        {
            dp[1][i][j] = max(dp[1][i][j], dp[0][i][j]);
            mx[i] = max({mx[i], dp[0][i][j], dp[1][i][j]});
        }
        for (int j = 0; j < ind[i].size(); j++) 
        {
            pre[0][i].push_back(max((pre[0][i].empty() ? 0 : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
            pre[1][i].push_back(max((pre[1][i].empty() ? 0 : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
        }
        suf[0][i].assign(ind[i].size(), 0);
        suf[1][i].assign(ind[i].size(), 0);
        for (int j = (int)ind[i].size() - 1; j >= 0; j--)
        {
            if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
            suf[0][i][j] = max(suf[0][i][j], dp[1][i][j]);
            suf[1][i][j] = max(suf[1][i][j], max(dp[0][i][j], dp[1][i][j]));
        }
    }
    long long ans = 0;
    for (int i = 1; i <= N; i++) 
    {
        for (long long &j : dp[0][i]) ans = max(ans, j);
        for (long long &j : dp[1][i]) ans = max(ans, j);
    }
    return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:43:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
      |                    ~~~^~~~~~~~~~~~~~~
fish.cpp:49:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:54:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:55:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:57:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
      |                 ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:59:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:60:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
      |                    ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:62:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
      |                            ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:74:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int j = 0; j < ind[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
      |                 ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 76132 KB Output is correct
2 Correct 66 ms 80948 KB Output is correct
3 Correct 8 ms 52312 KB Output is correct
4 Correct 8 ms 52056 KB Output is correct
5 Incorrect 202 ms 166192 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 102 ms 103564 KB Output is correct
3 Correct 132 ms 138988 KB Output is correct
4 Correct 52 ms 76012 KB Output is correct
5 Correct 64 ms 80948 KB Output is correct
6 Correct 7 ms 52060 KB Output is correct
7 Correct 7 ms 52116 KB Output is correct
8 Correct 7 ms 52060 KB Output is correct
9 Correct 7 ms 52112 KB Output is correct
10 Correct 8 ms 52060 KB Output is correct
11 Correct 8 ms 51900 KB Output is correct
12 Correct 58 ms 85260 KB Output is correct
13 Correct 69 ms 90400 KB Output is correct
14 Correct 54 ms 77804 KB Output is correct
15 Correct 63 ms 81552 KB Output is correct
16 Correct 64 ms 78344 KB Output is correct
17 Correct 65 ms 81516 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 8 ms 52056 KB Output is correct
3 Incorrect 58 ms 79748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52096 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 8 ms 51908 KB Output is correct
8 Correct 7 ms 52060 KB Output is correct
9 Correct 7 ms 52316 KB Output is correct
10 Correct 9 ms 52828 KB Output is correct
11 Correct 9 ms 52316 KB Output is correct
12 Correct 8 ms 52572 KB Output is correct
13 Correct 7 ms 52060 KB Output is correct
14 Correct 8 ms 52316 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52096 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 8 ms 51908 KB Output is correct
8 Correct 7 ms 52060 KB Output is correct
9 Correct 7 ms 52316 KB Output is correct
10 Correct 9 ms 52828 KB Output is correct
11 Correct 9 ms 52316 KB Output is correct
12 Correct 8 ms 52572 KB Output is correct
13 Correct 7 ms 52060 KB Output is correct
14 Correct 8 ms 52316 KB Output is correct
15 Correct 7 ms 52272 KB Output is correct
16 Incorrect 8 ms 52828 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '314050587306'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 7 ms 52112 KB Output is correct
3 Correct 7 ms 52096 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 7 ms 52060 KB Output is correct
6 Correct 6 ms 52060 KB Output is correct
7 Correct 8 ms 51908 KB Output is correct
8 Correct 7 ms 52060 KB Output is correct
9 Correct 7 ms 52316 KB Output is correct
10 Correct 9 ms 52828 KB Output is correct
11 Correct 9 ms 52316 KB Output is correct
12 Correct 8 ms 52572 KB Output is correct
13 Correct 7 ms 52060 KB Output is correct
14 Correct 8 ms 52316 KB Output is correct
15 Correct 7 ms 52272 KB Output is correct
16 Incorrect 8 ms 52828 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '314050587306'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 8 ms 52056 KB Output is correct
3 Incorrect 58 ms 79748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 76132 KB Output is correct
2 Correct 66 ms 80948 KB Output is correct
3 Correct 8 ms 52312 KB Output is correct
4 Correct 8 ms 52056 KB Output is correct
5 Incorrect 202 ms 166192 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572'
6 Halted 0 ms 0 KB -