結果

問題 No.1297 銅像
ユーザー 沙耶花
提出日時 2020-05-02 22:19:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,663 bytes
コンパイル時間 2,888 ms
コンパイル使用メモリ 205,388 KB
最終ジャッジ日時 2025-01-10 06:08:40
ジャッジサーバーID
(参考情報)
judge5 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000000
template <typename T>
struct CHT{
vector<T> v;
vector<T> a,b;
int n;
long long sign;
T init_value;
CHT(vector<T> &x,T iv,long long s=1){
init_value = iv;
sign = s;
v = x;
sort(v.begin(),v.end());
int temp = distance(v.begin(),unique(v.begin(),v.end()));
v.resize(temp);
n=1;
while(true){
if(n>=v.size())break;
n<<=1;
}
v.resize(n,1000000001);
a.resize(2*n,0);
b.resize(2*n,init_value);
}
void add(T A,T B,int start){
int now = start;
while(true){
int ll = (now<<(__builtin_clz(now)-__builtin_clz(n)))-n;
int rr = ll + (n>>(31-__builtin_clz(now))) -1;
int m = (ll+rr)>>1;
bool fl = sign*(A*v[ll]+B)<sign*(a[now]*v[ll]+b[now]);
bool fm = sign*(A*v[m]+B)<sign*(a[now]*v[m]+b[now]);
bool fr = sign*(A*v[rr]+B)<sign*(a[now]*v[rr]+b[now]);
if(fl&&fr){
a[now]=A;
b[now]=B;
break;
}
if(!fl&&!fr){
break;
}
if(fm){
swap(A,a[now]);
swap(B,b[now]);
swap(fl,fr);
}
if(fl){
now<<=1;
}
else{
now<<=1;
now++;
}
}
}
void add_line(T A,T B){
add(A,B,1);
}
void add_segment(T A,T B,T L,T R){
L = distance(v.begin(),lower_bound(v.begin(),v.end(),L));
R = distance(v.begin(),lower_bound(v.begin(),v.end(),R));
if(R==L)return;
L+=n;
R+=n;
while(true){
if(L&1){
add(A,B,L++);
}
if(R&1){
add(A,B,--R);
}
if(L>=R)break;
L>>=1;R>>=1;
}
}
T query(T x){
int now = n + distance(v.begin(),lower_bound(v.begin(),v.end(),x));
T ret = init_value;
while(true){
ret = min(sign*ret,sign*(a[now]*x+b[now]))*sign;
now>>=1;
if(now<=0)break;
}
return ret;
}
void show(){
int n = 1;
for(int i=1;i<a.size();i++){
for(int j=0;j<n;j++){
if(j!=0)cout<<' ';
cout<<a[i+j];
}
cout<<endl;
i+=n-1;
n*=2;
}
}
};
int main(){
int N;
cin>>N;
long long D;
cin>>D;
vector<long long> a(N),b(N);
for(int i=0;i<N;i++){
cin>>a[i]>>b[i];
}
vector<long long> x1(N),x2(N+1);
for(int i=0;i<=N;i++){
if(i!=N)x1[i] = a[i] + D*(i+1);
x2[i] = i;
}
vector<long long> dp1(N+1,Inf),dp2(N+1,Inf);
CHT<long long> C1(x1,Inf),C2(x2,Inf);
dp2[0] = 0;
C1.add_line(0LL,0LL);
for(long long i=1;i<=N;i++){
dp1[i] = (C1.query(a[i-1]+D*i) + a[i-1]*i*2 + i*i*D - i*D + b[i-1]*2)/2;
dp2[i] = min(dp1[i],(C2.query(i) + i*i*D + i*D)/2);
C1.add_line(-2*i,dp2[i]*2 + i*i*D + i*D);
C2.add_line((a[i-1]-i*D)*2,dp1[i]*2+(-a[i-1]*i)*2+i*i*D-i*D);
}
cout<<dp2.back()<<endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0