oj.uz

Submission #656337

# Submission time Handle Problem Language Result Execution time Memory
656337 2022-11-07T00:42:04 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 212804 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], pfmx1[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;
            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]]);
                // }
                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] = 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]]);
            pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],dp[i][h0][1]);
            pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],dp[i][h0][0]);

        }

        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);
        }
    }


    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:95: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]
   95 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:124: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]
  124 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 93228 KB Output is correct
2 Correct 259 ms 103592 KB Output is correct
3 Correct 92 ms 74572 KB Output is correct
4 Correct 94 ms 74716 KB Output is correct
5 Execution timed out 1106 ms 212804 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21332 KB Output is correct
2 Execution timed out 1098 ms 85116 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 74572 KB Output is correct
2 Correct 93 ms 74532 KB Output is correct
3 Correct 142 ms 76412 KB Output is correct
4 Correct 128 ms 79364 KB Output is correct
5 Correct 184 ms 88080 KB Output is correct
6 Correct 178 ms 87900 KB Output is correct
7 Correct 178 ms 87948 KB Output is correct
8 Correct 183 ms 87920 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21440 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21436 KB Output is correct
4 Correct 10 ms 21332 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21396 KB Output is correct
7 Correct 11 ms 21444 KB Output is correct
8 Correct 10 ms 21332 KB Output is correct
9 Correct 11 ms 21672 KB Output is correct
10 Correct 13 ms 22228 KB Output is correct
11 Correct 11 ms 21716 KB Output is correct
12 Correct 14 ms 21964 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21844 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21440 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21436 KB Output is correct
4 Correct 10 ms 21332 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21396 KB Output is correct
7 Correct 11 ms 21444 KB Output is correct
8 Correct 10 ms 21332 KB Output is correct
9 Correct 11 ms 21672 KB Output is correct
10 Correct 13 ms 22228 KB Output is correct
11 Correct 11 ms 21716 KB Output is correct
12 Correct 14 ms 21964 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21844 KB Output is correct
15 Correct 13 ms 21780 KB Output is correct
16 Correct 21 ms 22228 KB Output is correct
17 Correct 551 ms 37328 KB Output is correct
18 Correct 616 ms 37412 KB Output is correct
19 Correct 362 ms 37476 KB Output is correct
20 Correct 357 ms 36236 KB Output is correct
21 Correct 358 ms 36052 KB Output is correct
22 Execution timed out 1090 ms 48636 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 21440 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Correct 11 ms 21436 KB Output is correct
4 Correct 10 ms 21332 KB Output is correct
5 Correct 10 ms 21332 KB Output is correct
6 Correct 10 ms 21396 KB Output is correct
7 Correct 11 ms 21444 KB Output is correct
8 Correct 10 ms 21332 KB Output is correct
9 Correct 11 ms 21672 KB Output is correct
10 Correct 13 ms 22228 KB Output is correct
11 Correct 11 ms 21716 KB Output is correct
12 Correct 14 ms 21964 KB Output is correct
13 Correct 10 ms 21460 KB Output is correct
14 Correct 12 ms 21844 KB Output is correct
15 Correct 13 ms 21780 KB Output is correct
16 Correct 21 ms 22228 KB Output is correct
17 Correct 551 ms 37328 KB Output is correct
18 Correct 616 ms 37412 KB Output is correct
19 Correct 362 ms 37476 KB Output is correct
20 Correct 357 ms 36236 KB Output is correct
21 Correct 358 ms 36052 KB Output is correct
22 Execution timed out 1090 ms 48636 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 74572 KB Output is correct
2 Correct 93 ms 74532 KB Output is correct
3 Correct 142 ms 76412 KB Output is correct
4 Correct 128 ms 79364 KB Output is correct
5 Correct 184 ms 88080 KB Output is correct
6 Correct 178 ms 87900 KB Output is correct
7 Correct 178 ms 87948 KB Output is correct
8 Correct 183 ms 87920 KB Output is correct
9 Correct 270 ms 133324 KB Output is correct
10 Correct 142 ms 69880 KB Output is correct
11 Correct 289 ms 118528 KB Output is correct
12 Correct 12 ms 21332 KB Output is correct
13 Correct 10 ms 21332 KB Output is correct
14 Correct 11 ms 21320 KB Output is correct
15 Correct 11 ms 21332 KB Output is correct
16 Correct 10 ms 21444 KB Output is correct
17 Correct 11 ms 21332 KB Output is correct
18 Correct 94 ms 74572 KB Output is correct
19 Correct 98 ms 74528 KB Output is correct
20 Correct 95 ms 74712 KB Output is correct
21 Correct 97 ms 74540 KB Output is correct
22 Correct 291 ms 136796 KB Output is correct
23 Correct 392 ms 159940 KB Output is correct
24 Correct 386 ms 165452 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 93228 KB Output is correct
2 Correct 259 ms 103592 KB Output is correct
3 Correct 92 ms 74572 KB Output is correct
4 Correct 94 ms 74716 KB Output is correct
5 Execution timed out 1106 ms 212804 KB Time limit exceeded
6 Halted 0 ms 0 KB -