oj.uz

Submission #656346

# Submission time Handle Problem Language Result Execution time Memory
656346 2022-11-07T01:19:32 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 252456 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) {
                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 j : hr[i+1]) {
            // 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:110:18: warning: unused variable 'j' [-Wunused-variable]
  110 |         for(auto j : hr[i+1]) {
      |                  ^
fish.cpp:132:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 113292 KB Output is correct
2 Correct 344 ms 125908 KB Output is correct
3 Correct 125 ms 91852 KB Output is correct
4 Correct 114 ms 91848 KB Output is correct
5 Execution timed out 1103 ms 252456 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 543 ms 142592 KB Output is correct
3 Correct 659 ms 160088 KB Output is correct
4 Correct 292 ms 113336 KB Output is correct
5 Correct 344 ms 125924 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 15 ms 26068 KB Output is correct
8 Correct 12 ms 26072 KB Output is correct
9 Correct 12 ms 26128 KB Output is correct
10 Correct 109 ms 91780 KB Output is correct
11 Correct 114 ms 91800 KB Output is correct
12 Correct 398 ms 133688 KB Output is correct
13 Correct 483 ms 151164 KB Output is correct
14 Correct 348 ms 123708 KB Output is correct
15 Correct 347 ms 123752 KB Output is correct
16 Correct 338 ms 123616 KB Output is correct
17 Correct 380 ms 134248 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 91868 KB Output is correct
2 Correct 120 ms 91764 KB Output is correct
3 Correct 163 ms 91568 KB Output is correct
4 Correct 142 ms 96028 KB Output is correct
5 Correct 194 ms 103512 KB Output is correct
6 Correct 180 ms 103596 KB Output is correct
7 Correct 189 ms 103620 KB Output is correct
8 Correct 196 ms 103536 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26072 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26012 KB Output is correct
5 Correct 13 ms 26060 KB Output is correct
6 Correct 13 ms 26144 KB Output is correct
7 Correct 13 ms 26036 KB Output is correct
8 Correct 13 ms 26048 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 13 ms 26524 KB Output is correct
12 Correct 14 ms 26772 KB Output is correct
13 Correct 13 ms 26116 KB Output is correct
14 Correct 16 ms 26624 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26072 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26012 KB Output is correct
5 Correct 13 ms 26060 KB Output is correct
6 Correct 13 ms 26144 KB Output is correct
7 Correct 13 ms 26036 KB Output is correct
8 Correct 13 ms 26048 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 13 ms 26524 KB Output is correct
12 Correct 14 ms 26772 KB Output is correct
13 Correct 13 ms 26116 KB Output is correct
14 Correct 16 ms 26624 KB Output is correct
15 Correct 13 ms 26416 KB Output is correct
16 Correct 16 ms 26932 KB Output is correct
17 Correct 104 ms 43700 KB Output is correct
18 Correct 100 ms 43436 KB Output is correct
19 Correct 92 ms 43800 KB Output is correct
20 Correct 85 ms 42828 KB Output is correct
21 Correct 94 ms 42656 KB Output is correct
22 Correct 166 ms 58796 KB Output is correct
23 Correct 31 ms 31320 KB Output is correct
24 Correct 76 ms 40612 KB Output is correct
25 Correct 15 ms 26836 KB Output is correct
26 Correct 30 ms 30664 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26072 KB Output is correct
2 Correct 13 ms 26068 KB Output is correct
3 Correct 12 ms 26068 KB Output is correct
4 Correct 13 ms 26012 KB Output is correct
5 Correct 13 ms 26060 KB Output is correct
6 Correct 13 ms 26144 KB Output is correct
7 Correct 13 ms 26036 KB Output is correct
8 Correct 13 ms 26048 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 16 ms 27092 KB Output is correct
11 Correct 13 ms 26524 KB Output is correct
12 Correct 14 ms 26772 KB Output is correct
13 Correct 13 ms 26116 KB Output is correct
14 Correct 16 ms 26624 KB Output is correct
15 Correct 13 ms 26416 KB Output is correct
16 Correct 16 ms 26932 KB Output is correct
17 Correct 104 ms 43700 KB Output is correct
18 Correct 100 ms 43436 KB Output is correct
19 Correct 92 ms 43800 KB Output is correct
20 Correct 85 ms 42828 KB Output is correct
21 Correct 94 ms 42656 KB Output is correct
22 Correct 166 ms 58796 KB Output is correct
23 Correct 31 ms 31320 KB Output is correct
24 Correct 76 ms 40612 KB Output is correct
25 Correct 15 ms 26836 KB Output is correct
26 Correct 30 ms 30664 KB Output is correct
27 Correct 20 ms 29800 KB Output is correct
28 Correct 469 ms 109724 KB Output is correct
29 Correct 741 ms 154204 KB Output is correct
30 Correct 697 ms 200736 KB Output is correct
31 Correct 725 ms 199796 KB Output is correct
32 Correct 610 ms 133508 KB Output is correct
33 Correct 707 ms 203864 KB Output is correct
34 Correct 704 ms 203952 KB Output is correct
35 Correct 253 ms 85428 KB Output is correct
36 Correct 721 ms 187056 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 91868 KB Output is correct
2 Correct 120 ms 91764 KB Output is correct
3 Correct 163 ms 91568 KB Output is correct
4 Correct 142 ms 96028 KB Output is correct
5 Correct 194 ms 103512 KB Output is correct
6 Correct 180 ms 103596 KB Output is correct
7 Correct 189 ms 103620 KB Output is correct
8 Correct 196 ms 103536 KB Output is correct
9 Correct 289 ms 148912 KB Output is correct
10 Correct 148 ms 82420 KB Output is correct
11 Correct 305 ms 138828 KB Output is correct
12 Correct 13 ms 26068 KB Output is correct
13 Correct 13 ms 26068 KB Output is correct
14 Correct 12 ms 26068 KB Output is correct
15 Correct 13 ms 26060 KB Output is correct
16 Correct 14 ms 26068 KB Output is correct
17 Correct 13 ms 26144 KB Output is correct
18 Correct 108 ms 91860 KB Output is correct
19 Correct 105 ms 91852 KB Output is correct
20 Correct 105 ms 91852 KB Output is correct
21 Correct 109 ms 91756 KB Output is correct
22 Correct 326 ms 152520 KB Output is correct
23 Correct 415 ms 180236 KB Output is correct
24 Correct 425 ms 185796 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 113292 KB Output is correct
2 Correct 344 ms 125908 KB Output is correct
3 Correct 125 ms 91852 KB Output is correct
4 Correct 114 ms 91848 KB Output is correct
5 Execution timed out 1103 ms 252456 KB Time limit exceeded
6 Halted 0 ms 0 KB -