oj.uz

Submission #656325

# Submission time Handle Problem Language Result Execution time Memory
656325 2022-11-06T23:56:48 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 129384 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];
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][h0]]-pf[i-1][hr[i-1][h1]]);
            }

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

    // cout << dp[2][hr[4].size()-1][1] << endl;

    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;




    // // dp[i][h1][h] = until i and with h[i-1] = hr[i-1][h1] and h[i] = hr[i][h]

    // // dp[1][0][x] = 0;
    // for(int i = 0; i < hr[1].size(); i++) dp[1][0][i] = 0;
    // for(int i = 2; i <= n; i++) {
    //     for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
    //         for(int h = 0; h < hr[i].size(); h++) {
    //             dp[i][h1][h] = 0;

    //             int plus10 = max((int) 0,pf[i][hr[i-1][h1]]-pf[i][hr[i][h]]);

    //             for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
    //                 // fishs that 0 catchs in 1 and had not been caught by 2
    //                 // I catch every fish between h(i) and max(h(i-1),h(i-2)) + 1
    //                 int plus01 = max((int) 0, pf[i-1][hr[i][h]]-pf[i-1][max(hr[i-1][h1],hr[i-2][h2])]);
    //                 dp[i][h1][h] = max(dp[i][h1][h],dp[i-1][h2][h1]+plus01 + plus10);
    //              }
    //         }
    //     }
    // }

    // int ans = 0;
    // for(int h = 0; h < hr[n].size(); h++) {
    //     for(int h1 = 0; h1 < hr[n-1].size(); h1++) {
    //         ans = max(ans,dp[n][h1][h]);
    //     }
    // }
    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:90: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]
   90 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:101: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]
  101 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 56152 KB Output is correct
2 Correct 259 ms 62944 KB Output is correct
3 Correct 61 ms 40264 KB Output is correct
4 Correct 60 ms 40204 KB Output is correct
5 Execution timed out 1065 ms 129384 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 40204 KB Output is correct
2 Correct 61 ms 40204 KB Output is correct
3 Correct 122 ms 44436 KB Output is correct
4 Correct 91 ms 45052 KB Output is correct
5 Correct 146 ms 53408 KB Output is correct
6 Correct 140 ms 53524 KB Output is correct
7 Correct 156 ms 53524 KB Output is correct
8 Correct 152 ms 53524 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12012 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11996 KB Output is correct
5 Correct 6 ms 12004 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 9 ms 11956 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 12576 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12012 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11996 KB Output is correct
5 Correct 6 ms 12004 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 9 ms 11956 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 12576 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 9 ms 12100 KB Output is correct
16 Correct 19 ms 12372 KB Output is correct
17 Execution timed out 1090 ms 20656 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12012 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11996 KB Output is correct
5 Correct 6 ms 12004 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 9 ms 11956 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 11 ms 12576 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 9 ms 12100 KB Output is correct
16 Correct 19 ms 12372 KB Output is correct
17 Execution timed out 1090 ms 20656 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 40204 KB Output is correct
2 Correct 61 ms 40204 KB Output is correct
3 Correct 122 ms 44436 KB Output is correct
4 Correct 91 ms 45052 KB Output is correct
5 Correct 146 ms 53408 KB Output is correct
6 Correct 140 ms 53524 KB Output is correct
7 Correct 156 ms 53524 KB Output is correct
8 Correct 152 ms 53524 KB Output is correct
9 Correct 191 ms 73916 KB Output is correct
10 Correct 110 ms 41816 KB Output is correct
11 Correct 264 ms 71500 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 12048 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 7 ms 11944 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 7 ms 11988 KB Output is correct
18 Correct 65 ms 40200 KB Output is correct
19 Correct 61 ms 40160 KB Output is correct
20 Correct 59 ms 40140 KB Output is correct
21 Correct 60 ms 40192 KB Output is correct
22 Correct 221 ms 77488 KB Output is correct
23 Correct 312 ms 86756 KB Output is correct
24 Correct 292 ms 88836 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 56152 KB Output is correct
2 Correct 259 ms 62944 KB Output is correct
3 Correct 61 ms 40264 KB Output is correct
4 Correct 60 ms 40204 KB Output is correct
5 Execution timed out 1065 ms 129384 KB Time limit exceeded
6 Halted 0 ms 0 KB -