Submission #6136881
Source Code Expand
#include<bits/stdc++.h> using namespace std; using Int = long long; //BEGIN CUT HERE template<typename T, typename F> T KnuthYao(int n,F cost){ vector< vector<T> > dp(n,vector<T>(n)); vector< vector<int> > ar(n,vector<int>(n)); for(int i=0;i<n;i++) dp[i][i]=T(0),ar[i][i]=i; for(int w=1;w<n;w++){ for(int i=0;i+w<n;i++){ int j=i+w; int p=ar[i][j-1],q=ar[i+1][j]; dp[i][j]=dp[i][p]+dp[p+1][j]+cost(i,p,j); ar[i][j]=p; for(int k=p;k<=q&&k+1<=j;k++){ T res=dp[i][k]+dp[k+1][j]+cost(i,k,j); if(res<dp[i][j]) dp[i][j]=res,ar[i][j]=k; } } } return dp[0][n-1]; } //END CUT HERE //INSERT ABOVE HERE signed AOJ_2488(){ using ll = long long; int n; cin>>n; vector<ll> xs(n),ys(n); for(int i=0;i<n;i++) cin>>xs[i]>>ys[i]; auto calc= [&](int i,int k,int j){ return xs[k+1]-xs[i]+ys[k]-ys[j]; }; cout<<KnuthYao<ll>(n,calc)<<endl; return 0; } /* verified on 2018/09/30 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488 */ signed KUPC2012_J(){ using ll = long long; int n; cin>>n; vector<ll> ws(n); for(int i=0;i<n;i++) cin>>ws[i]; vector<ll> sm(n+1); for(int i=0;i<n;i++) sm[i+1]=sm[i]+ws[i]; auto cost=[&](int i,int k,int j){(void) k;return sm[j+1]-sm[i];}; cout<<KnuthYao<ll>(n,cost)<<endl; return 0; } /* verified on 2018/09/30 https://atcoder.jp/contests/kupc2012/tasks/kupc2012_10 */ signed main(){ //AOJ_2488(); KUPC2012_J(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - 刺身 |
User | beet |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1547 Byte |
Status | AC |
Exec Time | 725 ms |
Memory | 188288 KB |
Judge Result
Set Name | Partial 1 | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 3 / 3 | 97 / 97 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Partial 1 | 00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2 |
All | 00_Teuchi_00, 00_Teuchi_01, 00_alternate_0, 00_alternate_1, 00_alternate_2, 00_alternate_3, 00_alternate_4, 00_alternate_5, 00_random_0, 00_random_1, 00_random_2, 00_random_3, 00_random_4, 00_random_5, 00_random_6, 00_random_7, 00_random_8, 00_sample_00, 00_sample_01, 00_sample_02, 00_sorted_0, 00_sorted_1, 00_sorted_2, 20_random_11, 20_random_12, 40_alternate_6, 40_alternate_7, 40_alternate_8, 40_alternate_9, 40_random_10, 40_random_13, 40_random_14, 40_random_15, 40_random_16, 40_random_17, 40_random_18, 40_random_19, 40_random_9, 40_sorted_3, 40_sorted_4, 40_sorted_5, 99_Teuchi_00, 99_Teuchi_01, 99_Teuchi_02 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_Teuchi_00 | AC | 1 ms | 384 KB |
00_Teuchi_01 | AC | 1 ms | 384 KB |
00_alternate_0 | AC | 1 ms | 256 KB |
00_alternate_1 | AC | 1 ms | 256 KB |
00_alternate_2 | AC | 1 ms | 256 KB |
00_alternate_3 | AC | 1 ms | 384 KB |
00_alternate_4 | AC | 1 ms | 384 KB |
00_alternate_5 | AC | 1 ms | 384 KB |
00_random_0 | AC | 1 ms | 256 KB |
00_random_1 | AC | 1 ms | 256 KB |
00_random_2 | AC | 1 ms | 256 KB |
00_random_3 | AC | 1 ms | 256 KB |
00_random_4 | AC | 1 ms | 256 KB |
00_random_5 | AC | 1 ms | 256 KB |
00_random_6 | AC | 1 ms | 256 KB |
00_random_7 | AC | 1 ms | 256 KB |
00_random_8 | AC | 1 ms | 256 KB |
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sorted_0 | AC | 1 ms | 384 KB |
00_sorted_1 | AC | 1 ms | 384 KB |
00_sorted_2 | AC | 1 ms | 384 KB |
20_random_11 | AC | 134 ms | 49536 KB |
20_random_12 | AC | 135 ms | 49536 KB |
40_alternate_6 | AC | 666 ms | 188160 KB |
40_alternate_7 | AC | 663 ms | 188160 KB |
40_alternate_8 | AC | 596 ms | 188160 KB |
40_alternate_9 | AC | 604 ms | 188160 KB |
40_random_10 | AC | 644 ms | 188160 KB |
40_random_13 | AC | 654 ms | 188288 KB |
40_random_14 | AC | 652 ms | 188288 KB |
40_random_15 | AC | 654 ms | 188160 KB |
40_random_16 | AC | 653 ms | 188160 KB |
40_random_17 | AC | 666 ms | 188160 KB |
40_random_18 | AC | 665 ms | 188160 KB |
40_random_19 | AC | 663 ms | 188160 KB |
40_random_9 | AC | 641 ms | 188160 KB |
40_sorted_3 | AC | 645 ms | 188160 KB |
40_sorted_4 | AC | 642 ms | 188160 KB |
40_sorted_5 | AC | 632 ms | 188160 KB |
99_Teuchi_00 | AC | 667 ms | 188160 KB |
99_Teuchi_01 | AC | 717 ms | 188160 KB |
99_Teuchi_02 | AC | 725 ms | 188160 KB |