oj.uz

Submission #745549

# Submission time Handle Problem Language Result Execution time Memory
745549 2023-05-20T10:54:42 Z doowey Catfish Farm (IOI22_fish) C++17
9 / 100
 272 ms 46100 KB 
#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 10;

vector<int> cand[N];
vector<pii> fish[N];
vector<ll> fish_cum[N];
vector<pii> dp[N];

int fin_index(int id, int h){
    int ii = lower_bound(cand[id].begin(), cand[id].end(), h) - cand[id].begin();
    if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
    else return ii;
}

void maxi(ll &u, ll v){
    u=max(u, v);
}

ll get_sum(int id, ll pre){
    int jj = lower_bound(fish[id].begin(), fish[id].end(), mp(pre + 1, -1ll)) - fish[id].begin();
    jj -- ;
    if(jj < 0) return 0ll;
    return fish_cum[id][jj];
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for(auto &x : X){
        x ++ ;
    } // assume x is in range [1; n]
    for(int i = 0 ; i < m ; i ++ ){
        if(Y[i] > 0){
            cand[X[i]].push_back(Y[i] - 1);
        }
        fish[X[i]].push_back(mp(Y[i], W[i]));
    }
    ll tot;
    for(int i = 0; i <= n; i ++ ){
        cand[i].push_back(n - 1);
        cand[i].push_back(-1);
        sort(cand[i].begin(), cand[i].end());
        dp[i].resize(cand[i].size(), mp(-(ll)1e16, -(ll)1e16));
        sort(fish[i].begin(), fish[i].end());
        for(auto x : fish[i]){
            tot = x.se;
            if(!fish_cum[i].empty()) tot += fish_cum[i].back();
            fish_cum[i].push_back(tot);
        }

    }
    dp[0][0] = mp(0ll,0ll);
    ll meow = 0ll;
    // .fi means increasing direction, .se means decreasing direction
    int las;
    ll val;
    int pp;
    ll take;
    ll current;
    for(int i = 1; i <= n; i ++){
        // ----------------- SAME HEIGHT HANDLING -----------
        for(int j = 0 ;j < cand[i].size(); j ++ ){
            las = fin_index(i - 1, cand[i][j]);
            if(las != -1){
                val = max(dp[i - 1][las].fi, dp[i - 1][las].se);
                maxi(dp[i][j].fi, val);
                maxi(dp[i][j].se, val);
            }
        }

        // DECREASING HEIGHT HANDLING
        pp = cand[i - 1].size() - 1;
        take = 0ll;
        for(int j = cand[i].size() - 1; j >= 0 ; j -- ){
            while(pp >= 0 && cand[i - 1][pp] > cand[i][j]){
                ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
                ll B = get_sum(i, cand[i - 1][pp]);
                current = (ll)max(dp[i - 1][pp].fi, dp[i - 1][pp].se) + (ll)get_sum(i, cand[i - 1][pp]);
                maxi(take, current);
                pp -- ;
            }
            current = take - get_sum(i, cand[i][j]);
            maxi(dp[i][j].se, current);
        }
        // INCREASING HEIGHT HANDLING

        pp = 0; // transition from 0 is different

        take = -(ll)1e18;
        for(int j = 0; j < cand[i].size(); j ++ ){
            while(pp < cand[i - 1].size() && cand[i - 1][pp] < cand[i][j]){
                maxi(take, dp[i - 1][pp].fi - get_sum(i - 1, cand[i - 1][pp]));
                pp ++ ;
            }
            current = take + get_sum(i - 1, cand[i][j]);
            maxi(dp[i][j].fi, current);
            maxi(dp[i][j].se, current);

            maxi(meow, dp[i][j].fi);
            maxi(meow, dp[i][j].se);
        }

        // INCREASING HEIGHT IF PREV IS EMPTY

        pp = 0;
        take = 0ll;
        for(int j = 0 ; j < cand[i].size(); j ++ ){
            while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] < cand[i][j]){
                maxi(take, dp[i - 2][pp].fi);
                maxi(take, dp[i - 2][pp].se);
                pp ++ ;
            }
            current = take + get_sum(i - 1, cand[i][j]);
            maxi(dp[i][j].fi, current);
            maxi(dp[i][j].se, current);
        }
        if(i >= 2){
            pp = cand[i - 2].size() - 1;
            take = 0ll;
            for(int j = cand[i].size() - 1; j >= 0 ; j --  ){
                while(pp >= 0 && cand[i - 2][pp] > cand[i][j]){
                    maxi(take, max(dp[i - 2][pp].fi, dp[i - 2][pp].se) + get_sum(i - 1, cand[i - 2][pp]));
                    pp -- ;
                }
                maxi(dp[i][j].fi, take);
                maxi(dp[i][j].se, take);
            }
        }
    }
    return meow;
}

