oj.uz

Submission #656342

# Submission time Handle Problem Language Result Execution time Memory
656342 2022-11-07T01:11:19 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 254084 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 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] = 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] = 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]],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 j : hr[i+1]) {
            pfmx0[i][j] = max(pfmx0[i][j],0LL);
            sfmx0[i][j] = max(sfmx0[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);
        }
        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:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 113372 KB Output is correct
2 Correct 328 ms 125948 KB Output is correct
3 Correct 113 ms 91872 KB Output is correct
4 Correct 109 ms 91760 KB Output is correct
5 Execution timed out 1099 ms 254084 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 534 ms 142668 KB Output is correct
3 Correct 654 ms 160036 KB Output is correct
4 Correct 274 ms 113208 KB Output is correct
5 Correct 323 ms 125908 KB Output is correct
6 Correct 12 ms 26056 KB Output is correct
7 Correct 13 ms 26044 KB Output is correct
8 Correct 12 ms 26140 KB Output is correct
9 Correct 12 ms 26136 KB Output is correct
10 Correct 108 ms 91868 KB Output is correct
11 Correct 107 ms 91844 KB Output is correct
12 Correct 406 ms 133636 KB Output is correct
13 Correct 508 ms 150896 KB Output is correct
14 Correct 324 ms 123456 KB Output is correct
15 Correct 339 ms 123764 KB Output is correct
16 Correct 326 ms 123608 KB Output is correct
17 Correct 360 ms 134244 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 91764 KB Output is correct
2 Correct 117 ms 91888 KB Output is correct
3 Correct 147 ms 91560 KB Output is correct
4 Correct 140 ms 96060 KB Output is correct
5 Correct 187 ms 103584 KB Output is correct
6 Correct 189 ms 103592 KB Output is correct
7 Correct 189 ms 103500 KB Output is correct
8 Correct 191 ms 103500 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 13 ms 26088 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26068 KB Output is correct
5 Correct 13 ms 26072 KB Output is correct
6 Correct 15 ms 26108 KB Output is correct
7 Correct 13 ms 26140 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26312 KB Output is correct
10 Correct 16 ms 27104 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 15 ms 26780 KB Output is correct
13 Correct 13 ms 26188 KB Output is correct
14 Correct 16 ms 26580 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 13 ms 26088 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26068 KB Output is correct
5 Correct 13 ms 26072 KB Output is correct
6 Correct 15 ms 26108 KB Output is correct
7 Correct 13 ms 26140 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26312 KB Output is correct
10 Correct 16 ms 27104 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 15 ms 26780 KB Output is correct
13 Correct 13 ms 26188 KB Output is correct
14 Correct 16 ms 26580 KB Output is correct
15 Correct 15 ms 26452 KB Output is correct
16 Correct 17 ms 27108 KB Output is correct
17 Correct 107 ms 45108 KB Output is correct
18 Correct 103 ms 44108 KB Output is correct
19 Correct 92 ms 44328 KB Output is correct
20 Correct 85 ms 42788 KB Output is correct
21 Correct 85 ms 42700 KB Output is correct
22 Correct 177 ms 58812 KB Output is correct
23 Correct 35 ms 32400 KB Output is correct
24 Correct 81 ms 43124 KB Output is correct
25 Correct 17 ms 26968 KB Output is correct
26 Correct 36 ms 31564 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 13 ms 26088 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26068 KB Output is correct
5 Correct 13 ms 26072 KB Output is correct
6 Correct 15 ms 26108 KB Output is correct
7 Correct 13 ms 26140 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26312 KB Output is correct
10 Correct 16 ms 27104 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 15 ms 26780 KB Output is correct
13 Correct 13 ms 26188 KB Output is correct
14 Correct 16 ms 26580 KB Output is correct
15 Correct 15 ms 26452 KB Output is correct
16 Correct 17 ms 27108 KB Output is correct
17 Correct 107 ms 45108 KB Output is correct
18 Correct 103 ms 44108 KB Output is correct
19 Correct 92 ms 44328 KB Output is correct
20 Correct 85 ms 42788 KB Output is correct
21 Correct 85 ms 42700 KB Output is correct
22 Correct 177 ms 58812 KB Output is correct
23 Correct 35 ms 32400 KB Output is correct
24 Correct 81 ms 43124 KB Output is correct
25 Correct 17 ms 26968 KB Output is correct
26 Correct 36 ms 31564 KB Output is correct
27 Correct 22 ms 30164 KB Output is correct
28 Correct 508 ms 115316 KB Output is correct
29 Correct 841 ms 167704 KB Output is correct
30 Correct 818 ms 236156 KB Output is correct
31 Correct 842 ms 234900 KB Output is correct
32 Correct 573 ms 133612 KB Output is correct
33 Correct 817 ms 240220 KB Output is correct
34 Correct 829 ms 240204 KB Output is correct
35 Correct 292 ms 95428 KB Output is correct
36 Correct 808 ms 217192 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 91764 KB Output is correct
2 Correct 117 ms 91888 KB Output is correct
3 Correct 147 ms 91560 KB Output is correct
4 Correct 140 ms 96060 KB Output is correct
5 Correct 187 ms 103584 KB Output is correct
6 Correct 189 ms 103592 KB Output is correct
7 Correct 189 ms 103500 KB Output is correct
8 Correct 191 ms 103500 KB Output is correct
9 Correct 343 ms 161460 KB Output is correct
10 Correct 147 ms 82468 KB Output is correct
11 Correct 307 ms 138832 KB Output is correct
12 Correct 13 ms 26132 KB Output is correct
13 Correct 12 ms 26068 KB Output is correct
14 Correct 13 ms 26136 KB Output is correct
15 Correct 12 ms 26132 KB Output is correct
16 Correct 12 ms 26068 KB Output is correct
17 Correct 12 ms 26072 KB Output is correct
18 Correct 110 ms 91868 KB Output is correct
19 Correct 108 ms 91940 KB Output is correct
20 Correct 109 ms 91868 KB Output is correct
21 Correct 108 ms 91856 KB Output is correct
22 Correct 348 ms 164948 KB Output is correct
23 Correct 450 ms 191940 KB Output is correct
24 Correct 518 ms 198288 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 113372 KB Output is correct
2 Correct 328 ms 125948 KB Output is correct
3 Correct 113 ms 91872 KB Output is correct
4 Correct 109 ms 91760 KB Output is correct
5 Execution timed out 1099 ms 254084 KB Time limit exceeded
6 Halted 0 ms 0 KB -