結果
問題 | No.952 危険な火薬庫 |
ユーザー | 👑tozangezan |
提出日時 | 2019-12-22 02:15:44 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 977 ms / 2,000 ms |
コード長 | 4,574 bytes |
コンパイル時間 | 774 ms |
コンパイル使用メモリ | 96,164 KB |
実行使用メモリ | 75,268 KB |
最終ジャッジ日時 | 2023-10-11 11:15:40 |
合計ジャッジ時間 | 10,940 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,352 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,352 KB |
testcase_03 | AC | 643 ms
60,856 KB |
testcase_04 | AC | 629 ms
60,968 KB |
testcase_05 | AC | 503 ms
54,752 KB |
testcase_06 | AC | 768 ms
66,988 KB |
testcase_07 | AC | 260 ms
40,404 KB |
testcase_08 | AC | 863 ms
71,088 KB |
testcase_09 | AC | 879 ms
71,172 KB |
testcase_10 | AC | 347 ms
46,608 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 367 ms
46,540 KB |
testcase_13 | AC | 383 ms
48,532 KB |
testcase_14 | AC | 90 ms
24,016 KB |
testcase_15 | AC | 560 ms
58,916 KB |
testcase_16 | AC | 117 ms
28,112 KB |
testcase_17 | AC | 91 ms
24,000 KB |
testcase_18 | AC | 161 ms
32,204 KB |
testcase_19 | AC | 4 ms
5,580 KB |
testcase_20 | AC | 6 ms
5,536 KB |
testcase_21 | AC | 331 ms
44,496 KB |
testcase_22 | AC | 72 ms
21,868 KB |
testcase_23 | AC | 7 ms
7,632 KB |
testcase_24 | AC | 31 ms
13,720 KB |
testcase_25 | AC | 977 ms
75,268 KB |
ソースコード
// #pragma GCC target("avx") // CPU 処理並列化 // #pragma GCC optimize("O3") // CPU 処理並列化 // #pragma GCC optimize("unroll-loops") // 条件処理の呼び出しを減らす #include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<deque> #include<stack> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<bitset> #include<stdlib.h> #include<cassert> #include<time.h> #include<bitset> #include<numeric> #include<unordered_set> #include<complex> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; const long long d2=(mod+1)/2; const double EPS=1e-10; const double INF=1e+10; const double PI=acos(-1.0); const int C_SIZE = 3100000; const int UF_SIZE = 210000; namespace{ long long fact[C_SIZE]; long long finv[C_SIZE]; long long inv[C_SIZE]; long long Comb(int a,int b){ if(a<b||b<0)return 0; return fact[a]*finv[b]%mod*finv[a-b]%mod; } void init_C(int n){ fact[0]=finv[0]=inv[1]=1; for(int i=2;i<n;i++){ inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; } for(int i=1;i<n;i++){ fact[i]=fact[i-1]*i%mod; finv[i]=finv[i-1]*inv[i]%mod; } } long long pw(long long a,long long b){ if(a<0LL)return 0; if(b<0LL)return 0; long long ret=1; while(b){ if(b%2)ret=ret*a%mod; a=a*a%mod; b/=2; } return ret; } long long pw_mod(long long a,long long b,long long M){ if(a<0LL)return 0; if(b<0LL)return 0; long long ret=1; while(b){ if(b%2)ret=ret*a%M; a=a*a%M; b/=2; } return ret; } int pw_mod_int(int a,int b,int M){ if(a<0)return 0; if(b<0)return 0; int ret=1; while(b){ if(b%2)ret=(long long)ret*a%M; a=(long long)a*a%M; b/=2; } return ret; } int ABS(int a){return max(a,-a);} long long ABS(long long a){return max(a,-a);} double ABS(double a){return max(a,-a);} int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; } int UF[UF_SIZE]; void init_UF(int n){ for(int i=0;i<n;i++)UF[i]=-1; } int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a);b=FIND(b);if(a==b)return; if(UF[a]>UF[b])swap(a,b); UF[a]+=UF[b];UF[b]=a; } } // ここから編集しろ struct LiChaoTree{ typedef long long vint; typedef long long zint; typedef pair<vint,vint> F; static const int seg_sz=4096; static const vint inf=mod*mod; static const zint xinf=mod; vector<zint>x; F segtree[seg_sz*2]; vint func(F a,vint x){ return a.first*x+a.second; } void add_line(int a,int b,int c,F f){ if(segtree[c]==make_pair((vint)0,inf)){ segtree[c]=f; return; } int m=(a+b)/2; zint lx=x[a]; zint mx=x[m]; zint rx=x[b-1]; vint ly1=func(segtree[c],lx); vint my1=func(segtree[c],mx); vint ry1=func(segtree[c],rx); vint ly2=func(f,lx); vint my2=func(f,mx); vint ry2=func(f,rx); if(ly1<=ly2&&ry1<=ry2){ return; } if(ly1>ly2&&ry1>ry2){ segtree[c]=f; return; } if(my1>my2){ swap(segtree[c],f); if(ly1>ly2){ add_line(m,b,c*2+1,f); }else{ add_line(a,m,c*2,f); } return; } if(ly1>ly2){ add_line(a,m,c*2,f); }else{ add_line(m,b,c*2+1,f); } } void add_line(int a,int b,int c,int d,int e,F f){ if(d<=a||b<=c)return; if(c<=a&&b<=d){ add_line(a,b,e,f); return; } add_line(a,(a+b)/2,c,d,e*2,f); add_line((a+b)/2,b,c,d,e*2+1,f); } vint query(zint X){ int zx=lower_bound(x.begin(),x.end(),X)-x.begin(); zx+=seg_sz; vint ret=inf; while(zx){ ret=min(ret,func(segtree[zx],X)); zx/=2; } return ret; } void add_line(F a){ add_line(0,seg_sz,1,a); } void add_line(F a,zint b,zint c){ // add [b,c) int l=lower_bound(x.begin(),x.end(),b)-x.begin(); int r=lower_bound(x.begin(),x.end(),c)-x.begin(); if(l>=r)return; add_line(0,seg_sz,l,r,1,a); } void init(vector<zint>X){ x=vector<zint>(seg_sz,xinf); for(int i=0;i<seg_sz*2;i++){ segtree[i]=make_pair((vint)0,inf); } std::sort(X.begin(),X.end()); for(int i=0;i<X.size();i++){ x[i]=X[i]; } } }; long long p[3100]; long long dp[3100][3100]; long long S[3100]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%lld",p+i); S[i+1]=S[i]+p[i]; } for(int i=1;i<=a;i++){ LiChaoTree lc; vector<long long>x; for(int j=0;j<=a;j++){ x.push_back(S[j]); } lc.init(x); for(int j=0;i+j<=a+1;j++){ if(i!=1||j==0)lc.add_line(make_pair(-2*S[i+j-1],S[i+j-1]*S[i+j-1]+dp[i+j-1][j])); long long tmp=lc.query(S[i+j-1]); dp[i+j][j]=tmp+S[i+j-1]*S[i+j-1]; } } for(int i=1;i<=a;i++){ printf("%lld\n",dp[a+1][i]); } }