제출 #1149296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149296		duckindog	코알라 (JOI13_koala)	C++17	100 / 100	91 ms	5316 KiB

koala

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
const long long MAX = 2'000'000'000'000'000'000;

int k, m, d, cost, n;
int pos[N], add[N];
int mod[N], inv[N];

long long f[N];

namespace IT { 
  long long f[N << 2];
  void build(int s, int l, int r) { 
    f[s] = -MAX;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  }
  void update(int s, int l, int r, int p, long long x) { 
    if (p < l || p > r) return;
    if (l == r) { 
      f[s] = max(f[s], x);
      return;
    }
    int mid = (l + r) >> 1;
    update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
    f[s] = max(f[s << 1], f[s << 1 | 1]);
  }
  long long query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return -MAX;
    if (u <= l && r <= v) return f[s];
    int mid = (l + r) >> 1;
    return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> k >> m >> d >> cost >> n;
  for (int i = 1; i <= n; ++i) cin >> pos[i] >> add[i];
  pos[0] = k, pos[n + 1] = m;
  
  vector<int> allR;
  for (int i = 0; i <= n + 1; ++i) {
    mod[i] = pos[i] % d;
    inv[i] = pos[i] / d; 
    allR.push_back(mod[i]); 
  }
  sort(allR.begin(), allR.end());
  allR.erase(unique(allR.begin(), allR.end()), allR.end());

  auto it = [&](int x) { 
    return upper_bound(allR.begin(), allR.end(), x) - allR.begin();
  };

  IT::build(1, 1, allR.size());
  IT::update(1, 1, allR.size(), it(mod[0]), 1ll * inv[0] * cost);
  fill(f + 1, f + n + 2, -MAX);

  for (int i = 1; i <= n + 1; ++i) { 
    long long subtract = -MAX;
    subtract = max(subtract, IT::query(1, 1, allR.size(), 1, it(mod[i]) - 1));
    subtract = max(subtract, IT::query(1, 1, allR.size(), it(mod[i]), allR.size()) + cost);
    f[i] = -1ll * inv[i] * cost - cost + subtract + add[i];

    IT::update(1, 1, allR.size(), it(mod[i]), 1ll * inv[i] * cost + f[i]);
  }

  cout << f[n + 1] << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50