oj.uz

Submission #656327

# Submission time Handle Problem Language Result Execution time Memory
656327 2022-11-07T00:04:24 Z Lobo Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 129436 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-1][h1]] + pf[i-1][hr[i][h0]]);
            }

            if(i != 2) {
                for(int h2 = 0; h2 < hr[i-2].size(); h2++) {
                    if(hr[i-2][h2] > hr[i][h0]) continue;
                    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])]);
                }
            }

            // 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;
}

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:88: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]
   88 |             for(int h1 = 0; h1 < hr[i-1].size(); h1++) {
      |                             ~~~^~~~~~~~~~~~~~~~
fish.cpp:99: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]
   99 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 56256 KB Output is correct
2 Correct 229 ms 62932 KB Output is correct
3 Correct 57 ms 40180 KB Output is correct
4 Correct 61 ms 40156 KB Output is correct
5 Execution timed out 1006 ms 129436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Execution timed out 1100 ms 70232 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 40140 KB Output is correct
2 Correct 59 ms 40112 KB Output is correct
3 Correct 98 ms 44512 KB Output is correct
4 Correct 91 ms 44964 KB Output is correct
5 Correct 148 ms 53404 KB Output is correct
6 Correct 141 ms 53548 KB Output is correct
7 Correct 143 ms 53532 KB Output is correct
8 Correct 145 ms 53404 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 11988 KB Output is correct
3 Correct 6 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12136 KB Output is correct
10 Correct 9 ms 12500 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 7 ms 12084 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 11988 KB Output is correct
3 Correct 6 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12136 KB Output is correct
10 Correct 9 ms 12500 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 7 ms 12084 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 19 ms 12496 KB Output is correct
17 Correct 980 ms 20712 KB Output is correct
18 Execution timed out 1080 ms 21544 KB Time limit exceeded
19 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 11988 KB Output is correct
3 Correct 6 ms 11944 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 11988 KB Output is correct
9 Correct 7 ms 12136 KB Output is correct
10 Correct 9 ms 12500 KB Output is correct
11 Correct 7 ms 12244 KB Output is correct
12 Correct 8 ms 12372 KB Output is correct
13 Correct 7 ms 12084 KB Output is correct
14 Correct 7 ms 12244 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 19 ms 12496 KB Output is correct
17 Correct 980 ms 20712 KB Output is correct
18 Execution timed out 1080 ms 21544 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 40140 KB Output is correct
2 Correct 59 ms 40112 KB Output is correct
3 Correct 98 ms 44512 KB Output is correct
4 Correct 91 ms 44964 KB Output is correct
5 Correct 148 ms 53404 KB Output is correct
6 Correct 141 ms 53548 KB Output is correct
7 Correct 143 ms 53532 KB Output is correct
8 Correct 145 ms 53404 KB Output is correct
9 Correct 190 ms 73964 KB Output is correct
10 Correct 104 ms 41804 KB Output is correct
11 Correct 236 ms 71636 KB Output is correct
12 Correct 6 ms 11988 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 7 ms 11996 KB Output is correct
16 Correct 7 ms 11936 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 63 ms 40324 KB Output is correct
19 Correct 58 ms 40324 KB Output is correct
20 Correct 59 ms 40196 KB Output is correct
21 Correct 59 ms 40180 KB Output is correct
22 Correct 209 ms 77448 KB Output is correct
23 Correct 288 ms 86724 KB Output is correct
24 Correct 286 ms 88780 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 56256 KB Output is correct
2 Correct 229 ms 62932 KB Output is correct
3 Correct 57 ms 40180 KB Output is correct
4 Correct 61 ms 40156 KB Output is correct
5 Execution timed out 1006 ms 129436 KB Time limit exceeded
6 Halted 0 ms 0 KB -