oj.uz

Submission #38164

# Submission time Handle Problem Language Result Execution time Memory
38164 2018-01-02T14:31:04 Z szawinis 코알라 (JOI13_koala) C++14
100 / 100
 116 ms 4364 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4364 KB Output is correct
2 Correct 0 ms 4364 KB Output is correct
3 Correct 0 ms 4364 KB Output is correct
4 Correct 0 ms 4364 KB Output is correct
5 Correct 0 ms 4364 KB Output is correct
6 Correct 0 ms 4364 KB Output is correct
7 Correct 0 ms 4364 KB Output is correct
8 Correct 0 ms 4364 KB Output is correct
9 Correct 0 ms 4364 KB Output is correct
10 Correct 0 ms 4364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 4364 KB Output is correct
2 Correct 69 ms 4364 KB Output is correct
3 Correct 46 ms 4364 KB Output is correct
4 Correct 116 ms 4364 KB Output is correct
5 Correct 43 ms 4364 KB Output is correct
6 Correct 33 ms 4364 KB Output is correct
7 Correct 53 ms 4364 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4364 KB Output is correct
2 Correct 76 ms 4364 KB Output is correct
3 Correct 79 ms 4364 KB Output is correct
4 Correct 73 ms 4364 KB Output is correct
5 Correct 49 ms 4364 KB Output is correct
6 Correct 33 ms 4364 KB Output is correct