Submission #38164

#	Time	Username	Problem	Language	Result	Execution time	Memory
38164		szawinis	코알라 (JOI13_koala)	C++14	100 / 100	116 ms	4364 KiB

koala

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 2;
 
ll k, m, d, a, n, t[N], b[N], dp[N];
 
const ll is_query = LLONG_MIN;
struct Seg {
  ll l, r, val;
  bool operator<(const Seg &rhs) const {
    if(rhs.val == is_query) return r < rhs.r;
    return (val > rhs.val || (val == rhs.val && r < rhs.r));
  }
};
struct ModHull : public multiset<Seg> {
  bool bad(iterator it) {
    assert(it != end());
    if(it != begin() && prev(it)->r >= it->r) return true;
    if(next(it) != end() && next(it)->val == it->val) return true;
    return false;
  }
  void update(Seg s) {
    if(s.l > s.r) return;
    auto it = insert(s);
    if(bad(it)) {
      erase(it);
      return;
    }
    while(it != begin() && bad(prev(it))) erase(prev(it));
    while(it != end() && next(it) != end() && bad(next(it))) erase(next(it));
  }
  void update(ll x, ll c) {
    update((Seg){0, x % d, c - a * ceil((long double)-1.0 * x / d)});
    update((Seg){x % d + 1, d - 1,
                 c - a * ceil((long double)1.0 * (d - 1 - x) / d)});
  }
  ll query(ll x) {
    auto it = lower_bound((Seg){x % d, x % d, is_query});
    assert(it != end());
    return it->val - (x / d) * a;
  }
} hull;
 
int main() {
  scanf("%d %d %d %d %d", &k, &m, &d, &a, &n);
  t[0] = k;
  t[n + 1] = m;
  for(int i = 1; i <= n; i++) scanf("%d %d", t + i, b + i);
  fill(dp + 1, dp + n + 2, LLONG_MIN);
  hull.update(t[0], dp[0]);
  for(int i = 1; i <= n + 1; i++) {
    dp[i] = hull.query(t[i]) + b[i];
    hull.update(t[i], dp[i]);
  }
  printf("%lld", dp[n + 1]);
}

Compilation message (stderr)

koala.cpp: In member function 'void ModHull::update(ll, ll)':
koala.cpp:34:30: warning: narrowing conversion of '((long double)c - ((long double)a * std::ceil(((-(long double)x) / (long double)d))))' from 'long double' to 'll {aka long long int}' inside { } [-Wnarrowing]
     update((Seg){0, x % d, c - a * ceil((long double)-1.0 * x / d)});
                              ^
koala.cpp:36:20: warning: narrowing conversion of '((long double)c - ((long double)a * std::ceil(((long double)(d + -1ll - x) / (long double)d))))' from 'long double' to 'll {aka long long int}' inside { } [-Wnarrowing]
                  c - a * ceil((long double)1.0 * (d - 1 - x) / d)});
                    ^
koala.cpp: In function 'int main()':
koala.cpp:46:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   scanf("%d %d %d %d %d", &k, &m, &d, &a, &n);
                                             ^
koala.cpp:46:45: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
koala.cpp:46:45: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll* {aka long long int*}' [-Wformat=]
koala.cpp:46:45: warning: format '%d' expects argument of type 'int*', but argument 5 has type 'll* {aka long long int*}' [-Wformat=]
koala.cpp:46:45: warning: format '%d' expects argument of type 'int*', but argument 6 has type 'll* {aka long long int*}' [-Wformat=]
koala.cpp:49:58: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   for(int i = 1; i <= n; i++) scanf("%d %d", t + i, b + i);
                                                          ^
koala.cpp:49:58: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
koala.cpp:46:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d %d", &k, &m, &d, &a, &n);
                                              ^
koala.cpp:49:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= n; i++) scanf("%d %d", t + i, b + i);
                                                           ^

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