oj.uz

Submission #656429

# Submission time Handle Problem Language Result Execution time Memory
656429 2022-11-07T13:13:35 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 233628 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(pf[i-1].upper_bound(hr[i][h0]));
            dp[i][h0][0] = pfmx0[i-1][*it] + itpf->sc;

            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: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

# Verdict Execution time Memory Grader output
1 Correct 283 ms 113384 KB Output is correct
2 Correct 345 ms 125928 KB Output is correct
3 Correct 116 ms 91784 KB Output is correct
4 Correct 113 ms 91816 KB Output is correct
5 Execution timed out 1091 ms 233628 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 552 ms 141568 KB Output is correct
3 Correct 625 ms 160236 KB Output is correct
4 Correct 296 ms 113216 KB Output is correct
5 Correct 343 ms 126000 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26068 KB Output is correct
8 Correct 15 ms 26068 KB Output is correct
9 Correct 12 ms 26068 KB Output is correct
10 Correct 124 ms 91868 KB Output is correct
11 Correct 134 ms 91780 KB Output is correct
12 Correct 379 ms 123524 KB Output is correct
13 Correct 399 ms 138436 KB Output is correct
14 Correct 303 ms 118456 KB Output is correct
15 Correct 363 ms 123216 KB Output is correct
16 Correct 335 ms 118472 KB Output is correct
17 Correct 354 ms 128732 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 91840 KB Output is correct
2 Correct 124 ms 91872 KB Output is correct
3 Correct 151 ms 91556 KB Output is correct
4 Correct 149 ms 96104 KB Output is correct
5 Correct 194 ms 103580 KB Output is correct
6 Correct 206 ms 103504 KB Output is correct
7 Correct 198 ms 103628 KB Output is correct
8 Correct 203 ms 103584 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 13 ms 26140 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 13 ms 26060 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 26144 KB Output is correct
9 Correct 16 ms 26408 KB Output is correct
10 Correct 15 ms 27092 KB Output is correct
11 Correct 14 ms 26428 KB Output is correct
12 Correct 14 ms 26652 KB Output is correct
13 Correct 14 ms 26196 KB Output is correct
14 Correct 13 ms 26504 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 13 ms 26140 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 13 ms 26060 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 26144 KB Output is correct
9 Correct 16 ms 26408 KB Output is correct
10 Correct 15 ms 27092 KB Output is correct
11 Correct 14 ms 26428 KB Output is correct
12 Correct 14 ms 26652 KB Output is correct
13 Correct 14 ms 26196 KB Output is correct
14 Correct 13 ms 26504 KB Output is correct
15 Correct 13 ms 26452 KB Output is correct
16 Correct 17 ms 26908 KB Output is correct
17 Correct 99 ms 42936 KB Output is correct
18 Correct 101 ms 43080 KB Output is correct
19 Correct 85 ms 43204 KB Output is correct
20 Correct 84 ms 42700 KB Output is correct
21 Correct 86 ms 42700 KB Output is correct
22 Correct 175 ms 58812 KB Output is correct
23 Correct 30 ms 30796 KB Output is correct
24 Correct 68 ms 39504 KB Output is correct
25 Correct 16 ms 26832 KB Output is correct
26 Correct 28 ms 30272 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26068 KB Output is correct
2 Correct 13 ms 26140 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 13 ms 26068 KB Output is correct
5 Correct 13 ms 26060 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 26144 KB Output is correct
9 Correct 16 ms 26408 KB Output is correct
10 Correct 15 ms 27092 KB Output is correct
11 Correct 14 ms 26428 KB Output is correct
12 Correct 14 ms 26652 KB Output is correct
13 Correct 14 ms 26196 KB Output is correct
14 Correct 13 ms 26504 KB Output is correct
15 Correct 13 ms 26452 KB Output is correct
16 Correct 17 ms 26908 KB Output is correct
17 Correct 99 ms 42936 KB Output is correct
18 Correct 101 ms 43080 KB Output is correct
19 Correct 85 ms 43204 KB Output is correct
20 Correct 84 ms 42700 KB Output is correct
21 Correct 86 ms 42700 KB Output is correct
22 Correct 175 ms 58812 KB Output is correct
23 Correct 30 ms 30796 KB Output is correct
24 Correct 68 ms 39504 KB Output is correct
25 Correct 16 ms 26832 KB Output is correct
26 Correct 28 ms 30272 KB Output is correct
27 Correct 20 ms 29524 KB Output is correct
28 Correct 453 ms 106800 KB Output is correct
29 Correct 688 ms 144460 KB Output is correct
30 Correct 675 ms 182964 KB Output is correct
31 Correct 679 ms 182220 KB Output is correct
32 Correct 555 ms 133500 KB Output is correct
33 Correct 674 ms 185808 KB Output is correct
34 Correct 730 ms 185728 KB Output is correct
35 Correct 252 ms 80332 KB Output is correct
36 Correct 681 ms 172028 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 91840 KB Output is correct
2 Correct 124 ms 91872 KB Output is correct
3 Correct 151 ms 91556 KB Output is correct
4 Correct 149 ms 96104 KB Output is correct
5 Correct 194 ms 103580 KB Output is correct
6 Correct 206 ms 103504 KB Output is correct
7 Correct 198 ms 103628 KB Output is correct
8 Correct 203 ms 103584 KB Output is correct
9 Correct 342 ms 142796 KB Output is correct
10 Correct 158 ms 82380 KB Output is correct
11 Correct 316 ms 138816 KB Output is correct
12 Correct 14 ms 26068 KB Output is correct
13 Correct 13 ms 26068 KB Output is correct
14 Correct 13 ms 26068 KB Output is correct
15 Correct 16 ms 26044 KB Output is correct
16 Correct 17 ms 26068 KB Output is correct
17 Correct 14 ms 26068 KB Output is correct
18 Correct 115 ms 91868 KB Output is correct
19 Correct 111 ms 91872 KB Output is correct
20 Correct 112 ms 91868 KB Output is correct
21 Correct 116 ms 91868 KB Output is correct
22 Correct 327 ms 146208 KB Output is correct
23 Correct 392 ms 171640 KB Output is correct
24 Correct 420 ms 174784 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 113384 KB Output is correct
2 Correct 345 ms 125928 KB Output is correct
3 Correct 116 ms 91784 KB Output is correct
4 Correct 113 ms 91816 KB Output is correct
5 Execution timed out 1091 ms 233628 KB Time limit exceeded
6 Halted 0 ms 0 KB -