oj.uz

Submission #656305

# Submission time Handle Problem Language Result Execution time Memory
656305 2022-11-06T23:03:09 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 180996 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[i].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[i].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 291 ms 140988 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 9708 KB Output is correct
2 Execution timed out 1087 ms 51276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 137932 KB Output is correct
2 Correct 75 ms 137960 KB Output is correct
3 Correct 105 ms 133720 KB Output is correct
4 Correct 101 ms 143380 KB Output is correct
5 Correct 146 ms 156044 KB Output is correct
6 Correct 142 ms 155384 KB Output is correct
7 Correct 143 ms 155980 KB Output is correct
8 Correct 149 ms 156000 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9644 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 7 ms 9968 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 7 ms 10248 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9644 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 7 ms 9968 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 7 ms 10248 KB Output is correct
15 Correct 5 ms 10092 KB Output is correct
16 Incorrect 215 ms 10196 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 4 ms 9684 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9644 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 10 ms 10324 KB Output is correct
11 Correct 7 ms 9968 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 5 ms 9804 KB Output is correct
14 Correct 7 ms 10248 KB Output is correct
15 Correct 5 ms 10092 KB Output is correct
16 Incorrect 215 ms 10196 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 74 ms 137932 KB Output is correct
2 Correct 75 ms 137960 KB Output is correct
3 Correct 105 ms 133720 KB Output is correct
4 Correct 101 ms 143380 KB Output is correct
5 Correct 146 ms 156044 KB Output is correct
6 Correct 142 ms 155384 KB Output is correct
7 Correct 143 ms 155980 KB Output is correct
8 Correct 149 ms 156000 KB Output is correct
9 Correct 213 ms 168336 KB Output is correct
10 Correct 116 ms 88084 KB Output is correct
11 Correct 242 ms 166396 KB Output is correct
12 Correct 5 ms 9640 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9700 KB Output is correct
16 Correct 5 ms 9708 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 76 ms 138084 KB Output is correct
19 Correct 73 ms 138064 KB Output is correct
20 Correct 74 ms 138060 KB Output is correct
21 Correct 74 ms 137956 KB Output is correct
22 Correct 248 ms 171792 KB Output is correct
23 Correct 345 ms 178612 KB Output is correct
24 Correct 337 ms 180996 KB Output is correct

Subtask #8
0 / 16.0

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