oj.uz

Submission #656323

# Submission time Handle Problem Language Result Execution time Memory
656323 2022-11-06T23:55:47 Z Lobo Catfish Farm (IOI22_fish) C++17
35 / 100
 245 ms 36176 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 = 1e3+10;
const int maxqh = 12;
const int inf = 1e18+10;

int n, m;
vector<vector<int>> dp[maxn];
// map<int,int> pf[maxn];
int pf[maxn][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;
        // }

        for(int j = 1; j <= n; j++) {
            pf[i][j]+= pf[i][j-1];
        }
    }

    // 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:39: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]
   39 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:69: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]
   69 |     for(int i = 0; i < hr[1].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:75: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]
   75 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:78: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]
   78 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:84: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]
   84 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
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:106: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]
  106 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 17532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 97 ms 36176 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 4 ms 2516 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 2 ms 2388 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 2388 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 4 ms 2516 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 2 ms 2388 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 2388 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 98 ms 7060 KB Output is correct
18 Correct 110 ms 9212 KB Output is correct
19 Correct 83 ms 9156 KB Output is correct
20 Correct 88 ms 9080 KB Output is correct
21 Correct 73 ms 9124 KB Output is correct
22 Correct 245 ms 15720 KB Output is correct
23 Correct 10 ms 3576 KB Output is correct
24 Correct 42 ms 6260 KB Output is correct
25 Correct 2 ms 2388 KB Output is correct
26 Correct 7 ms 3412 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 4 ms 2516 KB Output is correct
11 Correct 1 ms 1236 KB Output is correct
12 Correct 2 ms 2388 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 2388 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 3 ms 988 KB Output is correct
17 Correct 98 ms 7060 KB Output is correct
18 Correct 110 ms 9212 KB Output is correct
19 Correct 83 ms 9156 KB Output is correct
20 Correct 88 ms 9080 KB Output is correct
21 Correct 73 ms 9124 KB Output is correct
22 Correct 245 ms 15720 KB Output is correct
23 Correct 10 ms 3576 KB Output is correct
24 Correct 42 ms 6260 KB Output is correct
25 Correct 2 ms 2388 KB Output is correct
26 Correct 7 ms 3412 KB Output is correct
27 Runtime error 4 ms 980 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 17532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -