oj.uz

Submission #656306

# Submission time Handle Problem Language Result Execution time Memory
656306 2022-11-06T23:03:42 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 176956 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, dp[maxn][maxqh][maxqh];
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 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[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:61: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]
   61 |     for(int i = 0; i < hr[1].size(); i++) dp[1][0][i] = 0;
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:63: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]
   63 |         for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~
fish.cpp:64:30: 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 h = 0; h < hr[i].size(); h++) {
      |                            ~~^~~~~~~~~~~~~~
fish.cpp:69: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]
   69 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:80: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]
   80 |     for(int h = 0; h < hr[n].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:81: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]
   81 |         for(int h1 = 0; h1 < hr[n-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 139584 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '148853805980349'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1095 ms 48388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 137980 KB Output is correct
2 Correct 79 ms 138108 KB Output is correct
3 Correct 129 ms 132844 KB Output is correct
4 Correct 105 ms 142792 KB Output is correct
5 Correct 151 ms 154388 KB Output is correct
6 Correct 147 ms 154512 KB Output is correct
7 Correct 161 ms 154444 KB Output is correct
8 Correct 149 ms 154392 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 6 ms 9936 KB Output is correct
12 Correct 8 ms 10228 KB Output is correct
13 Correct 5 ms 9824 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 6 ms 9936 KB Output is correct
12 Correct 8 ms 10228 KB Output is correct
13 Correct 5 ms 9824 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 6 ms 10068 KB Output is correct
16 Incorrect 194 ms 10040 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '107468939232283'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 5 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 6 ms 9936 KB Output is correct
12 Correct 8 ms 10228 KB Output is correct
13 Correct 5 ms 9824 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 6 ms 10068 KB Output is correct
16 Incorrect 194 ms 10040 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '107468939232283'
17 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 137980 KB Output is correct
2 Correct 79 ms 138108 KB Output is correct
3 Correct 129 ms 132844 KB Output is correct
4 Correct 105 ms 142792 KB Output is correct
5 Correct 151 ms 154388 KB Output is correct
6 Correct 147 ms 154512 KB Output is correct
7 Correct 161 ms 154444 KB Output is correct
8 Correct 149 ms 154392 KB Output is correct
9 Correct 202 ms 166988 KB Output is correct
10 Correct 111 ms 86220 KB Output is correct
11 Correct 234 ms 162908 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9644 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 77 ms 138036 KB Output is correct
19 Correct 77 ms 138060 KB Output is correct
20 Correct 85 ms 138000 KB Output is correct
21 Correct 81 ms 138004 KB Output is correct
22 Correct 262 ms 169676 KB Output is correct
23 Correct 471 ms 175228 KB Output is correct
24 Correct 376 ms 176956 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 139584 KB 1st lines differ - on the 1st token, expected: '40313272768926', found: '148853805980349'
2 Halted 0 ms 0 KB -