oj.uz

Submission #656336

# Submission time Handle Problem Language Result Execution time Memory
656336 2022-11-07T00:38:09 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 182520 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 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]]);
    }

    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(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]]);
            // }

            dp[i][h0][0] = max(dp[i][h0][0], pfmx0[i-1][hr[i][h0]] + 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(pfmx0[i].begin()); it != pfmx0[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: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]
   64 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:79: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]
   79 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:90: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]
   90 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:99: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]
   99 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:120: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]
  120 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 77192 KB Output is correct
2 Correct 287 ms 86304 KB Output is correct
3 Correct 85 ms 57384 KB Output is correct
4 Correct 81 ms 57376 KB Output is correct
5 Execution timed out 1100 ms 182520 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 57424 KB Output is correct
2 Correct 80 ms 57412 KB Output is correct
3 Correct 113 ms 60480 KB Output is correct
4 Correct 109 ms 62164 KB Output is correct
5 Correct 190 ms 70640 KB Output is correct
6 Correct 161 ms 70632 KB Output is correct
7 Correct 159 ms 70748 KB Output is correct
8 Correct 167 ms 70644 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16656 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 8 ms 16724 KB Output is correct
9 Correct 11 ms 16852 KB Output is correct
10 Correct 14 ms 17408 KB Output is correct
11 Correct 10 ms 17012 KB Output is correct
12 Correct 11 ms 17132 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17088 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16656 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 8 ms 16724 KB Output is correct
9 Correct 11 ms 16852 KB Output is correct
10 Correct 14 ms 17408 KB Output is correct
11 Correct 10 ms 17012 KB Output is correct
12 Correct 11 ms 17132 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17088 KB Output is correct
15 Correct 9 ms 17024 KB Output is correct
16 Correct 18 ms 17364 KB Output is correct
17 Correct 681 ms 28916 KB Output is correct
18 Correct 753 ms 29392 KB Output is correct
19 Correct 428 ms 29360 KB Output is correct
20 Correct 424 ms 28620 KB Output is correct
21 Correct 417 ms 28440 KB Output is correct
22 Execution timed out 1096 ms 38076 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 9 ms 16656 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 9 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 8 ms 16724 KB Output is correct
9 Correct 11 ms 16852 KB Output is correct
10 Correct 14 ms 17408 KB Output is correct
11 Correct 10 ms 17012 KB Output is correct
12 Correct 11 ms 17132 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17088 KB Output is correct
15 Correct 9 ms 17024 KB Output is correct
16 Correct 18 ms 17364 KB Output is correct
17 Correct 681 ms 28916 KB Output is correct
18 Correct 753 ms 29392 KB Output is correct
19 Correct 428 ms 29360 KB Output is correct
20 Correct 424 ms 28620 KB Output is correct
21 Correct 417 ms 28440 KB Output is correct
22 Execution timed out 1096 ms 38076 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 57424 KB Output is correct
2 Correct 80 ms 57412 KB Output is correct
3 Correct 113 ms 60480 KB Output is correct
4 Correct 109 ms 62164 KB Output is correct
5 Correct 190 ms 70640 KB Output is correct
6 Correct 161 ms 70632 KB Output is correct
7 Correct 159 ms 70748 KB Output is correct
8 Correct 167 ms 70644 KB Output is correct
9 Correct 238 ms 103632 KB Output is correct
10 Correct 139 ms 55808 KB Output is correct
11 Correct 261 ms 95008 KB Output is correct
12 Correct 9 ms 16724 KB Output is correct
13 Correct 10 ms 16740 KB Output is correct
14 Correct 9 ms 16724 KB Output is correct
15 Correct 9 ms 16724 KB Output is correct
16 Correct 9 ms 16724 KB Output is correct
17 Correct 9 ms 16672 KB Output is correct
18 Correct 77 ms 57416 KB Output is correct
19 Correct 76 ms 57408 KB Output is correct
20 Correct 77 ms 57392 KB Output is correct
21 Correct 80 ms 57400 KB Output is correct
22 Correct 270 ms 107172 KB Output is correct
23 Correct 379 ms 121864 KB Output is correct
24 Correct 348 ms 124728 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 77192 KB Output is correct
2 Correct 287 ms 86304 KB Output is correct
3 Correct 85 ms 57384 KB Output is correct
4 Correct 81 ms 57376 KB Output is correct
5 Execution timed out 1100 ms 182520 KB Time limit exceeded
6 Halted 0 ms 0 KB -