oj.uz

Submission #656339

# Submission time Handle Problem Language Result Execution time Memory
656339 2022-11-07T00:58:27 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 276260 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define int 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<int>> dp[maxn];
map<int,int> 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]));
            // pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],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]]);
            // sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],dp[i][h0][1]+pf[i+1][hr[i][h0]]);
        }

        for(auto j : hr[i+1]) {
            pfmx0[i][j] = max(pfmx0[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);
        }

        for(auto j : hr[i+1]) {
            sfmx0[i][j] = max(sfmx0[i][j],0LL);
        }
        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);
        }
    }

    int 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:37:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:63:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:89:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:133:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 114216 KB Output is correct
2 Correct 334 ms 127256 KB Output is correct
3 Correct 114 ms 91864 KB Output is correct
4 Correct 111 ms 91956 KB Output is correct
5 Execution timed out 1104 ms 276260 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 26040 KB Output is correct
2 Correct 528 ms 144492 KB Output is correct
3 Correct 651 ms 162396 KB Output is correct
4 Correct 270 ms 114264 KB Output is correct
5 Correct 333 ms 127088 KB Output is correct
6 Correct 12 ms 26088 KB Output is correct
7 Correct 13 ms 26032 KB Output is correct
8 Correct 13 ms 26072 KB Output is correct
9 Correct 13 ms 26068 KB Output is correct
10 Correct 113 ms 91820 KB Output is correct
11 Correct 109 ms 91784 KB Output is correct
12 Correct 388 ms 134716 KB Output is correct
13 Correct 487 ms 152108 KB Output is correct
14 Correct 328 ms 124428 KB Output is correct
15 Correct 336 ms 124920 KB Output is correct
16 Correct 323 ms 124816 KB Output is correct
17 Correct 361 ms 135528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 91860 KB Output is correct
2 Correct 115 ms 91852 KB Output is correct
3 Correct 145 ms 92408 KB Output is correct
4 Correct 139 ms 96632 KB Output is correct
5 Correct 195 ms 105132 KB Output is correct
6 Correct 196 ms 105136 KB Output is correct
7 Correct 198 ms 105140 KB Output is correct
8 Correct 191 ms 105180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26076 KB Output is correct
2 Correct 14 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 14 ms 26104 KB Output is correct
6 Correct 14 ms 26064 KB Output is correct
7 Correct 14 ms 26124 KB Output is correct
8 Correct 14 ms 26068 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 18 ms 27128 KB Output is correct
11 Correct 13 ms 26452 KB Output is correct
12 Correct 15 ms 26836 KB Output is correct
13 Correct 12 ms 26196 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 12 ms 26076 KB Output is correct
2 Correct 14 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 14 ms 26104 KB Output is correct
6 Correct 14 ms 26064 KB Output is correct
7 Correct 14 ms 26124 KB Output is correct
8 Correct 14 ms 26068 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 18 ms 27128 KB Output is correct
11 Correct 13 ms 26452 KB Output is correct
12 Correct 15 ms 26836 KB Output is correct
13 Correct 12 ms 26196 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 13 ms 26452 KB Output is correct
16 Correct 16 ms 27024 KB Output is correct
17 Correct 100 ms 45644 KB Output is correct
18 Correct 98 ms 45088 KB Output is correct
19 Correct 86 ms 45256 KB Output is correct
20 Correct 86 ms 43724 KB Output is correct
21 Correct 82 ms 43728 KB Output is correct
22 Correct 165 ms 60620 KB Output is correct
23 Correct 33 ms 32516 KB Output is correct
24 Correct 83 ms 43588 KB Output is correct
25 Correct 15 ms 26964 KB Output is correct
26 Correct 31 ms 31592 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26076 KB Output is correct
2 Correct 14 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 14 ms 26104 KB Output is correct
6 Correct 14 ms 26064 KB Output is correct
7 Correct 14 ms 26124 KB Output is correct
8 Correct 14 ms 26068 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 18 ms 27128 KB Output is correct
11 Correct 13 ms 26452 KB Output is correct
12 Correct 15 ms 26836 KB Output is correct
13 Correct 12 ms 26196 KB Output is correct
14 Correct 14 ms 26580 KB Output is correct
15 Correct 13 ms 26452 KB Output is correct
16 Correct 16 ms 27024 KB Output is correct
17 Correct 100 ms 45644 KB Output is correct
18 Correct 98 ms 45088 KB Output is correct
19 Correct 86 ms 45256 KB Output is correct
20 Correct 86 ms 43724 KB Output is correct
21 Correct 82 ms 43728 KB Output is correct
22 Correct 165 ms 60620 KB Output is correct
23 Correct 33 ms 32516 KB Output is correct
24 Correct 83 ms 43588 KB Output is correct
25 Correct 15 ms 26964 KB Output is correct
26 Correct 31 ms 31592 KB Output is correct
27 Correct 22 ms 30164 KB Output is correct
28 Correct 466 ms 118856 KB Output is correct
29 Correct 740 ms 172144 KB Output is correct
30 Correct 809 ms 240600 KB Output is correct
31 Correct 807 ms 239360 KB Output is correct
32 Correct 547 ms 138584 KB Output is correct
33 Correct 826 ms 244760 KB Output is correct
34 Correct 812 ms 244728 KB Output is correct
35 Correct 291 ms 97612 KB Output is correct
36 Correct 771 ms 223080 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 91860 KB Output is correct
2 Correct 115 ms 91852 KB Output is correct
3 Correct 145 ms 92408 KB Output is correct
4 Correct 139 ms 96632 KB Output is correct
5 Correct 195 ms 105132 KB Output is correct
6 Correct 196 ms 105136 KB Output is correct
7 Correct 198 ms 105140 KB Output is correct
8 Correct 191 ms 105180 KB Output is correct
9 Correct 311 ms 163004 KB Output is correct
10 Correct 165 ms 84024 KB Output is correct
11 Correct 349 ms 142004 KB Output is correct
12 Correct 14 ms 26116 KB Output is correct
13 Correct 12 ms 26040 KB Output is correct
14 Correct 13 ms 26068 KB Output is correct
15 Correct 12 ms 26048 KB Output is correct
16 Correct 12 ms 26068 KB Output is correct
17 Correct 12 ms 26068 KB Output is correct
18 Correct 113 ms 91804 KB Output is correct
19 Correct 115 ms 91932 KB Output is correct
20 Correct 119 ms 91788 KB Output is correct
21 Correct 127 ms 91848 KB Output is correct
22 Correct 432 ms 166576 KB Output is correct
23 Correct 548 ms 195044 KB Output is correct
24 Correct 534 ms 201504 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 114216 KB Output is correct
2 Correct 334 ms 127256 KB Output is correct
3 Correct 114 ms 91864 KB Output is correct
4 Correct 111 ms 91956 KB Output is correct
5 Execution timed out 1104 ms 276260 KB Time limit exceeded
6 Halted 0 ms 0 KB -