library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub beet-aizu/library

:heavy_check_mark: test MaxLineContainer
(test/aoj/2725.linecontainer.test.cpp)

Depends on

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/chminmax.cpp"
#include "../../vector/zip.cpp"
#include "../../convexhulltrick/linecontainer.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  int n,x;
  cin>>n>>x;
  vector<ll> ts(n),ps(n),fs(n);
  for(int i=0;i<n;i++) cin>>ts[i]>>ps[i]>>fs[i];

  auto vt=zip(fs,ps,ts);
  sort(vt.begin(),vt.end());
  for(int i=0;i<n;i++) tie(fs[i],ps[i],ts[i])=vt[i];

  vector<MaxLineContainer<ll>> vh(x+1);

  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=x;j>ts[i];j--){
      if(vh[j-ts[i]].empty()) continue;
      ll val=vh[j-ts[i]].query(fs[i])+ps[i]-fs[i]*fs[i];
      vh[j].add(2*fs[i],val-fs[i]*fs[i]);
      chmax(ans,val);
    }
    vh[ts[i]].add(2*fs[i],ps[i]-fs[i]*fs[i]);
    chmax(ans,ps[i]);
  }

  cout<<ans<<endl;
  return 0;
}
#line 1 "test/aoj/2725.linecontainer.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2725

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "vector/zip.cpp"

#line 3 "vector/zip.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename ...Ts>
decltype(auto) zip(vector<Ts>... args){
  vector<decltype(make_tuple(args[0]...))> res;
  int n=min({args.size()...});
  res.reserve(n);
  for(int i=0;i<n;i++) res.emplace_back(args[i]...);
  return res;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "convexhulltrick/linecontainer.cpp"

#line 3 "convexhulltrick/linecontainer.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
enum Objective{
  MAXIMIZE = +1,
  MINIMIZE = -1,
};

template<typename T>
struct Line {
  mutable T k,m,p;
  bool operator<(const Line&o)const{return k<o.k;}
  bool operator<(T x)const{return p<x;}
};

template<typename T> T lc_inf(){return numeric_limits<T>::max();}
template<> double lc_inf<double>(){return 1/.0;}

template<typename T> T lc_div(T a,T b){return a/b-((a^b)<0 and a%b);}
template<> double lc_div(double a,double b){return a/b;};

template<typename T, Objective objective>
struct LineContainer : multiset<Line<T>, less<>>{
  using super = multiset<Line<T>, less<>>;
  using super::begin,super::end,super::insert,super::erase;
  using super::empty,super::lower_bound;
  const T inf = lc_inf<T>();
  bool insect(typename super::iterator x,typename super::iterator y){
    if(y==end()) return x->p=inf,false;
    if(x->k==y->k) x->p=(x->m>y->m?inf:-inf);
    else x->p=lc_div(y->m-x->m,x->k-y->k);
    return x->p>=y->p;
  }
  void add(T k,T m){
    auto z=insert({k*objective,m*objective,0}),y=z++,x=y;
    while(insect(y,z)) z=erase(z);
    if(x!=begin() and insect(--x,y)) insect(x,y=erase(y));
    while((y=x)!=begin() and (--x)->p>=y->p) insect(x,erase(y));
  }
  T query(T x){
    assert(!empty());
    auto l=*lower_bound(x);
    return (l.k*x+l.m)*objective;
  }
};
template<typename T>
using MinLineContainer = LineContainer<T, Objective::MINIMIZE>;
template<typename T>
using MaxLineContainer = LineContainer<T, Objective::MAXIMIZE>;
//END CUT HERE

#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/2725.linecontainer.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  int n,x;
  cin>>n>>x;
  vector<ll> ts(n),ps(n),fs(n);
  for(int i=0;i<n;i++) cin>>ts[i]>>ps[i]>>fs[i];

  auto vt=zip(fs,ps,ts);
  sort(vt.begin(),vt.end());
  for(int i=0;i<n;i++) tie(fs[i],ps[i],ts[i])=vt[i];

  vector<MaxLineContainer<ll>> vh(x+1);

  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=x;j>ts[i];j--){
      if(vh[j-ts[i]].empty()) continue;
      ll val=vh[j-ts[i]].query(fs[i])+ps[i]-fs[i]*fs[i];
      vh[j].add(2*fs[i],val-fs[i]*fs[i]);
      chmax(ans,val);
    }
    vh[ts[i]].add(2*fs[i],ps[i]-fs[i]*fs[i]);
    chmax(ans,ps[i]);
  }

  cout<<ans<<endl;
  return 0;
}
Back to top page