oj.uz

답안 #656427

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656427 2022-11-07T13:10:49 Z Lobo 메기 농장 (IOI22_fish) C++17
81 / 100
 1000 ms 234352 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
// #define int long long
#define ll long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int maxn = 1e5+10;
// const int inf = 1e18+10;

int n, m;
vector<vector<ll>> dp[maxn];
map<int,ll> pf[maxn], pfmx0[maxn], pfmx1[maxn], sfmx0[maxn];
vector<pair<int,int>> fish[maxn]; // fishs from column i
vector<int> hr[maxn]; // important heights from column i, the ones that can be chosen

long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) {
    n = N;
    m = M;

    for(int i = 0; i < m; i++) {
        fish[X[i]+1].pb(mp(Y[i]+1,W[i]));
        hr[X[i]+1].pb(Y[i]);
    }

    for(int i = 0; i <= n; i++) {
        hr[i].pb(0);
        hr[i].pb(n);
        sort(all(hr[i]));
        sort(all(fish[i]));
        hr[i].erase(unique(all(hr[i])),hr[i].end());
        // Store only the relevant heights

        for(int j = 0; j < hr[i].size(); j++) {
            dp[i].pb({0,0});
        }
    }

    for(int i = 1; i <= n; i++) {
        for(auto j : hr[i-1]) pf[i][j] = 0;
        for(auto j : hr[i]) pf[i][j] = 0;
        for(auto j : hr[i+1]) pf[i][j] = 0;

        for(auto aux : fish[i]) {
            int y = aux.fr;
            int w = aux.sc;
            pf[i][y]+= w;
        }
        // Do a prefix sum on the weight of the fishs
        pf[i][0] = 0;
        for(auto it = next(pf[i].begin()); it != pf[i].end(); it++) {
            it->sc+= prev(it)->sc;
        }
    }

    // dp[i][h0][0/1] = until i, with h[i] = hr[i][h0] 
    // and it's greater/smaller tha the previous

    // dp[1][h0][0/1] = 0
    for(int h0 = 0; h0 < hr[1].size(); h0++) {
        dp[1][h0][0] = 0;
        dp[1][h0][1] = 0;
        pfmx0[1][hr[1][h0]] = max(pfmx0[1][hr[1][h0]],dp[1][h0][0]-pf[1][hr[1][h0]]);
        sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][0]+pf[1+1][hr[1][h0]]);
        sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][1]+pf[1+1][hr[1][h0]]);
    }

    for(auto it = next(pfmx0[1].begin()); it != pfmx0[1].end(); it++) {
        it->sc = max(it->sc,prev(it)->sc);
    }
    auto it = prev(prev(sfmx0[1].end()));
    while(true) {
        it->sc = max(it->sc,next(it)->sc);
        if(it == sfmx0[1].begin()) break;
        it = prev(it);
    }

    for(int i = 2; i <= n; i++) {
        for(int h0 = 0; h0 < hr[i].size(); h0++) {
            // It's greater than the previous
            auto it = prev(upper_bound(all(hr[i-1]),hr[i][h0]));
            auto itpf = prev(upper_bound(all(hr[i-1]),hr[i][h0]));
            dp[i][h0][0] = pfmx0[i-1][*it] + pf[i-1][hr[i][h0]];

            if(i != 2) {
                it = prev(upper_bound(all(hr[i-2]),hr[i][h0]));
                dp[i][h0][0] = max(dp[i][h0][0],pfmx1[i-2][*it] + pf[i-1][hr[i][h0]]);
            }

            // It's smaller than the previous
            it = lower_bound(all(hr[i-1]),hr[i][h0]);
            dp[i][h0][1] = sfmx0[i-1][*it] - pf[i][hr[i][h0]];

            pfmx0[i][hr[i][h0]] = max(pfmx0[i][hr[i][h0]],dp[i][h0][0]-pf[i][hr[i][h0]]);
            pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],max(dp[i][h0][1],dp[i][h0][0]));
            sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],max(dp[i][h0][0],dp[i][h0][1])+pf[i+1][hr[i][h0]]);
        }
        for(auto it = next(pfmx0[i].begin()); it != pfmx0[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }
        for(auto it = next(pfmx1[i].begin()); it != pfmx1[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }
        auto it = prev(prev(sfmx0[i].end()));
        while(true) {
            it->sc = max(it->sc,next(it)->sc);
            if(it == sfmx0[i].begin()) break;
            it = prev(it);
        }
    }

    ll ans = 0;
    for(int h0 = 0; h0 < hr[n].size(); h0++) {
        ans = max(ans, dp[n][h0][0]);
        ans = max(ans, dp[n][h0][1]);
    }
    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:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:87:18: warning: variable 'itpf' set but not used [-Wunused-but-set-variable]
   87 |             auto itpf = prev(upper_bound(all(hr[i-1]),hr[i][h0]));
      |                  ^~~~
fish.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 113888 KB Output is correct
2 Correct 345 ms 126504 KB Output is correct
3 Correct 116 ms 91876 KB Output is correct
4 Correct 117 ms 91840 KB Output is correct
5 Execution timed out 1080 ms 234352 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 548 ms 142332 KB Output is correct
3 Correct 645 ms 160580 KB Output is correct
4 Correct 279 ms 113876 KB Output is correct
5 Correct 344 ms 126372 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 13 ms 26112 KB Output is correct
9 Correct 13 ms 26060 KB Output is correct
10 Correct 112 ms 91760 KB Output is correct
11 Correct 109 ms 91956 KB Output is correct
12 Correct 344 ms 124028 KB Output is correct
13 Correct 403 ms 138960 KB Output is correct
14 Correct 310 ms 118968 KB Output is correct
15 Correct 337 ms 123680 KB Output is correct
16 Correct 321 ms 118988 KB Output is correct
17 Correct 364 ms 129252 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 91860 KB Output is correct
2 Correct 115 ms 91968 KB Output is correct
3 Correct 141 ms 92136 KB Output is correct
4 Correct 138 ms 96612 KB Output is correct
5 Correct 229 ms 104328 KB Output is correct
6 Correct 186 ms 104248 KB Output is correct
7 Correct 187 ms 104180 KB Output is correct
8 Correct 194 ms 104396 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26040 KB Output is correct
2 Correct 13 ms 26128 KB Output is correct
3 Correct 13 ms 26132 KB Output is correct
4 Correct 12 ms 26144 KB Output is correct
5 Correct 13 ms 26196 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26132 KB Output is correct
8 Correct 13 ms 26096 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26528 KB Output is correct
12 Correct 16 ms 26680 KB Output is correct
13 Correct 12 ms 26172 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26040 KB Output is correct
2 Correct 13 ms 26128 KB Output is correct
3 Correct 13 ms 26132 KB Output is correct
4 Correct 12 ms 26144 KB Output is correct
5 Correct 13 ms 26196 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26132 KB Output is correct
8 Correct 13 ms 26096 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26528 KB Output is correct
12 Correct 16 ms 26680 KB Output is correct
13 Correct 12 ms 26172 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 14 ms 26392 KB Output is correct
16 Correct 16 ms 26920 KB Output is correct
17 Correct 94 ms 43540 KB Output is correct
18 Correct 97 ms 43564 KB Output is correct
19 Correct 89 ms 43816 KB Output is correct
20 Correct 87 ms 43212 KB Output is correct
21 Correct 86 ms 43160 KB Output is correct
22 Correct 174 ms 59332 KB Output is correct
23 Correct 31 ms 30924 KB Output is correct
24 Correct 72 ms 39940 KB Output is correct
25 Correct 17 ms 26788 KB Output is correct
26 Correct 33 ms 30328 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 26040 KB Output is correct
2 Correct 13 ms 26128 KB Output is correct
3 Correct 13 ms 26132 KB Output is correct
4 Correct 12 ms 26144 KB Output is correct
5 Correct 13 ms 26196 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26132 KB Output is correct
8 Correct 13 ms 26096 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26528 KB Output is correct
12 Correct 16 ms 26680 KB Output is correct
13 Correct 12 ms 26172 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 14 ms 26392 KB Output is correct
16 Correct 16 ms 26920 KB Output is correct
17 Correct 94 ms 43540 KB Output is correct
18 Correct 97 ms 43564 KB Output is correct
19 Correct 89 ms 43816 KB Output is correct
20 Correct 87 ms 43212 KB Output is correct
21 Correct 86 ms 43160 KB Output is correct
22 Correct 174 ms 59332 KB Output is correct
23 Correct 31 ms 30924 KB Output is correct
24 Correct 72 ms 39940 KB Output is correct
25 Correct 17 ms 26788 KB Output is correct
26 Correct 33 ms 30328 KB Output is correct
27 Correct 21 ms 29656 KB Output is correct
28 Correct 439 ms 107460 KB Output is correct
29 Correct 692 ms 144888 KB Output is correct
30 Correct 637 ms 183484 KB Output is correct
31 Correct 660 ms 182792 KB Output is correct
32 Correct 606 ms 133964 KB Output is correct
33 Correct 658 ms 186344 KB Output is correct
34 Correct 670 ms 186388 KB Output is correct
35 Correct 243 ms 80968 KB Output is correct
36 Correct 671 ms 172764 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 91860 KB Output is correct
2 Correct 115 ms 91968 KB Output is correct
3 Correct 141 ms 92136 KB Output is correct
4 Correct 138 ms 96612 KB Output is correct
5 Correct 229 ms 104328 KB Output is correct
6 Correct 186 ms 104248 KB Output is correct
7 Correct 187 ms 104180 KB Output is correct
8 Correct 194 ms 104396 KB Output is correct
9 Correct 291 ms 143384 KB Output is correct
10 Correct 174 ms 83128 KB Output is correct
11 Correct 309 ms 139436 KB Output is correct
12 Correct 13 ms 26068 KB Output is correct
13 Correct 13 ms 26136 KB Output is correct
14 Correct 13 ms 26120 KB Output is correct
15 Correct 13 ms 26068 KB Output is correct
16 Correct 13 ms 26136 KB Output is correct
17 Correct 13 ms 26068 KB Output is correct
18 Correct 112 ms 91872 KB Output is correct
19 Correct 109 ms 91976 KB Output is correct
20 Correct 116 ms 91756 KB Output is correct
21 Correct 109 ms 91796 KB Output is correct
22 Correct 325 ms 146916 KB Output is correct
23 Correct 392 ms 172272 KB Output is correct
24 Correct 389 ms 175504 KB Output is correct

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 113888 KB Output is correct
2 Correct 345 ms 126504 KB Output is correct
3 Correct 116 ms 91876 KB Output is correct
4 Correct 117 ms 91840 KB Output is correct
5 Execution timed out 1080 ms 234352 KB Time limit exceeded
6 Halted 0 ms 0 KB -