oj.uz

Submission #630107

# Submission time Handle Problem Language Result Execution time Memory
630107 2022-08-15T17:01:11 Z CyanForces Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 48660 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vi;
typedef long double ld;


bool smin(auto &a, auto&& b) { return (b < a) ? (a = b, 1) : 0; } 
bool smax(auto &a, auto&& b) { return (a < b) ? (a = b, 1) : 0; } 

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
    std::vector<int> W) {

  int n = N, m = M;
  vi x(all(X)), y(all(Y));
  vi w(all(W));

  vector<vi> at_x(n);
  vector<vi> at_dp(n);
  rep(i,0,n) at_dp[i].emplace_back(-1);
  rep(i,0,m) {
    at_x[x[i]].emplace_back(i);
    if(x[i]) at_dp[x[i]-1].emplace_back(y[i]);
    if(x[i]+1 < n) at_dp[x[i]+1].emplace_back(y[i]);
  }
  rep(i,0,n) sort(all(at_dp[i]));

  vector<vi> at_x_pref(n);
  rep(i,0,n) {
    sort(all(at_x[i]), [&](int a, int b) { return y[a] < y[b]; });
    at_x_pref[i].resize(sz(at_x[i])+1);
    rep(j,0,sz(at_x[i])) at_x_pref[i][j+1] = at_x_pref[i][j] + w[at_x[i][j]];
  }

  auto fish_ = [&](int x, int h) -> ll { // exclusive
    int l = -1, r = sz(at_x[x]);
    while(l+1 < r) {
      int m = (l+r)/2;
      if(h <= y[at_x[x][m]]) r = m;
      else l = m;
    }
    return at_x_pref[x][r];
  };

  auto fish = [&](int x, int h0, int h1) -> ll { // inclusive
    ll res2 = fish_(x,h1+1) - fish_(x,h0);
    //ll res = 0;
    //for(int i : at_x[x]) if(h0 <= y[i] && y[i] <= h1) res += w[i];
    //assert(res == res2);
    return res2;
  };

  vector<vi> dp_inc(n), dp_dec(n);
  rep(i,0,n) {
    vi& cur_inc = dp_inc[i];
    vi& cur_dec = dp_dec[i];
    cur_inc.assign(sz(at_dp[i]),0);
    cur_dec.assign(sz(at_dp[i]),0);

    if(i == 0) continue;

    vi& prev_inc = dp_inc[i-1];
    vi& prev_dec = dp_dec[i-1];

    //rep(j,0,sz(cur_inc)) {
    //  rep(jp,0,sz(prev_inc)) {
    //    int h_cur = at_dp[i][j];
    //    int h_prev = at_dp[i-1][jp];
    //    if(h_prev > h_cur) continue;
    //    smax(cur_inc[j], prev_inc[jp] + fish(i-1,h_prev+1,h_cur));
    //  }
    //}

    {
      int jp = 0;
      ll opt = -1e18;
      rep(j,0,sz(cur_inc)) {
        int h_cur = at_dp[i][j];
        while(jp < sz(at_dp[i-1]) && at_dp[i-1][jp] <= h_cur) {
          int h_prev = at_dp[i-1][jp];
          assert(h_prev <= h_cur);
          smax(opt, prev_inc[jp] - fish(i-1,0,h_prev));
          ++jp;
        }
        smax(cur_inc[j], opt + fish(i-1,0,h_cur));
      }
    }

    {
      int jp = sz(prev_dec);
      ll opt = -1e18;
      for(int j = sz(cur_dec)-1; j >= 0; --j) {
        int h_cur = at_dp[i][j];
        while(jp && at_dp[i-1][jp-1] >= h_cur) {
          --jp;
          int h_prev = at_dp[i-1][jp];
          assert(h_prev >= h_cur);
          smax(opt, max(prev_dec[jp], prev_inc[jp]) + fish(i,0,h_prev));
        }
        smax(cur_dec[j], opt - fish(i,0,h_cur));
      }
    }

    //rep(j,0,sz(cur_dec)) {
    //  rep(jp,0,sz(prev_dec)) {
    //    int h_cur = at_dp[i][j];
    //    int h_prev = at_dp[i-1][jp];
    //    if(h_prev < h_cur) continue;
    //    smax(cur_dec[j], prev_dec[jp] + fish(i,h_cur+1,h_prev));
    //  }
    //}

    //rep(j,0,sz(cur_dec)) {
    //  rep(jp,0,sz(prev_inc)) {
    //    int h_cur = at_dp[i][j];
    //    int h_prev = at_dp[i-1][jp];
    //    if(h_prev < h_cur) continue;
    //    smax(cur_dec[j], prev_inc[jp] + fish(i,h_cur+1,h_prev));
    //  }
    //}

    if(i == 1) continue;

    for(auto prev : {dp_inc[i-2], dp_dec[i-2]}) {
      rep(j,0,sz(at_dp[i])) {
        rep(jp,0,sz(prev)) {
          int h_cur = at_dp[i][j];
          int h_prev = at_dp[i-2][jp];
          ll q = prev[jp] + fish(i-1,0,max(h_prev, h_cur));
          smax(cur_inc[j], q);
          smax(cur_dec[j], q);
        }
      }
    }
  }

  ll ans = 0;
  ans = max(ans, *max_element(all(dp_inc[n-1])));
  ans = max(ans, *max_element(all(dp_dec[n-1])));
  if(n >= 2) {
    rep(jp,0,sz(at_dp[n-2])) {
      int h_prev = at_dp[n-2][jp];
      smax(ans, dp_inc[n-2][jp] + fish(n-1,0,h_prev));
      smax(ans, dp_dec[n-2][jp] + fish(n-1,0,h_prev));
    }
  }

  return ans;
}

