oj.uz

Submission #656328

# Submission time Handle Problem Language Result Execution time Memory
656328 2022-11-07T00:13:37 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 182508 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 maxqh = 12;
const int inf = 1e18+10;

int n, m;
vector<vector<int>> dp[maxn];
map<int,int> pf[maxn], pfmx0[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 i = 0; i < hr[1].size(); i++) {
        dp[1][i][0] = 0;
        dp[1][i][1] = 0;
    }

    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] = 0;
            for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
                if(hr[i-1][h1] > hr[i][h0]) continue;
                dp[i][h0][0] = max(dp[i][h0][0], dp[i-1][h1][0]-pf[i-1][hr[i-1][h1]] + pf[i-1][hr[i][h0]]);
            }

            if(i != 2) {
                for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
                    if(hr[i-2][h2] > hr[i][h0]) continue;
                    dp[i][h0][0] = max(dp[i][h0][0], dp[i-2][h2][1] + pf[i-1][hr[i][h0]]);
                    dp[i][h0][0] = max(dp[i][h0][0], dp[i-2][h2][0] + pf[i-1][hr[i][h0]]);
                }
            }

            // It's smaller than the previous
            dp[i][h0][1] = 0;
            for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
                if(hr[i-1][h1] < hr[i][h0]) continue;
                dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][0]-pf[i][hr[i][h0]] + pf[i][hr[i-1][h1]]);
                dp[i][h0][1] = max(dp[i][h0][1], dp[i-1][h1][1]-pf[i][hr[i][h0]] + pf[i][hr[i-1][h1]]);
            }

            pfmx0[i][hr[i][h0]] = max(pfmx0[i][hr[i][h0]],dp[i][h0][0]-pf[i][hr[i][h0]]);
        }

        if(i == n) continue;

        for(auto j : hr[i+1]) {
            pfmx0[i][j] = max(pfmx0[i][j],0LL);
        }
        for(auto it = next(pf[i].begin()); it != pf[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }
    }

    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:38: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]
   38 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:64:22: 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]
   64 |     for(int i = 0; i < hr[1].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:70: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]
   70 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:73:32: 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]
   73 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:79:36: 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]
   79 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:88:32: 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]
   88 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:108: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]
  108 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 72172 KB Output is correct
2 Correct 288 ms 80104 KB Output is correct
3 Correct 77 ms 57424 KB Output is correct
4 Correct 82 ms 57360 KB Output is correct
5 Execution timed out 1097 ms 182508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Execution timed out 1091 ms 74928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 57420 KB Output is correct
2 Correct 79 ms 57368 KB Output is correct
3 Correct 148 ms 60456 KB Output is correct
4 Correct 111 ms 62208 KB Output is correct
5 Correct 187 ms 70760 KB Output is correct
6 Correct 196 ms 70716 KB Output is correct
7 Correct 165 ms 70856 KB Output is correct
8 Correct 182 ms 70872 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16624 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 8 ms 16700 KB Output is correct
4 Correct 8 ms 16684 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16736 KB Output is correct
8 Correct 8 ms 16656 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 12 ms 17344 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 20 ms 17108 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 16980 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16624 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 8 ms 16700 KB Output is correct
4 Correct 8 ms 16684 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16736 KB Output is correct
8 Correct 8 ms 16656 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 12 ms 17344 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 20 ms 17108 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 16980 KB Output is correct
15 Correct 9 ms 16980 KB Output is correct
16 Correct 21 ms 17268 KB Output is correct
17 Correct 950 ms 28984 KB Output is correct
18 Execution timed out 1056 ms 29340 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16624 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 8 ms 16700 KB Output is correct
4 Correct 8 ms 16684 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16736 KB Output is correct
8 Correct 8 ms 16656 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 12 ms 17344 KB Output is correct
11 Correct 10 ms 16980 KB Output is correct
12 Correct 20 ms 17108 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 16980 KB Output is correct
15 Correct 9 ms 16980 KB Output is correct
16 Correct 21 ms 17268 KB Output is correct
17 Correct 950 ms 28984 KB Output is correct
18 Execution timed out 1056 ms 29340 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 57420 KB Output is correct
2 Correct 79 ms 57368 KB Output is correct
3 Correct 148 ms 60456 KB Output is correct
4 Correct 111 ms 62208 KB Output is correct
5 Correct 187 ms 70760 KB Output is correct
6 Correct 196 ms 70716 KB Output is correct
7 Correct 165 ms 70856 KB Output is correct
8 Correct 182 ms 70872 KB Output is correct
9 Correct 255 ms 103708 KB Output is correct
10 Correct 157 ms 55808 KB Output is correct
11 Correct 338 ms 95000 KB Output is correct
12 Correct 12 ms 16740 KB Output is correct
13 Correct 10 ms 16736 KB Output is correct
14 Correct 10 ms 16672 KB Output is correct
15 Correct 10 ms 16724 KB Output is correct
16 Correct 10 ms 16656 KB Output is correct
17 Correct 10 ms 16724 KB Output is correct
18 Correct 95 ms 57396 KB Output is correct
19 Correct 86 ms 57320 KB Output is correct
20 Correct 78 ms 57332 KB Output is correct
21 Correct 97 ms 57384 KB Output is correct
22 Correct 277 ms 107076 KB Output is correct
23 Correct 370 ms 121892 KB Output is correct
24 Correct 355 ms 124916 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 72172 KB Output is correct
2 Correct 288 ms 80104 KB Output is correct
3 Correct 77 ms 57424 KB Output is correct
4 Correct 82 ms 57360 KB Output is correct
5 Execution timed out 1097 ms 182508 KB Time limit exceeded
6 Halted 0 ms 0 KB -