oj.uz

답안 #1077857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077857 2024-08-27T09:48:56 Z beaconmc 메기 농장 (IOI22_fish) C++17
81 / 100
 1000 ms 300464 KB 
#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
const ll maxn = 100005;
 
 
basic_string<ll> realheights[maxn];
 
unordered_map<ll, unordered_map<ll,ll>> weights;
 
basic_string<ll> p[maxn];
 
basic_string<array<ll,2>>  dp[maxn];
 
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<ll> suff[maxn][2];
 
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
 

    FOR(i,0,M){
        Y[i]++;
        weights[X[i]][Y[i]] = W[i];
 
        if (X[i] > 0) realheights[X[i]-1].push_back(Y[i]);
        if (X[i] > 1) realheights[X[i]-2].push_back(Y[i]);
        realheights[X[i]].push_back(Y[i]);
        realheights[X[i]+1].push_back(Y[i]);
        realheights[X[i]+2].push_back(Y[i]);
    }
    FOR(i,0,maxn) realheights[i].push_back(0);
    FOR(i,0,maxn) realheights[i].push_back(maxn);
 
    FOR(i,0,maxn){
        sort(realheights[i].begin(), realheights[i].end());
        auto it = unique(realheights[i].begin(), realheights[i].end());
        realheights[i].resize(it-realheights[i].begin());
        sort(realheights[i].begin(), realheights[i].end());
    }
 
    FOR(i,0,maxn){
        FOR(k,0,2){
            pref[i][k].resize(realheights[i].size());
            pref2[i][k].resize(realheights[i].size());
            suff[i][k].resize(realheights[i].size());
        }
        p[i].resize(realheights[i].size());
        dp[i].resize(realheights[i].size());
    }
 
 
 
 
    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        FOR(j,1,realheights[i].size()){
            p[i][j] = p[i][j-1] + weights[i][realheights[i][j]];
        }
    }
 
 
 
    FOR(i,1,N+1){
 
        FOR(X,0,dp[i].size()){
            ll j = realheights[i][X];
            FOR(k,0,2){
 
 
                if (i<2) continue;
                ll temp = 0;
                ll add = 0;
                if (k==0){
                    if (X==dp[i].size()-1) continue;
                    ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
 
                    temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
                    temp = max(temp, suff[i-1][1][down] - p[i-1][down]);
 
                    // FOR(p,j+1,N+1){
                    //     if (fish[i-1][p]) add += weights[i-1][p];
                    //     temp = max(temp, dp[i-1][p][0] + add);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }
                else{
                    ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
                    ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
 
 
                    temp = max(temp, pref[i-1][0][down]);
                    temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);
 
                    // FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
                    // FOR(p,0,j+1){
                    //     if (fish[i-2][p]) add -= weights[i-2][p];
                    //     temp = max(temp, dp[i-1][p][0]);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }
 
 
                dp[i][X][k] = temp;
            }
        }
        ll sz = realheights[i].size();
 
        FOR(k,0,2){
            ll tempadd = 0;
            ll tempadd2 = 0;
 
 
            FOR(j,0,sz){
                tempadd += weights[i][realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[(i-1)][realheights[i][j]];
                pref[i][k][j] = dp[i][j][k] + tempadd2;
                pref2[i][k][j] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
                pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
 
            }
 
            FORNEG(j,sz-2,-1){
                suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
 
 
            }
 
        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << endl;
 
    }
 
 
 
 
 
 
    ll ans = 0;
 
    FOR(i,0,N+1){
        FOR(j,0,dp[i].size()){
            ans = max(dp[i][j][0], ans);
            ans = max(dp[i][j][1], ans);
        }
    }
    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:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   66 |         FOR(j,1,realheights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:66:9: note: in expansion of macro 'FOR'
   66 |         FOR(j,1,realheights[i].size()){
      |         ^~~
fish.cpp:65:12: warning: unused variable 'prev' [-Wunused-variable]
   65 |         ll prev = 0;
      |            ^~~~
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   75 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:75:9: note: in expansion of macro 'FOR'
   75 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:84:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:82:20: warning: unused variable 'add' [-Wunused-variable]
   82 |                 ll add = 0;
      |                    ^~~
fish.cpp:133:16: warning: unused variable 'prev' [-Wunused-variable]
  133 |             ll prev = 0;
      |                ^~~~
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  160 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:160:9: note: in expansion of macro 'FOR'
  160 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 117672 KB Output is correct
2 Correct 221 ms 127396 KB Output is correct
3 Correct 100 ms 86328 KB Output is correct
4 Correct 98 ms 86188 KB Output is correct
5 Correct 822 ms 300464 KB Output is correct
6 Execution timed out 1038 ms 296136 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 83140 KB Output is correct
2 Correct 309 ms 137100 KB Output is correct
3 Correct 329 ms 146112 KB Output is correct
4 Correct 176 ms 117816 KB Output is correct
5 Correct 238 ms 127392 KB Output is correct
6 Correct 97 ms 83128 KB Output is correct
7 Correct 98 ms 83140 KB Output is correct
8 Correct 91 ms 83140 KB Output is correct
9 Correct 84 ms 83200 KB Output is correct
10 Correct 108 ms 86148 KB Output is correct
11 Correct 91 ms 86216 KB Output is correct
12 Correct 206 ms 127512 KB Output is correct
13 Correct 252 ms 139548 KB Output is correct
14 Correct 208 ms 122804 KB Output is correct
15 Correct 211 ms 114732 KB Output is correct
16 Correct 213 ms 122644 KB Output is correct
17 Correct 227 ms 129172 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 86212 KB Output is correct
2 Correct 92 ms 86292 KB Output is correct
3 Correct 184 ms 100552 KB Output is correct
4 Correct 160 ms 97480 KB Output is correct
5 Correct 264 ms 110996 KB Output is correct
6 Correct 260 ms 110276 KB Output is correct
7 Correct 260 ms 111200 KB Output is correct
8 Correct 260 ms 110792 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 83140 KB Output is correct
2 Correct 79 ms 83304 KB Output is correct
3 Correct 75 ms 83140 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 76 ms 83172 KB Output is correct
6 Correct 82 ms 83140 KB Output is correct
7 Correct 88 ms 83184 KB Output is correct
8 Correct 78 ms 83192 KB Output is correct
9 Correct 83 ms 83144 KB Output is correct
10 Correct 81 ms 83524 KB Output is correct
11 Correct 82 ms 83356 KB Output is correct
12 Correct 92 ms 83368 KB Output is correct
13 Correct 87 ms 83024 KB Output is correct
14 Correct 97 ms 83396 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 83140 KB Output is correct
2 Correct 79 ms 83304 KB Output is correct
3 Correct 75 ms 83140 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 76 ms 83172 KB Output is correct
6 Correct 82 ms 83140 KB Output is correct
7 Correct 88 ms 83184 KB Output is correct
8 Correct 78 ms 83192 KB Output is correct
9 Correct 83 ms 83144 KB Output is correct
10 Correct 81 ms 83524 KB Output is correct
11 Correct 82 ms 83356 KB Output is correct
12 Correct 92 ms 83368 KB Output is correct
13 Correct 87 ms 83024 KB Output is correct
14 Correct 97 ms 83396 KB Output is correct
15 Correct 78 ms 83400 KB Output is correct
16 Correct 94 ms 83740 KB Output is correct
17 Correct 139 ms 95428 KB Output is correct
18 Correct 129 ms 93380 KB Output is correct
19 Correct 153 ms 94668 KB Output is correct
20 Correct 130 ms 92872 KB Output is correct
21 Correct 127 ms 92480 KB Output is correct
22 Correct 164 ms 102080 KB Output is correct
23 Correct 137 ms 88560 KB Output is correct
24 Correct 130 ms 95176 KB Output is correct
25 Correct 73 ms 83544 KB Output is correct
26 Correct 115 ms 87236 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 83140 KB Output is correct
2 Correct 79 ms 83304 KB Output is correct
3 Correct 75 ms 83140 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 76 ms 83172 KB Output is correct
6 Correct 82 ms 83140 KB Output is correct
7 Correct 88 ms 83184 KB Output is correct
8 Correct 78 ms 83192 KB Output is correct
9 Correct 83 ms 83144 KB Output is correct
10 Correct 81 ms 83524 KB Output is correct
11 Correct 82 ms 83356 KB Output is correct
12 Correct 92 ms 83368 KB Output is correct
13 Correct 87 ms 83024 KB Output is correct
14 Correct 97 ms 83396 KB Output is correct
15 Correct 78 ms 83400 KB Output is correct
16 Correct 94 ms 83740 KB Output is correct
17 Correct 139 ms 95428 KB Output is correct
18 Correct 129 ms 93380 KB Output is correct
19 Correct 153 ms 94668 KB Output is correct
20 Correct 130 ms 92872 KB Output is correct
21 Correct 127 ms 92480 KB Output is correct
22 Correct 164 ms 102080 KB Output is correct
23 Correct 137 ms 88560 KB Output is correct
24 Correct 130 ms 95176 KB Output is correct
25 Correct 73 ms 83544 KB Output is correct
26 Correct 115 ms 87236 KB Output is correct
27 Correct 107 ms 85220 KB Output is correct
28 Correct 317 ms 133940 KB Output is correct
29 Correct 557 ms 187384 KB Output is correct
30 Correct 858 ms 272996 KB Output is correct
31 Correct 824 ms 265084 KB Output is correct
32 Correct 413 ms 145980 KB Output is correct
33 Correct 898 ms 285892 KB Output is correct
34 Correct 918 ms 286200 KB Output is correct
35 Correct 274 ms 131276 KB Output is correct
36 Correct 710 ms 228804 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 86212 KB Output is correct
2 Correct 92 ms 86292 KB Output is correct
3 Correct 184 ms 100552 KB Output is correct
4 Correct 160 ms 97480 KB Output is correct
5 Correct 264 ms 110996 KB Output is correct
6 Correct 260 ms 110276 KB Output is correct
7 Correct 260 ms 111200 KB Output is correct
8 Correct 260 ms 110792 KB Output is correct
9 Correct 414 ms 154820 KB Output is correct
10 Correct 195 ms 105160 KB Output is correct
11 Correct 393 ms 127096 KB Output is correct
12 Correct 70 ms 83140 KB Output is correct
13 Correct 72 ms 83144 KB Output is correct
14 Correct 112 ms 83140 KB Output is correct
15 Correct 74 ms 83148 KB Output is correct
16 Correct 70 ms 83140 KB Output is correct
17 Correct 73 ms 83140 KB Output is correct
18 Correct 126 ms 86288 KB Output is correct
19 Correct 117 ms 86384 KB Output is correct
20 Correct 92 ms 86216 KB Output is correct
21 Correct 98 ms 86324 KB Output is correct
22 Correct 512 ms 153164 KB Output is correct
23 Correct 507 ms 162248 KB Output is correct
24 Correct 611 ms 174216 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 117672 KB Output is correct
2 Correct 221 ms 127396 KB Output is correct
3 Correct 100 ms 86328 KB Output is correct
4 Correct 98 ms 86188 KB Output is correct
5 Correct 822 ms 300464 KB Output is correct
6 Execution timed out 1038 ms 296136 KB Time limit exceeded
7 Halted 0 ms 0 KB -