oj.uz

Submission #781462

# Submission time Handle Problem Language Result Execution time Memory
781462 2023-07-13T06:41:27 Z asdfgrace Rice Hub (IOI11_ricehub) C++17
17 / 100
 210 ms 4976 KB 
#include <bits/stdc++.h>
//#include "ricehub.h"
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
const int INF = 1000000007; //998244353;

int besthub(int R, int L, int X[], i64 B) {
  vector<pair<i64, i64>> at;
  for (int i = 0; i < R; ++i) {
    if (i == 0 || X[i] != X[i - 1]) at.push_back({X[i], 1LL});
    else ++at.back().second;
  }
  int n = (int)at.size();
  // for each city, find maximum number WITHIN BUDGET
  // this can be done greedily
  // if we add in the order of distance from current city
  // we can binary search (yes!!!) for the size of the outer bound
  // nlog^2n probably passes as well
  vector<pair<i64, i64>> pref(n);
  pref[0] = at[0];
  for (int i = 1; i < n; ++i) {
    pref[i].first = pref[i - 1].first + at[i].first;
    pref[i].second = pref[i - 1].second + at[i].second; 
  }
  PAR2(at); PAR2(pref);
  auto cost = [&] (i64 m, int i) -> i64 {
    int lb = lower_bound(at.begin(), at.end(),
                         make_pair(at[i].first - m, 0LL)) - at.begin();
    int rb = upper_bound(at.begin(), at.end(),
                         make_pair(at[i].first + m, 0LL)) - at.begin() - 1;
    i64 ldist = pref[i].first - pref[lb].first + at[lb].first;
    i64 lcnt = pref[i].second - pref[lb].second + at[lb].second;
    i64 rdist = pref[rb].first - pref[i].first + at[i].first;
    i64 rcnt = pref[rb].second - pref[i].second + at[i].second;
    return lcnt * at[i].first - ldist + rdist - rcnt * at[i].first;
  };
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    i64 l = 0, r = L;
    // make sure it COMPLETELY works
    // then we can add on the edges if needed
    while (r > l + 1) {
      i64 m = (l + r) / 2;
      //PV(m);
      //PV(cost(m, i));
      if (cost(m, i) <= B) {
        l = m;
      } else {
        r = m - 1;
      }
    }
    i64 res = (cost(r, i) <= B ? r : l), c = cost(res, i);
    PV(res); PV(c);
    int lb = lower_bound(at.begin(), at.end(),
                         make_pair(at[i].first - res, 0LL)) - at.begin();
    int rb = upper_bound(at.begin(), at.end(),
                         make_pair(at[i].first + res, 0LL)) - at.begin() - 1;
    int cnt = pref[rb].second - pref[lb].second + at[lb].second;
    PV(cnt);
    if (c < B) {
      vector<pair<i64, i64>> extras;
      PV(lb); PV(rb);
      if (lb > 0) extras.push_back(at[lb - 1]);
      if (rb < n - 1) extras.push_back(at[rb + 1]);
      sort(extras.begin(), extras.end(), [&](pair<i64, i64> a, pair<i64, i64> b) {
        return a.first - at[i].first < b.first - at[i].first;
      });
      for (int j = 0; j < (int) extras.size(); ++j) {
        i64 rem = B - c, used = min(rem / abs(extras[j].first - at[i].first), extras[j].second);
        cnt += used;
        c += abs(extras[j].first - at[i].first) * used;
      }
      PAR2(extras); PV(cnt); PV(c);
    }
    ans = max(ans, cnt);
  }
  return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 276 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1228 KB Output is correct
2 Correct 39 ms 1228 KB Output is correct
3 Correct 146 ms 4932 KB Output is correct
4 Correct 210 ms 4976 KB Output is correct
5 Incorrect 5 ms 852 KB Output isn't correct
6 Halted 0 ms 0 KB -