oj.uz

Submission #630096

# Submission time Handle Problem Language Result Execution time Memory
630096 2022-08-15T16:52:46 Z CyanForces Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 49452 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));
      }
    }

    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 93 ms 29444 KB Output is correct
2 Correct 97 ms 33648 KB Output is correct
3 Correct 50 ms 24552 KB Output is correct
4 Correct 47 ms 24660 KB Output is correct
5 Execution timed out 1075 ms 49452 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24468 KB Output is correct
2 Correct 50 ms 24524 KB Output is correct
3 Correct 103 ms 27416 KB Output is correct
4 Correct 81 ms 28136 KB Output is correct
5 Correct 205 ms 34172 KB Output is correct
6 Correct 166 ms 34164 KB Output is correct
7 Correct 173 ms 34316 KB Output is correct
8 Correct 177 ms 34332 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 0 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 348 KB Output is correct
10 Correct 9 ms 696 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 444 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 1 ms 260 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 0 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 348 KB Output is correct
10 Correct 9 ms 696 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 444 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 55 ms 588 KB Output is correct
17 Execution timed out 1085 ms 5288 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 224 KB Output is correct
3 Correct 0 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 348 KB Output is correct
10 Correct 9 ms 696 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 444 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 55 ms 588 KB Output is correct
17 Execution timed out 1085 ms 5288 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24468 KB Output is correct
2 Correct 50 ms 24524 KB Output is correct
3 Correct 103 ms 27416 KB Output is correct
4 Correct 81 ms 28136 KB Output is correct
5 Correct 205 ms 34172 KB Output is correct
6 Correct 166 ms 34164 KB Output is correct
7 Correct 173 ms 34316 KB Output is correct
8 Correct 177 ms 34332 KB Output is correct
9 Correct 218 ms 34220 KB Output is correct
10 Correct 192 ms 23936 KB Output is correct
11 Correct 376 ms 47044 KB Output is correct
12 Correct 1 ms 220 KB Output is correct
13 Correct 0 ms 220 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 220 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 216 KB Output is correct
18 Correct 45 ms 24504 KB Output is correct
19 Correct 40 ms 24576 KB Output is correct
20 Correct 41 ms 24460 KB Output is correct
21 Correct 46 ms 24536 KB Output is correct
22 Correct 203 ms 34004 KB Output is correct
23 Correct 386 ms 45700 KB Output is correct
24 Correct 374 ms 47332 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 29444 KB Output is correct
2 Correct 97 ms 33648 KB Output is correct
3 Correct 50 ms 24552 KB Output is correct
4 Correct 47 ms 24660 KB Output is correct
5 Execution timed out 1075 ms 49452 KB Time limit exceeded
6 Halted 0 ms 0 KB -