結果
問題 | No.952 危険な火薬庫 |
ユーザー | kopricky |
提出日時 | 2019-12-15 11:11:27 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 2,608 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 164,752 KB |
実行使用メモリ | 73,912 KB |
最終ジャッジ日時 | 2023-09-15 15:30:07 |
合計ジャッジ時間 | 3,425 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 63 ms
60,768 KB |
testcase_04 | AC | 60 ms
60,680 KB |
testcase_05 | AC | 46 ms
54,456 KB |
testcase_06 | AC | 77 ms
66,940 KB |
testcase_07 | AC | 24 ms
39,664 KB |
testcase_08 | AC | 88 ms
71,116 KB |
testcase_09 | AC | 91 ms
71,220 KB |
testcase_10 | AC | 32 ms
45,916 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 33 ms
48,004 KB |
testcase_13 | AC | 35 ms
48,024 KB |
testcase_14 | AC | 11 ms
24,816 KB |
testcase_15 | AC | 53 ms
58,556 KB |
testcase_16 | AC | 13 ms
27,012 KB |
testcase_17 | AC | 11 ms
24,960 KB |
testcase_18 | AC | 16 ms
31,232 KB |
testcase_19 | AC | 3 ms
5,848 KB |
testcase_20 | AC | 3 ms
5,880 KB |
testcase_21 | AC | 30 ms
45,968 KB |
testcase_22 | AC | 9 ms
20,840 KB |
testcase_23 | AC | 2 ms
5,968 KB |
testcase_24 | AC | 5 ms
14,308 KB |
testcase_25 | AC | 92 ms
73,912 KB |
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF (1LL << 60) #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(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<ll> vl; typedef vector<vi> vvi; typedef vector<vl> vvl; typedef vector<P> vp; typedef vector<double> vd; typedef vector<string> vs; const int MAX_N = 3005; ll sm[MAX_N], dp[MAX_N][MAX_N]; int pos[MAX_N][2]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n){ int a; cin >> a; sm[i+1] = sm[i]+a; } rep(i,n+2) rep(j,n+2) dp[i][j] = INF; dp[0][0] = 0; rep(i,n+1){ dp[i+1][i+1] = 0, pos[i+1][(i+1)&1] = i; rrep(j,i){ srep(k,pos[j][i&1],pos[j+2][(i+1)&1]+1){ const ll res = dp[k][j]+(sm[i]-sm[k])*(sm[i]-sm[k]); if(dp[i+1][j+1] > res) dp[i+1][j+1] = res, pos[j+1][(i+1)&1] = k; } } } rep(i,n) cout << dp[n+1][n-i] << "\n"; return 0; }