結果
問題 | No.913 木の燃やし方 |
ユーザー | sigma425 |
提出日時 | 2019-10-18 22:28:33 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 314 ms / 3,000 ms |
コード長 | 2,766 bytes |
コンパイル時間 | 2,597 ms |
コンパイル使用メモリ | 207,456 KB |
実行使用メモリ | 11,496 KB |
最終ジャッジ日時 | 2023-09-08 00:18:53 |
合計ジャッジ時間 | 12,284 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 3 ms
4,380 KB |
testcase_04 | AC | 3 ms
4,376 KB |
testcase_05 | AC | 3 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 157 ms
7,548 KB |
testcase_09 | AC | 153 ms
7,528 KB |
testcase_10 | AC | 156 ms
7,552 KB |
testcase_11 | AC | 154 ms
7,448 KB |
testcase_12 | AC | 159 ms
7,796 KB |
testcase_13 | AC | 157 ms
7,596 KB |
testcase_14 | AC | 151 ms
7,552 KB |
testcase_15 | AC | 150 ms
7,232 KB |
testcase_16 | AC | 152 ms
7,552 KB |
testcase_17 | AC | 156 ms
7,444 KB |
testcase_18 | AC | 150 ms
7,528 KB |
testcase_19 | AC | 304 ms
11,496 KB |
testcase_20 | AC | 162 ms
7,924 KB |
testcase_21 | AC | 195 ms
7,760 KB |
testcase_22 | AC | 222 ms
8,000 KB |
testcase_23 | AC | 271 ms
8,516 KB |
testcase_24 | AC | 286 ms
9,584 KB |
testcase_25 | AC | 296 ms
11,344 KB |
testcase_26 | AC | 173 ms
7,816 KB |
testcase_27 | AC | 314 ms
11,436 KB |
testcase_28 | AC | 150 ms
7,868 KB |
testcase_29 | AC | 157 ms
7,752 KB |
testcase_30 | AC | 172 ms
7,816 KB |
testcase_31 | AC | 195 ms
9,840 KB |
testcase_32 | AC | 200 ms
9,896 KB |
testcase_33 | AC | 200 ms
9,896 KB |
testcase_34 | AC | 186 ms
7,708 KB |
testcase_35 | AC | 186 ms
7,920 KB |
testcase_36 | AC | 190 ms
7,716 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){ return o<<"("<<p.fs<<","<<p.sc<<")"; } template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){ o<<"{"; for(const T& v:vc) o<<v<<","; o<<"}"; return o; } using ll = long long; template<class T> using V = vector<T>; template<class T> using VV = vector<vector<T>>; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); } #ifdef LOCAL #define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl #else #define show(x) true #endif struct CHT{ using D = ll; typedef pair<D,D> P; vector<P> deq; int s,sd,t; CHT():s(0),sd(0),t(0){} void add(D a,D b){ //add ax+b a:(広義)単調減少!!! P p(a,b); while(s+1<t&&check(deq[t-2],deq[t-1],p)) t--; if(t == (int)deq.size()) deq.pb(p); deq[t++]=p; } D incr_query(D x){ //x:単調増加の時,これを繰り返し呼ぶ(間にaddが挟まるのはOK) while(s+1<t&&f(deq[s],x)>=f(deq[s+1],x)) s++; return f(deq[s],x); } D decr_query(D x){ //x:単調減少の時,これを繰り返し呼ぶ(間にaddが挟まるのはOK) if(sd>=t) sd=t-1; while(sd+1<t&&f(deq[sd],x)>=f(deq[sd+1],x)) sd++; while(sd>0&&f(deq[sd],x)<f(deq[sd-1],x)) sd--; return f(deq[sd],x); } D query(D x){ int lb=s-1,ub=t-1; while(ub-lb>1){ int m=(lb+ub)/2; if(isright(deq[m],deq[m+1],x)) lb=m; else ub=m; } return f(deq[ub],x); } bool isright(P& a,P& b,D x){ return f(a,x)>=f(b,x); } bool check(P& a,P& b,P& c){ return (b.fs-a.fs)*(c.sc-b.sc)>=(b.sc-a.sc)*(c.fs-b.fs); } D f(P &p,int x){ return p.fs*x+p.sc; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); int N; cin >> N; V<ll> A(N); rep(i,N) cin >> A[i]; V<ll> S(N+1); rep(i,N) S[i+1] = S[i] + A[i]; const ll inf = 1e18; V<ll> ans(N,inf); function<void(int,int)> f = [&](int L,int R){ if(L == R) return; int m = (L+R)/2; //L<=j<=m<=p<i<=R { CHT cht; for(ll j=L;j<=m;j++) cht.add(-j*2,j*j-S[j]); ll mn = inf; for(ll i=R;i>=m+1;i--){ ll val=cht.query(i) + i*i + S[i]; chmin(mn,val); chmin(ans[i-1],mn); } } //L<=j<=p<m<i<=R { CHT cht; for(ll i=m+1;i<=R;i++) cht.add(-i*2,i*i+S[i]); ll mn = inf; for(ll j=L;j<m;j++){ ll val=cht.query(j) + j*j - S[j]; chmin(mn,val); chmin(ans[j],mn); } } f(L,m); f(m+1,R); }; f(0,N); rep(i,N) cout << ans[i] << '\n'; }