oj.uz

Submission #630109

# Submission time Handle Problem Language Result Execution time Memory
630109 2022-08-15T17:05:27 Z CyanForces Catfish Farm (IOI22_fish) C++17
9 / 100
 454 ms 62524 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];

    {
      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));
      }
    }

    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);
      //  }
      //}

      {
        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-2]) && at_dp[i-2][jp] <= h_cur) {
            int h_prev = at_dp[i-2][jp];
            assert(h_prev <= h_cur);
            smax(opt, prev[jp] + fish(i-1,0,h_prev));
            ++jp;
          }
          smax(cur_inc[j], opt);
          smax(cur_dec[j], opt);
        }
      }
      {
        int jp = sz(prev);
        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-2][jp-1] >= h_cur) {
            --jp;
            int h_prev = at_dp[i-2][jp];
            assert(h_prev >= h_cur);
            smax(opt, prev[jp]);
          }
          smax(cur_dec[j], opt + fish(i,0,h_cur));
          smax(cur_inc[j], opt + fish(i,0,h_cur));
        }
      }
    }
  }

  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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29092 KB Output is correct
2 Correct 129 ms 33156 KB Output is correct
3 Correct 45 ms 24552 KB Output is correct
4 Correct 44 ms 24544 KB Output is correct
5 Correct 337 ms 59328 KB Output is correct
6 Correct 454 ms 62524 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 183 ms 37976 KB Output is correct
3 Correct 237 ms 44756 KB Output is correct
4 Correct 88 ms 29320 KB Output is correct
5 Correct 108 ms 33552 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 280 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 47 ms 24524 KB Output is correct
11 Correct 45 ms 24468 KB Output is correct
12 Correct 113 ms 31296 KB Output is correct
13 Correct 137 ms 36004 KB Output is correct
14 Correct 106 ms 30372 KB Output is correct
15 Correct 135 ms 33728 KB Output is correct
16 Correct 116 ms 30412 KB Output is correct
17 Correct 115 ms 33640 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24508 KB Output is correct
2 Correct 48 ms 24476 KB Output is correct
3 Incorrect 130 ms 27104 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19090957524280'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '179595352383'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '179595352383'
10 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 Incorrect 1 ms 340 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '179595352383'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24508 KB Output is correct
2 Correct 48 ms 24476 KB Output is correct
3 Incorrect 130 ms 27104 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19090957524280'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29092 KB Output is correct
2 Correct 129 ms 33156 KB Output is correct
3 Correct 45 ms 24552 KB Output is correct
4 Correct 44 ms 24544 KB Output is correct
5 Correct 337 ms 59328 KB Output is correct
6 Correct 454 ms 62524 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 183 ms 37976 KB Output is correct
9 Correct 237 ms 44756 KB Output is correct
10 Correct 88 ms 29320 KB Output is correct
11 Correct 108 ms 33552 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 280 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 47 ms 24524 KB Output is correct
17 Correct 45 ms 24468 KB Output is correct
18 Correct 113 ms 31296 KB Output is correct
19 Correct 137 ms 36004 KB Output is correct
20 Correct 106 ms 30372 KB Output is correct
21 Correct 135 ms 33728 KB Output is correct
22 Correct 116 ms 30412 KB Output is correct
23 Correct 115 ms 33640 KB Output is correct
24 Correct 44 ms 24508 KB Output is correct
25 Correct 48 ms 24476 KB Output is correct
26 Incorrect 130 ms 27104 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '19090957524280'
27 Halted 0 ms 0 KB -