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
AC × 23
AC × 44
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