oj.uz

Submission #656344

# Submission time Handle Problem Language Result Execution time Memory
656344 2022-11-07T01:16:15 Z Lobo Catfish Farm (IOI22_fish) C++17
15 / 100
 1000 ms 261632 KB 
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3","unroll-loops")
// #define int long long
#define ll 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 inf = 1e18+10;

int n, m;
vector<vector<ll>> dp[maxn];
map<int,ll> pf[maxn], pfmx0[maxn], pfmx1[maxn], sfmx0[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 h0 = 0; h0 < hr[1].size(); h0++) {
        dp[1][h0][0] = 0;
        dp[1][h0][1] = 0;
        pfmx0[1][hr[1][h0]] = max(pfmx0[1][hr[1][h0]],dp[1][h0][0]-pf[1][hr[1][h0]]);
        sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][0]+pf[1+1][hr[1][h0]]);
        sfmx0[1][hr[1][h0]] = max(sfmx0[1][hr[1][h0]],dp[1][h0][1]+pf[1+1][hr[1][h0]]);
    }

    for(auto j : hr[2]) {
        pfmx0[1][j] = max(pfmx0[1][j],0LL);
    }
    for(auto it = next(pfmx0[1].begin()); it != pfmx0[1].end(); it++) {
        it->sc = max(it->sc,prev(it)->sc);
    }

    for(auto j : hr[2]) {
        sfmx0[1][j] = max(sfmx0[1][j],0LL);
    }
    auto it = prev(prev(sfmx0[1].end()));
    while(true) {
        it->sc = max(it->sc,next(it)->sc);
        if(it == sfmx0[1].begin()) break;
        it = prev(it);
    }

    for(int i = 2; i <= n; i++) {
        for(int h0 = 0; h0 < hr[i].size(); h0++) {
            // It's greater than the previous
            auto it = prev(upper_bound(all(hr[i-1]),hr[i][h0]));
            dp[i][h0][0] = pfmx0[i-1][*it] + pf[i-1][hr[i][h0]];

            if(i != 2) {
                it = prev(upper_bound(all(hr[i-2]),hr[i][h0]));
                dp[i][h0][0] = max(dp[i][h0][0],pfmx1[i-2][*it] + pf[i-1][hr[i][h0]]);
            }

            // It's smaller than the previous
            dp[i][h0][1] = sfmx0[i-1][hr[i][h0]] - pf[i][hr[i][h0]];

            pfmx0[i][hr[i][h0]] = max(pfmx0[i][hr[i][h0]],dp[i][h0][0]-pf[i][hr[i][h0]]);
            pfmx1[i][hr[i][h0]] = max(pfmx1[i][hr[i][h0]],max(dp[i][h0][1],dp[i][h0][0]));
            sfmx0[i][hr[i][h0]] = max(sfmx0[i][hr[i][h0]],max(dp[i][h0][0],dp[i][h0][1])+pf[i+1][hr[i][h0]]);
        }
        for(auto it = next(pfmx0[i].begin()); it != pfmx0[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }

        for(auto j : hr[i+2]) {
            pfmx1[i][j] = max(pfmx1[i][j],0LL);
        }
        for(auto it = next(pfmx1[i].begin()); it != pfmx1[i].end(); it++) {
            it->sc = max(it->sc,prev(it)->sc);
        }
        auto it = prev(prev(sfmx0[i].end()));
        while(true) {
            it->sc = max(it->sc,next(it)->sc);
            if(it == sfmx0[i].begin()) break;
            it = prev(it);
        }
    }

    ll 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:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0; j < hr[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~
fish.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int h0 = 0; h0 < hr[1].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~
fish.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(int h0 = 0; h0 < hr[i].size(); h0++) {
      |                         ~~~^~~~~~~~~~~~~~
fish.cpp:127:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int h0 = 0; h0 < hr[n].size(); h0++) {
      |                     ~~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 113336 KB Output is correct
2 Correct 335 ms 125944 KB Output is correct
3 Correct 108 ms 91792 KB Output is correct
4 Correct 108 ms 91868 KB Output is correct
5 Execution timed out 1092 ms 261632 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26068 KB Output is correct
2 Correct 542 ms 142592 KB Output is correct
3 Correct 669 ms 160024 KB Output is correct
4 Correct 274 ms 113204 KB Output is correct
5 Correct 319 ms 125976 KB Output is correct
6 Correct 13 ms 26068 KB Output is correct
7 Correct 14 ms 26068 KB Output is correct
8 Correct 14 ms 26056 KB Output is correct
9 Correct 12 ms 26036 KB Output is correct
10 Correct 113 ms 91748 KB Output is correct
11 Correct 110 ms 91844 KB Output is correct
12 Correct 400 ms 133700 KB Output is correct
13 Correct 482 ms 150964 KB Output is correct
14 Correct 321 ms 123548 KB Output is correct
15 Correct 349 ms 123716 KB Output is correct
16 Correct 353 ms 123548 KB Output is correct
17 Correct 366 ms 134312 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 91868 KB Output is correct
2 Correct 109 ms 91768 KB Output is correct
3 Correct 137 ms 91580 KB Output is correct
4 Correct 132 ms 96088 KB Output is correct
5 Correct 191 ms 103588 KB Output is correct
6 Correct 194 ms 103592 KB Output is correct
7 Correct 187 ms 103544 KB Output is correct
8 Correct 178 ms 103616 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26020 KB Output is correct
2 Correct 12 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 12 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 12 ms 26056 KB Output is correct
9 Correct 13 ms 26324 KB Output is correct
10 Correct 18 ms 27092 KB Output is correct
11 Incorrect 14 ms 26452 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278117792498'
12 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26020 KB Output is correct
2 Correct 12 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 12 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 12 ms 26056 KB Output is correct
9 Correct 13 ms 26324 KB Output is correct
10 Correct 18 ms 27092 KB Output is correct
11 Incorrect 14 ms 26452 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278117792498'
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26020 KB Output is correct
2 Correct 12 ms 26068 KB Output is correct
3 Correct 13 ms 26068 KB Output is correct
4 Correct 12 ms 26068 KB Output is correct
5 Correct 13 ms 26068 KB Output is correct
6 Correct 12 ms 26068 KB Output is correct
7 Correct 13 ms 26068 KB Output is correct
8 Correct 12 ms 26056 KB Output is correct
9 Correct 13 ms 26324 KB Output is correct
10 Correct 18 ms 27092 KB Output is correct
11 Incorrect 14 ms 26452 KB 1st lines differ - on the 1st token, expected: '278622587073', found: '278117792498'
12 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 91868 KB Output is correct
2 Correct 109 ms 91768 KB Output is correct
3 Correct 137 ms 91580 KB Output is correct
4 Correct 132 ms 96088 KB Output is correct
5 Correct 191 ms 103588 KB Output is correct
6 Correct 194 ms 103592 KB Output is correct
7 Correct 187 ms 103544 KB Output is correct
8 Correct 178 ms 103616 KB Output is correct
9 Correct 309 ms 155188 KB Output is correct
10 Correct 148 ms 82480 KB Output is correct
11 Correct 306 ms 138816 KB Output is correct
12 Correct 13 ms 26068 KB Output is correct
13 Correct 12 ms 26140 KB Output is correct
14 Correct 13 ms 26068 KB Output is correct
15 Correct 15 ms 26068 KB Output is correct
16 Correct 13 ms 26108 KB Output is correct
17 Correct 12 ms 26092 KB Output is correct
18 Correct 106 ms 91868 KB Output is correct
19 Correct 106 ms 91860 KB Output is correct
20 Correct 107 ms 91768 KB Output is correct
21 Correct 106 ms 91772 KB Output is correct
22 Incorrect 320 ms 158644 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '44736941582713'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 113336 KB Output is correct
2 Correct 335 ms 125944 KB Output is correct
3 Correct 108 ms 91792 KB Output is correct
4 Correct 108 ms 91868 KB Output is correct
5 Execution timed out 1092 ms 261632 KB Time limit exceeded
6 Halted 0 ms 0 KB -