Compilation message

fish.cpp: In function 'int fin_index(int, int)':
fish.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(ii >= cand[id].size() || cand[id][ii] != h) return -1;
      |        ~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0 ;j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:85:20: warning: unused variable 'A' [-Wunused-variable]
   85 |                 ll A = max(dp[i - 1][pp].fi, dp[i - 1][pp].se);
      |                    ^
fish.cpp:86:20: warning: unused variable 'B' [-Wunused-variable]
   86 |                 ll B = get_sum(i, cand[i - 1][pp]);
      |                    ^
fish.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j = 0; j < cand[i].size(); j ++ ){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(pp < cand[i - 1].size() && cand[i - 1][pp] < cand[i][j]){
      |                   ~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j = 0 ; j < cand[i].size(); j ++ ){
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:117:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             while(i >= 2 && pp < cand[i - 2].size() && cand[i - 2][pp] < cand[i][j]){
      |                             ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22076 KB Output is correct
2 Correct 87 ms 25892 KB Output is correct
3 Correct 27 ms 17492 KB Output is correct
4 Correct 26 ms 17508 KB Output is correct
5 Correct 208 ms 42992 KB Output is correct
6 Correct 272 ms 46100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 135 ms 27704 KB Output is correct
3 Correct 174 ms 34464 KB Output is correct
4 Correct 77 ms 23492 KB Output is correct
5 Correct 89 ms 25820 KB Output is correct
6 Correct 6 ms 9700 KB Output is correct
7 Correct 5 ms 9696 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 27 ms 17504 KB Output is correct
11 Correct 33 ms 17492 KB Output is correct
12 Correct 73 ms 23504 KB Output is correct
13 Correct 86 ms 25944 KB Output is correct
14 Correct 86 ms 23476 KB Output is correct
15 Correct 99 ms 25040 KB Output is correct
16 Correct 75 ms 23660 KB Output is correct
17 Correct 86 ms 25084 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17492 KB Output is correct
2 Correct 34 ms 17496 KB Output is correct
3 Incorrect 53 ms 22224 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 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 5 ms 9684 KB Output is correct
7 Correct 6 ms 9696 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 6 ms 9700 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 8 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 5 ms 9684 KB Output is correct
7 Correct 6 ms 9696 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 6 ms 9700 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 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 8 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 5 ms 9684 KB Output is correct
7 Correct 6 ms 9696 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 6 ms 9700 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17492 KB Output is correct
2 Correct 34 ms 17496 KB Output is correct
3 Incorrect 53 ms 22224 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22076 KB Output is correct
2 Correct 87 ms 25892 KB Output is correct
3 Correct 27 ms 17492 KB Output is correct
4 Correct 26 ms 17508 KB Output is correct
5 Correct 208 ms 42992 KB Output is correct
6 Correct 272 ms 46100 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 135 ms 27704 KB Output is correct
9 Correct 174 ms 34464 KB Output is correct
10 Correct 77 ms 23492 KB Output is correct
11 Correct 89 ms 25820 KB Output is correct
12 Correct 6 ms 9700 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9692 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 27 ms 17504 KB Output is correct
17 Correct 33 ms 17492 KB Output is correct
18 Correct 73 ms 23504 KB Output is correct
19 Correct 86 ms 25944 KB Output is correct
20 Correct 86 ms 23476 KB Output is correct
21 Correct 99 ms 25040 KB Output is correct
22 Correct 75 ms 23660 KB Output is correct
23 Correct 86 ms 25084 KB Output is correct
24 Correct 27 ms 17492 KB Output is correct
25 Correct 34 ms 17496 KB Output is correct
26 Incorrect 53 ms 22224 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
27 Halted 0 ms 0 KB -