Submission #994425


Source Code Expand

#include<bits/stdc++.h>

using namespace std;
#define int long long


template< class T >
struct ConvexHullTrick
{
  struct Fraction
  {
    T a, b;

    Fraction(T a, T b) : a(a), b(b)
    {
      if(b < 0) a *= -1, b *= -1;
    }

    bool operator<(const Fraction &r) const
    {
      return a * r.b < r.a * b;
    }
  };

  struct Line
  {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    T operator()(T x) const
    {
      return a * x + b;
    }

    bool operator<(const Line &r) const
    {
      return a != r.a ? a < r.a : b < r.b;
    }
  };

  set< Line > ls;
  set< pair< Fraction, Line>> ip;

  ConvexHullTrick()
  {
    ls.emplace(numeric_limits< T >::min(), 0);
  }

  Fraction intersection(Line l1, Line l2)
  {
    return Fraction(-(l2.b - l1.b), l2.a - l1.a);
  }

  bool need(Line l1, Line l2, Line l3)
  {
    return intersection(l1, l2) < intersection(l2, l3);
  }

  void add(T a, T b)
  {
    Line c(a, b);
    auto r = ls.lower_bound(c);
    auto l = prev(r);
    if(l != ls.begin() && r != ls.end()) {
      if(need(*l, c, *r)) {
        ip.erase(make_pair(intersection(*l, *r), *l));
      } else return;
    }
    while(l != ls.begin() && prev(l) != ls.begin() && !need(*prev(l), *l, c)) {
      ip.erase(make_pair(intersection(*prev(l), *l), *prev(l)));
      ls.erase(l--);
    }
    while(r != ls.end() && next(r) != ls.end() && !need(c, *r, *next(r))) {
      ip.erase(make_pair(intersection(*r, *next(r)), *r));
      ls.erase(r++);
    }
    if(l != ls.begin()) {
      ip.emplace(intersection(*l, c), *l);
    }
    if(r != ls.end()) {
      ip.emplace(intersection(c, *r), c);
    }
    ls.emplace(c);
  }

  T maximum(T x)
  {
    auto it = ip.lower_bound(make_pair(Fraction(x, 1), Line(numeric_limits< T >::min(), numeric_limits< T >::min())));
    Line l = it != ip.end() ? it->second : *ls.rbegin();
    return l(x);
  }
};

const int INF = 1 << 30;

int N, A;

signed main()
{
  cin >> N >> A;

  if(N == 1) {
    cout << 1 << endl;
    return (0);
  }
  if(N <= A) {
    cout << N << endl;
    return (0);
  }

  dp1[0] = 0;
  dp1[1] = 1;
  dp2[1] = 1;

  ConvexHullTrick< long long > cht;
  cht.add(1, 0);

  map< int, int > con;

  for(int j = 2; true; j++) {
    dp1[j] = cht.maximum(j);
    if(dp1[j] >= N) {
      cout << j << endl;
      return (0);
    }
    if(j - A >= 0) {
      int val = cht.maximum(j - A);
      cht.add(val, -val * j);
    }
  }
}

Submission Info

Submission Time
Task E - Cookies
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2541 Byte
Status CE

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:3: error: ‘dp1’ was not declared in this scope
   dp1[0] = 0;
   ^
./Main.cpp:114:3: error: ‘dp2’ was not declared in this scope
   dp2[1] = 1;
   ^