結果
問題 | No.952 危険な火薬庫 |
ユーザー | tarattata1 |
提出日時 | 2019-12-15 22:22:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 2,723 bytes |
コンパイル時間 | 630 ms |
コンパイル使用メモリ | 81,476 KB |
実行使用メモリ | 71,964 KB |
最終ジャッジ日時 | 2023-09-15 15:46:43 |
合計ジャッジ時間 | 3,402 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 135 ms
58,812 KB |
testcase_04 | AC | 133 ms
58,784 KB |
testcase_05 | AC | 106 ms
52,680 KB |
testcase_06 | AC | 163 ms
64,988 KB |
testcase_07 | AC | 53 ms
38,300 KB |
testcase_08 | AC | 188 ms
69,104 KB |
testcase_09 | AC | 190 ms
69,032 KB |
testcase_10 | AC | 71 ms
44,460 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 76 ms
46,500 KB |
testcase_13 | AC | 79 ms
46,460 KB |
testcase_14 | AC | 19 ms
23,884 KB |
testcase_15 | AC | 119 ms
56,720 KB |
testcase_16 | AC | 24 ms
26,012 KB |
testcase_17 | AC | 20 ms
23,884 KB |
testcase_18 | AC | 33 ms
30,096 KB |
testcase_19 | AC | 3 ms
5,476 KB |
testcase_20 | AC | 3 ms
5,472 KB |
testcase_21 | AC | 68 ms
44,404 KB |
testcase_22 | AC | 16 ms
19,796 KB |
testcase_23 | AC | 3 ms
5,412 KB |
testcase_24 | AC | 8 ms
13,684 KB |
testcase_25 | AC | 160 ms
71,964 KB |
ソースコード
#include <stdio.h> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <iterator> #include <assert.h> #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; ll dp[3005][3005]; // dp[i][j] i番目(0,1,..i-1)まで見て、j個閉じている場合の危険度の最小値 int main(int argc, char* argv[]) { int n; scanf("%d%", &n); vector<ll> A(n),S(n+1); int i,j; for(i=0; i<n; i++) { scanf("%lld", &A[i]); S[i+1]=S[i]+A[i]; } vector<ll> a(n+1),b(n+1); const double eps=1e-6; for(j=0; j<=n; j++) { if(j==0) { for(i=0; i<=n; i++) { dp[i][j]=S[i]*S[i]; } } else { vector<pair<double,int> > z; // xの値, xより少し大きいところの直線のindex for(i=j; i<=n; i++) { { // for CHT a[i]=-2*S[i]; b[i]=dp[i-1][j-1]+S[i]*S[i]; while( 1 ) { if(z.empty()) { z.push_back(make_pair(-HUGE_VAL,i)); break; } else { double x0=z.back().first; int id0=z.back().second; double tmp=-(double)(b[i]-b[id0])/(a[i]-a[id0]); if(tmp<x0) { z.pop_back(); } else { z.push_back(make_pair(tmp,i)); break; } } } } if(i>j) { ll tmp=0; if(!z.empty()) { int k=lower_bound(z.begin(), z.end(), make_pair((double)S[i]+eps,-INF))-z.begin(); if(k>0) { k--; int id=z[k].second; tmp=a[id]*S[i]+b[id]; } } dp[i][j]=tmp+S[i]*S[i]; } } } } for(i=0; i<n; i++) { printf("%lld\n", dp[n][n-1-i]); } return 0; }