oj.uz

Submission #656343

# Submission time Handle Problem Language Result Execution time Memory
656343 2022-11-07T01:14:20 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 258688 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
            auto it = 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) {
                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:131:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 113224 KB Output is correct
2 Correct 344 ms 125844 KB Output is correct
3 Correct 117 ms 91888 KB Output is correct
4 Correct 116 ms 91868 KB Output is correct
5 Execution timed out 1096 ms 258688 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 555 ms 142504 KB Output is correct
3 Correct 651 ms 160052 KB Output is correct
4 Correct 286 ms 113272 KB Output is correct
5 Correct 335 ms 126008 KB Output is correct
6 Correct 13 ms 26108 KB Output is correct
7 Correct 12 ms 26056 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 13 ms 26068 KB Output is correct
10 Correct 113 ms 91956 KB Output is correct
11 Correct 111 ms 91852 KB Output is correct
12 Correct 403 ms 133684 KB Output is correct
13 Correct 481 ms 150880 KB Output is correct
14 Correct 326 ms 123640 KB Output is correct
15 Correct 339 ms 123704 KB Output is correct
16 Correct 334 ms 123648 KB Output is correct
17 Correct 363 ms 134396 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 91872 KB Output is correct
2 Correct 114 ms 91860 KB Output is correct
3 Correct 145 ms 91496 KB Output is correct
4 Correct 140 ms 96076 KB Output is correct
5 Correct 187 ms 103616 KB Output is correct
6 Correct 183 ms 103604 KB Output is correct
7 Correct 188 ms 103536 KB Output is correct
8 Correct 184 ms 103548 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 13 ms 26196 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26128 KB Output is correct
5 Correct 13 ms 26104 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26076 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 15 ms 27136 KB Output is correct
11 Correct 16 ms 26456 KB Output is correct
12 Correct 15 ms 26836 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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 13 ms 26196 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26128 KB Output is correct
5 Correct 13 ms 26104 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26076 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 15 ms 27136 KB Output is correct
11 Correct 16 ms 26456 KB Output is correct
12 Correct 15 ms 26836 KB Output is correct
13 Correct 12 ms 26172 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 15 ms 26544 KB Output is correct
16 Correct 16 ms 27092 KB Output is correct
17 Correct 102 ms 45100 KB Output is correct
18 Correct 104 ms 44112 KB Output is correct
19 Correct 93 ms 44332 KB Output is correct
20 Correct 88 ms 42828 KB Output is correct
21 Correct 90 ms 42684 KB Output is correct
22 Correct 171 ms 58800 KB Output is correct
23 Correct 34 ms 32344 KB Output is correct
24 Correct 80 ms 43056 KB Output is correct
25 Correct 17 ms 26940 KB Output is correct
26 Correct 34 ms 31484 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26068 KB Output is correct
2 Correct 13 ms 26196 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 14 ms 26128 KB Output is correct
5 Correct 13 ms 26104 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 13 ms 26076 KB Output is correct
8 Correct 13 ms 26068 KB Output is correct
9 Correct 14 ms 26396 KB Output is correct
10 Correct 15 ms 27136 KB Output is correct
11 Correct 16 ms 26456 KB Output is correct
12 Correct 15 ms 26836 KB Output is correct
13 Correct 12 ms 26172 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 15 ms 26544 KB Output is correct
16 Correct 16 ms 27092 KB Output is correct
17 Correct 102 ms 45100 KB Output is correct
18 Correct 104 ms 44112 KB Output is correct
19 Correct 93 ms 44332 KB Output is correct
20 Correct 88 ms 42828 KB Output is correct
21 Correct 90 ms 42684 KB Output is correct
22 Correct 171 ms 58800 KB Output is correct
23 Correct 34 ms 32344 KB Output is correct
24 Correct 80 ms 43056 KB Output is correct
25 Correct 17 ms 26940 KB Output is correct
26 Correct 34 ms 31484 KB Output is correct
27 Correct 22 ms 30100 KB Output is correct
28 Correct 496 ms 115280 KB Output is correct
29 Correct 822 ms 167676 KB Output is correct
30 Correct 848 ms 235988 KB Output is correct
31 Correct 866 ms 234836 KB Output is correct
32 Correct 593 ms 133440 KB Output is correct
33 Correct 828 ms 240232 KB Output is correct
34 Correct 864 ms 240204 KB Output is correct
35 Correct 293 ms 95480 KB Output is correct
36 Correct 825 ms 217072 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 91872 KB Output is correct
2 Correct 114 ms 91860 KB Output is correct
3 Correct 145 ms 91496 KB Output is correct
4 Correct 140 ms 96076 KB Output is correct
5 Correct 187 ms 103616 KB Output is correct
6 Correct 183 ms 103604 KB Output is correct
7 Correct 188 ms 103536 KB Output is correct
8 Correct 184 ms 103548 KB Output is correct
9 Correct 341 ms 161616 KB Output is correct
10 Correct 158 ms 82484 KB Output is correct
11 Correct 305 ms 138828 KB Output is correct
12 Correct 13 ms 26140 KB Output is correct
13 Correct 12 ms 26132 KB Output is correct
14 Correct 12 ms 26068 KB Output is correct
15 Correct 13 ms 26140 KB Output is correct
16 Correct 14 ms 26024 KB Output is correct
17 Correct 12 ms 26084 KB Output is correct
18 Correct 110 ms 91864 KB Output is correct
19 Correct 110 ms 91772 KB Output is correct
20 Correct 116 ms 91864 KB Output is correct
21 Correct 112 ms 91836 KB Output is correct
22 Correct 358 ms 165096 KB Output is correct
23 Correct 451 ms 191936 KB Output is correct
24 Correct 466 ms 198268 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 113224 KB Output is correct
2 Correct 344 ms 125844 KB Output is correct
3 Correct 117 ms 91888 KB Output is correct
4 Correct 116 ms 91868 KB Output is correct
5 Execution timed out 1096 ms 258688 KB Time limit exceeded
6 Halted 0 ms 0 KB -