oj.uz

Submission #656347

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 113200 KB Output is correct
2 Correct 342 ms 125860 KB Output is correct
3 Correct 124 ms 91816 KB Output is correct
4 Correct 109 ms 91864 KB Output is correct
5 Execution timed out 1096 ms 233676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 564 ms 141528 KB Output is correct
3 Correct 648 ms 160060 KB Output is correct
4 Correct 289 ms 113208 KB Output is correct
5 Correct 350 ms 125856 KB Output is correct
6 Correct 17 ms 26068 KB Output is correct
7 Correct 14 ms 26068 KB Output is correct
8 Correct 16 ms 26020 KB Output is correct
9 Correct 14 ms 26068 KB Output is correct
10 Correct 114 ms 91808 KB Output is correct
11 Correct 134 ms 91948 KB Output is correct
12 Correct 337 ms 123480 KB Output is correct
13 Correct 416 ms 138456 KB Output is correct
14 Correct 298 ms 118608 KB Output is correct
15 Correct 332 ms 123164 KB Output is correct
16 Correct 313 ms 118492 KB Output is correct
17 Correct 361 ms 128640 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 91856 KB Output is correct
2 Correct 110 ms 91844 KB Output is correct
3 Correct 147 ms 91496 KB Output is correct
4 Correct 141 ms 96092 KB Output is correct
5 Correct 188 ms 103568 KB Output is correct
6 Correct 181 ms 103624 KB Output is correct
7 Correct 189 ms 103600 KB Output is correct
8 Correct 204 ms 103528 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26096 KB Output is correct
2 Correct 13 ms 26064 KB Output is correct
3 Correct 13 ms 26072 KB Output is correct
4 Correct 12 ms 26116 KB Output is correct
5 Correct 13 ms 26024 KB Output is correct
6 Correct 13 ms 26080 KB Output is correct
7 Correct 13 ms 26048 KB Output is correct
8 Correct 13 ms 26084 KB Output is correct
9 Correct 13 ms 26404 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 14 ms 26708 KB Output is correct
13 Correct 15 ms 26148 KB Output is correct
14 Correct 15 ms 26552 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26096 KB Output is correct
2 Correct 13 ms 26064 KB Output is correct
3 Correct 13 ms 26072 KB Output is correct
4 Correct 12 ms 26116 KB Output is correct
5 Correct 13 ms 26024 KB Output is correct
6 Correct 13 ms 26080 KB Output is correct
7 Correct 13 ms 26048 KB Output is correct
8 Correct 13 ms 26084 KB Output is correct
9 Correct 13 ms 26404 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 14 ms 26708 KB Output is correct
13 Correct 15 ms 26148 KB Output is correct
14 Correct 15 ms 26552 KB Output is correct
15 Correct 13 ms 26488 KB Output is correct
16 Correct 16 ms 26964 KB Output is correct
17 Correct 93 ms 42920 KB Output is correct
18 Correct 94 ms 43124 KB Output is correct
19 Correct 88 ms 43204 KB Output is correct
20 Correct 101 ms 42688 KB Output is correct
21 Correct 83 ms 42700 KB Output is correct
22 Correct 162 ms 59004 KB Output is correct
23 Correct 29 ms 30804 KB Output is correct
24 Correct 71 ms 39400 KB Output is correct
25 Correct 18 ms 26836 KB Output is correct
26 Correct 29 ms 30292 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26096 KB Output is correct
2 Correct 13 ms 26064 KB Output is correct
3 Correct 13 ms 26072 KB Output is correct
4 Correct 12 ms 26116 KB Output is correct
5 Correct 13 ms 26024 KB Output is correct
6 Correct 13 ms 26080 KB Output is correct
7 Correct 13 ms 26048 KB Output is correct
8 Correct 13 ms 26084 KB Output is correct
9 Correct 13 ms 26404 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 14 ms 26452 KB Output is correct
12 Correct 14 ms 26708 KB Output is correct
13 Correct 15 ms 26148 KB Output is correct
14 Correct 15 ms 26552 KB Output is correct
15 Correct 13 ms 26488 KB Output is correct
16 Correct 16 ms 26964 KB Output is correct
17 Correct 93 ms 42920 KB Output is correct
18 Correct 94 ms 43124 KB Output is correct
19 Correct 88 ms 43204 KB Output is correct
20 Correct 101 ms 42688 KB Output is correct
21 Correct 83 ms 42700 KB Output is correct
22 Correct 162 ms 59004 KB Output is correct
23 Correct 29 ms 30804 KB Output is correct
24 Correct 71 ms 39400 KB Output is correct
25 Correct 18 ms 26836 KB Output is correct
26 Correct 29 ms 30292 KB Output is correct
27 Correct 18 ms 29620 KB Output is correct
28 Correct 447 ms 106832 KB Output is correct
29 Correct 702 ms 144460 KB Output is correct
30 Correct 649 ms 183008 KB Output is correct
31 Correct 682 ms 182404 KB Output is correct
32 Correct 549 ms 133616 KB Output is correct
33 Correct 666 ms 185768 KB Output is correct
34 Correct 692 ms 185860 KB Output is correct
35 Correct 236 ms 80312 KB Output is correct
36 Correct 677 ms 172112 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 91856 KB Output is correct
2 Correct 110 ms 91844 KB Output is correct
3 Correct 147 ms 91496 KB Output is correct
4 Correct 141 ms 96092 KB Output is correct
5 Correct 188 ms 103568 KB Output is correct
6 Correct 181 ms 103624 KB Output is correct
7 Correct 189 ms 103600 KB Output is correct
8 Correct 204 ms 103528 KB Output is correct
9 Correct 282 ms 142752 KB Output is correct
10 Correct 149 ms 82484 KB Output is correct
11 Correct 352 ms 138952 KB Output is correct
12 Correct 14 ms 26068 KB Output is correct
13 Correct 15 ms 26044 KB Output is correct
14 Correct 14 ms 26028 KB Output is correct
15 Correct 13 ms 26136 KB Output is correct
16 Correct 13 ms 26068 KB Output is correct
17 Correct 13 ms 26068 KB Output is correct
18 Correct 120 ms 91768 KB Output is correct
19 Correct 117 ms 91812 KB Output is correct
20 Correct 116 ms 91800 KB Output is correct
21 Correct 112 ms 91932 KB Output is correct
22 Correct 364 ms 146180 KB Output is correct
23 Correct 387 ms 171584 KB Output is correct
24 Correct 395 ms 174780 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 113200 KB Output is correct
2 Correct 342 ms 125860 KB Output is correct
3 Correct 124 ms 91816 KB Output is correct
4 Correct 109 ms 91864 KB Output is correct
5 Execution timed out 1096 ms 233676 KB Time limit exceeded
6 Halted 0 ms 0 KB -