oj.uz

Submission #656341

# Submission time Handle Problem Language Result Execution time Memory
656341 2022-11-07T01:02:15 Z Lobo Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 249244 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
// #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
            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]));
            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:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:129:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 113352 KB Output is correct
2 Correct 347 ms 126032 KB Output is correct
3 Correct 113 ms 91840 KB Output is correct
4 Correct 129 ms 91872 KB Output is correct
5 Execution timed out 1092 ms 249244 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26028 KB Output is correct
2 Correct 546 ms 142528 KB Output is correct
3 Correct 644 ms 160024 KB Output is correct
4 Correct 289 ms 113328 KB Output is correct
5 Correct 329 ms 125940 KB Output is correct
6 Correct 16 ms 26068 KB Output is correct
7 Correct 13 ms 26124 KB Output is correct
8 Correct 13 ms 26120 KB Output is correct
9 Correct 13 ms 26068 KB Output is correct
10 Correct 109 ms 91840 KB Output is correct
11 Correct 110 ms 91764 KB Output is correct
12 Correct 417 ms 133720 KB Output is correct
13 Correct 511 ms 150968 KB Output is correct
14 Correct 336 ms 123560 KB Output is correct
15 Correct 373 ms 124012 KB Output is correct
16 Correct 337 ms 123512 KB Output is correct
17 Correct 378 ms 134320 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 91768 KB Output is correct
2 Correct 111 ms 91852 KB Output is correct
3 Correct 148 ms 91540 KB Output is correct
4 Correct 141 ms 96076 KB Output is correct
5 Correct 190 ms 103824 KB Output is correct
6 Correct 189 ms 103620 KB Output is correct
7 Correct 205 ms 103504 KB Output is correct
8 Correct 208 ms 103600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26096 KB Output is correct
2 Correct 17 ms 26068 KB Output is correct
3 Correct 17 ms 26068 KB Output is correct
4 Correct 15 ms 26068 KB Output is correct
5 Correct 15 ms 26196 KB Output is correct
6 Correct 15 ms 26020 KB Output is correct
7 Correct 14 ms 26096 KB Output is correct
8 Correct 14 ms 26144 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 22 ms 27092 KB Output is correct
11 Correct 17 ms 26452 KB Output is correct
12 Correct 19 ms 26836 KB Output is correct
13 Correct 17 ms 26136 KB Output is correct
14 Correct 16 ms 26580 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26096 KB Output is correct
2 Correct 17 ms 26068 KB Output is correct
3 Correct 17 ms 26068 KB Output is correct
4 Correct 15 ms 26068 KB Output is correct
5 Correct 15 ms 26196 KB Output is correct
6 Correct 15 ms 26020 KB Output is correct
7 Correct 14 ms 26096 KB Output is correct
8 Correct 14 ms 26144 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 22 ms 27092 KB Output is correct
11 Correct 17 ms 26452 KB Output is correct
12 Correct 19 ms 26836 KB Output is correct
13 Correct 17 ms 26136 KB Output is correct
14 Correct 16 ms 26580 KB Output is correct
15 Correct 17 ms 26452 KB Output is correct
16 Correct 18 ms 27076 KB Output is correct
17 Correct 100 ms 45108 KB Output is correct
18 Correct 120 ms 44108 KB Output is correct
19 Correct 94 ms 44292 KB Output is correct
20 Correct 85 ms 42908 KB Output is correct
21 Correct 82 ms 42700 KB Output is correct
22 Correct 172 ms 58812 KB Output is correct
23 Correct 35 ms 32356 KB Output is correct
24 Correct 83 ms 43052 KB Output is correct
25 Correct 16 ms 26972 KB Output is correct
26 Correct 32 ms 31572 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26096 KB Output is correct
2 Correct 17 ms 26068 KB Output is correct
3 Correct 17 ms 26068 KB Output is correct
4 Correct 15 ms 26068 KB Output is correct
5 Correct 15 ms 26196 KB Output is correct
6 Correct 15 ms 26020 KB Output is correct
7 Correct 14 ms 26096 KB Output is correct
8 Correct 14 ms 26144 KB Output is correct
9 Correct 14 ms 26324 KB Output is correct
10 Correct 22 ms 27092 KB Output is correct
11 Correct 17 ms 26452 KB Output is correct
12 Correct 19 ms 26836 KB Output is correct
13 Correct 17 ms 26136 KB Output is correct
14 Correct 16 ms 26580 KB Output is correct
15 Correct 17 ms 26452 KB Output is correct
16 Correct 18 ms 27076 KB Output is correct
17 Correct 100 ms 45108 KB Output is correct
18 Correct 120 ms 44108 KB Output is correct
19 Correct 94 ms 44292 KB Output is correct
20 Correct 85 ms 42908 KB Output is correct
21 Correct 82 ms 42700 KB Output is correct
22 Correct 172 ms 58812 KB Output is correct
23 Correct 35 ms 32356 KB Output is correct
24 Correct 83 ms 43052 KB Output is correct
25 Correct 16 ms 26972 KB Output is correct
26 Correct 32 ms 31572 KB Output is correct
27 Correct 22 ms 30240 KB Output is correct
28 Correct 482 ms 115344 KB Output is correct
29 Correct 811 ms 167608 KB Output is correct
30 Correct 827 ms 236104 KB Output is correct
31 Correct 822 ms 234828 KB Output is correct
32 Correct 571 ms 133420 KB Output is correct
33 Correct 881 ms 240200 KB Output is correct
34 Correct 874 ms 240204 KB Output is correct
35 Correct 296 ms 95436 KB Output is correct
36 Correct 877 ms 217148 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 91768 KB Output is correct
2 Correct 111 ms 91852 KB Output is correct
3 Correct 148 ms 91540 KB Output is correct
4 Correct 141 ms 96076 KB Output is correct
5 Correct 190 ms 103824 KB Output is correct
6 Correct 189 ms 103620 KB Output is correct
7 Correct 205 ms 103504 KB Output is correct
8 Correct 208 ms 103600 KB Output is correct
9 Correct 426 ms 161452 KB Output is correct
10 Correct 151 ms 82372 KB Output is correct
11 Correct 319 ms 138832 KB Output is correct
12 Correct 12 ms 26068 KB Output is correct
13 Correct 13 ms 26068 KB Output is correct
14 Correct 12 ms 26100 KB Output is correct
15 Correct 12 ms 26068 KB Output is correct
16 Correct 12 ms 26136 KB Output is correct
17 Correct 13 ms 26144 KB Output is correct
18 Correct 117 ms 91844 KB Output is correct
19 Correct 111 ms 91852 KB Output is correct
20 Correct 149 ms 91780 KB Output is correct
21 Correct 120 ms 91876 KB Output is correct
22 Correct 351 ms 165000 KB Output is correct
23 Correct 499 ms 191940 KB Output is correct
24 Correct 463 ms 198452 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 113352 KB Output is correct
2 Correct 347 ms 126032 KB Output is correct
3 Correct 113 ms 91840 KB Output is correct
4 Correct 129 ms 91872 KB Output is correct
5 Execution timed out 1092 ms 249244 KB Time limit exceeded
6 Halted 0 ms 0 KB -