oj.uz

Submission #656338

# Submission time Handle Problem Language Result Execution time Memory
656338 2022-11-07T00:50:45 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 250520 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define int 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 maxqh = 12;
const int inf = 1e18+10;

int n, m;
vector<vector<int>> dp[maxn];
map<int,int> 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 j : hr[2]) {
        pfmx0[1][j] = max(pfmx0[1][j],0LL);
    }
    for(auto it = next(pfmx0[1].begin()); it != pfmx0[1].end(); it++) {
        it->sc = max(it->sc,prev(it)->sc);
    }

    for(auto j : hr[2]) {
        sfmx0[1][j] = max(sfmx0[1][j],0LL);
    }
    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
            dp[i][h0][0] = 0;
            dp[i][h0][0] = max(dp[i][h0][0], pfmx0[i-1][hr[i][h0]] + pf[i-1][hr[i][h0]]);

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

            // It's smaller than the previous
            dp[i][h0][1] = 0;
            // for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
            //     if(hr[i-1][h1] < hr[i][h0]) continue;
            //     dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][0]+pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]);
            //     dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][1]+pf[i][hr[i-1][h1]] - pf[i][hr[i][h0]]);
            // }

            dp[i][h0][1] = max(dp[i][h0][1], sfmx0[i-1][hr[i][h0]] - 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]],dp[i][h0][1]);
            pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],dp[i][h0][0]);
            sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],dp[i][h0][0]+pf[i+1][hr[i][h0]]);
            sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],dp[i][h0][1]+pf[i+1][hr[i][h0]]);
        }

        for(auto j : hr[i+1]) {
            pfmx0[i][j] = max(pfmx0[i][j],0LL);
        }
        for(auto it = next(pfmx0[i].begin()); it != pfmx0[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }

        for(auto j : hr[i+2]) {
            pfmx1[i][j] = max(pfmx1[i][j],0LL);
        }
        for(auto it = next(pfmx1[i].begin()); it != pfmx1[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }

        for(auto j : hr[i+1]) {
            sfmx0[i][j] = max(sfmx0[i][j],0LL);
        }
        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);
        }
    }


    int 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:38:26: 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]
   38 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:64:24: 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]
   64 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:90:28: 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]
   90 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:143:24: 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]
  143 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 114232 KB Output is correct
