結果
問題 | No.1297 銅像 |
ユーザー |
|
提出日時 | 2020-12-03 00:04:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 5,099 bytes |
コンパイル時間 | 1,788 ms |
コンパイル使用メモリ | 169,412 KB |
実行使用メモリ | 14,592 KB |
最終ジャッジ日時 | 2024-09-13 10:55:10 |
合計ジャッジ時間 | 4,623 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#define ll long long#define INF 1000000005#define MOD 1000000007#define EPS 1e-10#define rep(i,n) for(int i=0;i<(int)(n);++i)#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)#define each(a,b) for(const auto& (a): (b))#define all(v) (v).begin(),(v).end()#define len(v) (int)(v).size()#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())#define cmx(x,y) x=max(x,y)#define cmn(x,y) x=min(x,y)#define fi first#define se second#define pb push_back#define show(x) cout<<#x<<" = "<<(x)<<endl#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}using namespace std;template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}template<typename S,typename T,typename U>auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}template<typename S,typename T,typename U>struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};template<typename S,typename T,typename U>auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}typedef pair<int, int> P;typedef pair<ll,ll> pll;typedef TRI<int, int, int> tri;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<double> vd;typedef vector<P> vp;typedef vector<string> vs;const int MAX_N = 100005;#define getchar getchar_unlocked#define putchar putchar_unlockedinline int in() {int n = 0; short c;while ((c = getchar()) >= '0') n = n * 10 + c - '0';return n;}inline ll inll() {ll n = 0; short c;while ((c = getchar()) >= '0') n = n * 10 + c - '0';return n;}inline void out(ll n) {short res[20], i = 0;do { res[i++] = n % 10, n /= 10; } while (n);while (i) putchar(res[--i] + '0');putchar('\n');}template<typename T> class CHT {private:struct node {node *left, *right;static const T inf = numeric_limits<T>::max();T a, b;node() : node(0, inf){}node(const T _a, const T _b): left(nullptr), right(nullptr), a(_a), b(_b){}T f(const T x) const { return a * x + b; }};static void swap(node *x, node *y){std::swap(x->a, y->a), std::swap(x->b, y->b);}void _add_line(node *cur, node *nw, T l, T r){while(true){if(nw->f(l) < cur->f(l)) swap(cur, nw);if(cur->f(r - 1) <= nw->f(r - 1)) break;const T mid = (l + r) / 2;if(cur->f(mid) <= nw->f(mid)){if(!cur->right){cur->right = new node(*nw);break;}else{cur = cur->right, l = mid;}}else{swap(cur, nw);if(!cur->left){cur->left = new node(*nw);break;}else{cur = cur->left, r = mid;}}}}T query(node *cur, const T k, T l, T r) const {T ans = numeric_limits<T>::max();while(cur){ans = min(ans, cur->f(k));const T mid = (l + r) / 2;if(k < mid){cur = cur->left, r = mid;}else{cur = cur->right, l = mid;}}return ans;}void clear(node *cur){if(cur->left) clear(cur->left);if(cur->right) clear(cur->right);delete cur;}const T lpos, rpos;node *root;public:CHT(const T _lpos, const T _rpos) : lpos(_lpos), rpos(_rpos), root(new node()){assert(lpos < rpos);}// ~CHT(){ clear(root); }// f(x) = a * x + b を挿入void add_line(const T a, const T b){node nw(a, b);return _add_line(root, &nw, lpos, rpos);}// x = k での最小値T query(const T k) const {return query(root, k, lpos, rpos);}};const ll MX = 1200000000000LL;ll a[MAX_N], b[MAX_N];int main(){int n = in(), C = in();CHT<ll> x(0, MX), y(0, n+1);rep(i,n) a[i+1] = inll(), b[i+1] = inll();ll p = 0, q = 0;x.add_line(0, 0);srep(i,1,n+1){p = x.query(a[i] + (ll)i * C) + b[i] + i * a[i] + ((ll)i * i - i) * C / 2;y.add_line(a[i] - (ll)i * C, p - (ll)i * a[i] + ((ll)i * i - i) * C / 2);q = y.query(i) + ((ll)i * i + i) * C / 2;x.add_line(-i, q + ((ll)i * i + i) * C / 2);}out(q);return 0;}