Compilation message

fish.cpp:16:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool smin(auto &a, auto&& b) { return (b < a) ? (a = b, 1) : 0; }
      |           ^~~~
fish.cpp:16:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | bool smin(auto &a, auto&& b) { return (b < a) ? (a = b, 1) : 0; }
      |                    ^~~~
fish.cpp:17:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool smax(auto &a, auto&& b) { return (a < b) ? (a = b, 1) : 0; }
      |           ^~~~
fish.cpp:17:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | bool smax(auto &a, auto&& b) { return (a < b) ? (a = b, 1) : 0; }
      |                    ^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 29076 KB Output is correct
2 Correct 99 ms 33272 KB Output is correct
3 Correct 47 ms 24452 KB Output is correct
4 Correct 43 ms 24436 KB Output is correct
5 Execution timed out 1093 ms 48660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1081 ms 34208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24532 KB Output is correct
2 Correct 49 ms 24536 KB Output is correct
3 Correct 117 ms 27048 KB Output is correct
4 Correct 83 ms 27852 KB Output is correct
5 Correct 175 ms 34004 KB Output is correct
6 Correct 196 ms 33928 KB Output is correct
7 Correct 175 ms 33996 KB Output is correct
8 Correct 172 ms 33948 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 468 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 22 ms 524 KB Output is correct
17 Execution timed out 1089 ms 4672 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 22 ms 524 KB Output is correct
17 Execution timed out 1089 ms 4672 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24532 KB Output is correct
2 Correct 49 ms 24536 KB Output is correct
3 Correct 117 ms 27048 KB Output is correct
4 Correct 83 ms 27852 KB Output is correct
5 Correct 175 ms 34004 KB Output is correct
6 Correct 196 ms 33928 KB Output is correct
7 Correct 175 ms 33996 KB Output is correct
8 Correct 172 ms 33948 KB Output is correct
9 Correct 166 ms 33984 KB Output is correct
10 Correct 146 ms 22724 KB Output is correct
11 Correct 319 ms 45408 KB Output is correct
12 Correct 1 ms 220 KB Output is correct
13 Correct 0 ms 220 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 45 ms 24436 KB Output is correct
19 Correct 45 ms 24560 KB Output is correct
20 Correct 44 ms 24552 KB Output is correct
21 Correct 45 ms 24528 KB Output is correct
22 Correct 213 ms 33720 KB Output is correct
23 Correct 339 ms 45376 KB Output is correct
24 Correct 373 ms 45388 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 29076 KB Output is correct
2 Correct 99 ms 33272 KB Output is correct
3 Correct 47 ms 24452 KB Output is correct
4 Correct 43 ms 24436 KB Output is correct
5 Execution timed out 1093 ms 48660 KB Time limit exceeded
6 Halted 0 ms 0 KB -