2 Correct 333 ms 127048 KB Output is correct
3 Correct 140 ms 91800 KB Output is correct
4 Correct 117 ms 91832 KB Output is correct
5 Execution timed out 1096 ms 246348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26068 KB Output is correct
2 Correct 596 ms 144492 KB Output is correct
3 Correct 784 ms 165784 KB Output is correct
4 Correct 285 ms 115628 KB Output is correct
5 Correct 357 ms 128816 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 14 ms 26068 KB Output is correct
9 Correct 14 ms 26196 KB Output is correct
10 Correct 128 ms 91872 KB Output is correct
11 Correct 119 ms 91800 KB Output is correct
12 Correct 448 ms 136036 KB Output is correct
13 Correct 556 ms 153908 KB Output is correct
14 Correct 361 ms 125876 KB Output is correct
15 Correct 370 ms 126496 KB Output is correct
16 Correct 362 ms 126112 KB Output is correct
17 Correct 394 ms 137116 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 91852 KB Output is correct
2 Correct 123 ms 91812 KB Output is correct
3 Correct 147 ms 92432 KB Output is correct
4 Correct 154 ms 96572 KB Output is correct
5 Correct 205 ms 105128 KB Output is correct
6 Correct 208 ms 105168 KB Output is correct
7 Correct 211 ms 105128 KB Output is correct
8 Correct 207 ms 105168 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 12 ms 26124 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 15 ms 26036 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 17 ms 26068 KB Output is correct
8 Correct 14 ms 26028 KB Output is correct
9 Correct 17 ms 26344 KB Output is correct
10 Correct 16 ms 27108 KB Output is correct
11 Correct 15 ms 26572 KB Output is correct
12 Correct 17 ms 26904 KB Output is correct
13 Correct 12 ms 26132 KB Output is correct
14 Correct 15 ms 26652 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 12 ms 26124 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 15 ms 26036 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 17 ms 26068 KB Output is correct
8 Correct 14 ms 26028 KB Output is correct
9 Correct 17 ms 26344 KB Output is correct
10 Correct 16 ms 27108 KB Output is correct
11 Correct 15 ms 26572 KB Output is correct
12 Correct 17 ms 26904 KB Output is correct
13 Correct 12 ms 26132 KB Output is correct
14 Correct 15 ms 26652 KB Output is correct
15 Correct 13 ms 26528 KB Output is correct
16 Correct 16 ms 27092 KB Output is correct
17 Correct 108 ms 45672 KB Output is correct
18 Correct 104 ms 45104 KB Output is correct
19 Correct 93 ms 45260 KB Output is correct
20 Correct 92 ms 43768 KB Output is correct
21 Correct 87 ms 43556 KB Output is correct
22 Correct 201 ms 60704 KB Output is correct
23 Correct 45 ms 32524 KB Output is correct
24 Correct 88 ms 43528 KB Output is correct
25 Correct 16 ms 26968 KB Output is correct
26 Correct 32 ms 31692 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 12 ms 26124 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 15 ms 26036 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 17 ms 26068 KB Output is correct
8 Correct 14 ms 26028 KB Output is correct
9 Correct 17 ms 26344 KB Output is correct
10 Correct 16 ms 27108 KB Output is correct
11 Correct 15 ms 26572 KB Output is correct
12 Correct 17 ms 26904 KB Output is correct
13 Correct 12 ms 26132 KB Output is correct
14 Correct 15 ms 26652 KB Output is correct
15 Correct 13 ms 26528 KB Output is correct
16 Correct 16 ms 27092 KB Output is correct
17 Correct 108 ms 45672 KB Output is correct
18 Correct 104 ms 45104 KB Output is correct
19 Correct 93 ms 45260 KB Output is correct
20 Correct 92 ms 43768 KB Output is correct
21 Correct 87 ms 43556 KB Output is correct
22 Correct 201 ms 60704 KB Output is correct
23 Correct 45 ms 32524 KB Output is correct
24 Correct 88 ms 43528 KB Output is correct
25 Correct 16 ms 26968 KB Output is correct
26 Correct 32 ms 31692 KB Output is correct
27 Correct 22 ms 30240 KB Output is correct
28 Correct 500 ms 118804 KB Output is correct
29 Correct 813 ms 177860 KB Output is correct
30 Correct 864 ms 246196 KB Output is correct
31 Correct 856 ms 245000 KB Output is correct
32 Correct 597 ms 143692 KB Output is correct
33 Correct 870 ms 250456 KB Output is correct
34 Correct 858 ms 250520 KB Output is correct
35 Correct 305 ms 99496 KB Output is correct
36 Correct 827 ms 228424 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 91852 KB Output is correct
2 Correct 123 ms 91812 KB Output is correct
3 Correct 147 ms 92432 KB Output is correct
4 Correct 154 ms 96572 KB Output is correct
5 Correct 205 ms 105128 KB Output is correct
6 Correct 208 ms 105168 KB Output is correct
7 Correct 211 ms 105128 KB Output is correct
8 Correct 207 ms 105168 KB Output is correct
9 Correct 315 ms 163148 KB Output is correct
10 Correct 161 ms 84072 KB Output is correct
11 Correct 356 ms 141960 KB Output is correct
12 Correct 13 ms 26132 KB Output is correct
13 Correct 14 ms 26196 KB Output is correct
14 Correct 13 ms 26068 KB Output is correct
15 Correct 12 ms 26112 KB Output is correct
16 Correct 12 ms 26140 KB Output is correct
17 Correct 12 ms 26096 KB Output is correct
18 Correct 122 ms 91936 KB Output is correct
19 Correct 118 ms 91852 KB Output is correct
20 Correct 120 ms 91852 KB Output is correct
21 Correct 116 ms 91828 KB Output is correct
22 Correct 448 ms 166476 KB Output is correct
23 Correct 482 ms 195140 KB Output is correct
24 Correct 517 ms 201420 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 114232 KB Output is correct
2 Correct 333 ms 127048 KB Output is correct
3 Correct 140 ms 91800 KB Output is correct
4 Correct 117 ms 91832 KB Output is correct
5 Execution timed out 1096 ms 246348 KB Time limit exceeded
6 Halted 0 ms 0 KB -