oj.uz

Submission #652805

# Submission time Handle Problem Language Result Execution time Memory
652805 2022-10-24T15:09:55 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 179900 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][h1][h] = until i and with h[i-1] = hr[i-1][h1] and h[i] = hr[i][h-1]

    // 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:58: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]
   58 |     for(int i = 0; i < hr[i].size(); i++) dp[1][0][i] = 0;
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:60: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]
   60 |         for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~
fish.cpp:61: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]
   61 |             for(int h = 0; h < hr[i].size(); h++) {
      |                            ~~^~~~~~~~~~~~~~
fish.cpp:66: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]
   66 |                 for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
      |                                 ~~~^~~~~~~~~~~~~~~~
fish.cpp:77: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]
   77 |     for(int h = 0; h < hr[n].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~
fish.cpp:78: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]
   78 |         for(int h1 = 0; h1 < hr[n-1].size(); h1++) {
      |                         ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 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 6 ms 9684 KB Output is correct
2 Execution timed out 1096 ms 48380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 138028 KB Output is correct
2 Correct 88 ms 138056 KB Output is correct
3 Correct 129 ms 133556 KB Output is correct
4 Correct 131 ms 142952 KB Output is correct
5 Correct 185 ms 155728 KB Output is correct
6 Correct 182 ms 155184 KB Output is correct
7 Correct 180 ms 155740 KB Output is correct
8 Correct 190 ms 155828 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9592 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 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 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9968 KB Output is correct
10 Correct 11 ms 10324 KB Output is correct
11 Correct 8 ms 9940 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 6 ms 9812 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 6 ms 9592 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 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 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9968 KB Output is correct
10 Correct 11 ms 10324 KB Output is correct
11 Correct 8 ms 9940 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 7 ms 10068 KB Output is correct
16 Incorrect 251 ms 10184 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 6 ms 9592 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 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 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9968 KB Output is correct
10 Correct 11 ms 10324 KB Output is correct
11 Correct 8 ms 9940 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 7 ms 10196 KB Output is correct
15 Correct 7 ms 10068 KB Output is correct
16 Incorrect 251 ms 10184 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 87 ms 138028 KB Output is correct
2 Correct 88 ms 138056 KB Output is correct
3 Correct 129 ms 133556 KB Output is correct
4 Correct 131 ms 142952 KB Output is correct
5 Correct 185 ms 155728 KB Output is correct
6 Correct 182 ms 155184 KB Output is correct
7 Correct 180 ms 155740 KB Output is correct
8 Correct 190 ms 155828 KB Output is correct
9 Correct 247 ms 167868 KB Output is correct
10 Correct 135 ms 87644 KB Output is correct
11 Correct 288 ms 165840 KB Output is correct
12 Correct 5 ms 9700 KB Output is correct
13 Correct 6 ms 9700 KB Output is correct
14 Correct 6 ms 9704 KB Output is correct
15 Correct 7 ms 9684 KB Output is correct
16 Correct 6 ms 9700 KB Output is correct
17 Correct 7 ms 9640 KB Output is correct
18 Correct 90 ms 138112 KB Output is correct
19 Correct 92 ms 138044 KB Output is correct
20 Correct 85 ms 138024 KB Output is correct
21 Correct 86 ms 137976 KB Output is correct
22 Correct 322 ms 171276 KB Output is correct
23 Correct 427 ms 176264 KB Output is correct
24 Correct 418 ms 179900 KB Output is correct

Subtask #8
0 / 16.0

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