oj.uz

답안 #745578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745578 2023-05-20T12:23:11 Z doowey 메기 농장 (IOI22_fish) C++17
9 / 100
 296 ms 42664 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)1e18, -(ll)1e18));
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 22356 KB Output is correct
2 Correct 90 ms 24640 KB Output is correct
3 Correct 28 ms 17468 KB Output is correct
4 Correct 30 ms 17492 KB Output is correct
5 Correct 231 ms 39348 KB Output is correct
6 Correct 296 ms 42664 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 145 ms 28212 KB Output is correct
3 Correct 173 ms 31412 KB Output is correct
4 Correct 81 ms 22552 KB Output is correct
5 Correct 97 ms 24664 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 5 ms 9684 KB Output is correct
10 Correct 27 ms 17520 KB Output is correct
11 Correct 28 ms 17504 KB Output is correct
12 Correct 73 ms 22588 KB Output is correct
13 Correct 91 ms 24704 KB Output is correct
14 Correct 90 ms 22788 KB Output is correct
15 Correct 103 ms 24000 KB Output is correct
16 Correct 82 ms 22776 KB Output is correct
17 Correct 82 ms 23928 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 17436 KB Output is correct
2 Correct 28 ms 17492 KB Output is correct
3 Incorrect 53 ms 21524 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9692 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9824 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9696 KB Output is correct
9 Incorrect 6 ms 9708 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9692 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9824 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9696 KB Output is correct
9 Incorrect 6 ms 9708 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9692 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9824 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9696 KB Output is correct
9 Incorrect 6 ms 9708 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '215553967157'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 17436 KB Output is correct
2 Correct 28 ms 17492 KB Output is correct
3 Incorrect 53 ms 21524 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 22356 KB Output is correct
2 Correct 90 ms 24640 KB Output is correct
3 Correct 28 ms 17468 KB Output is correct
4 Correct 30 ms 17492 KB Output is correct
5 Correct 231 ms 39348 KB Output is correct
6 Correct 296 ms 42664 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 145 ms 28212 KB Output is correct
9 Correct 173 ms 31412 KB Output is correct
10 Correct 81 ms 22552 KB Output is correct
11 Correct 97 ms 24664 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 27 ms 17520 KB Output is correct
17 Correct 28 ms 17504 KB Output is correct
18 Correct 73 ms 22588 KB Output is correct
19 Correct 91 ms 24704 KB Output is correct
20 Correct 90 ms 22788 KB Output is correct
21 Correct 103 ms 24000 KB Output is correct
22 Correct 82 ms 22776 KB Output is correct
23 Correct 82 ms 23928 KB Output is correct
24 Correct 28 ms 17436 KB Output is correct
25 Correct 28 ms 17492 KB Output is correct
26 Incorrect 53 ms 21524 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
27 Halted 0 ms 0 KB -