Submission #6008789
Source Code Expand
#include<iomanip> #include<limits> #include<thread> #include<utility> #include<iostream> #include<string> #include<algorithm> #include<set> #include<map> #include<vector> #include<stack> #include<queue> #include<cmath> #include<numeric> #include<cassert> #include<random> #include<chrono> #include<unordered_set> #include<unordered_map> #include<fstream> #include<list> #include<functional> #include<bitset> #include<complex> #include<tuple> using namespace std; typedef unsigned long long int ull; typedef long long int ll; typedef pair<ll,ll> pll; typedef long double D; typedef complex<D> P; #define F first #define S second const ll E=1e18+7; const ll MOD=1000000007; template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;} template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;} template<typename T,typename U>ostream & operator << (ostream &o,pair<T,U> &A){o<<A.F<<" "<<A.S; return o;} template<typename T>ostream & operator << (ostream &o,vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;} template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;} int main(){ ll N; cin>>N; vector<ll> A(N); cin>>A; for(int i=1;i<N;i++){A[i]+=A[i-1];} auto sum=[&](ll l,ll r){return A[r]-(l==0?0:A[l-1]);}; vector<vector<ll>> dp(N,vector<ll>(N,0)); vector<vector<ll>> K(N,vector<ll>(N,0)); for(int i=0;i<N;i++){dp[i][i]=sum(i,i); K[i][i]=i;} for(int i=1;i<N;i++){ for(int j=0;j+i<N;j++){ dp[j][i+j]=E; ll l=K[j][i+j-1],r=K[j+1][i+j]; for(ll k=l;k<=r;k++){ ll L=dp[j][k]; ll R=(k+1<=i+j?dp[k+1][i+j]:0LL); if(dp[j][i+j]>L+R){ dp[j][i+j]=L+R; K[j][i+j]=k; } } dp[j][i+j]+=sum(j,i+j); } } cout<<dp[0].back()-sum(0,N-1)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - 刺身 |
User | tubuann |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2091 Byte |
Status | AC |
Exec Time | 859 ms |
Memory | 250624 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 | 384 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 | 160 ms | 65920 KB |
20_random_12 | AC | 160 ms | 65920 KB |
40_alternate_6 | AC | 801 ms | 250624 KB |
40_alternate_7 | AC | 799 ms | 250624 KB |
40_alternate_8 | AC | 713 ms | 250624 KB |
40_alternate_9 | AC | 718 ms | 250624 KB |
40_random_10 | AC | 762 ms | 250624 KB |
40_random_13 | AC | 772 ms | 250624 KB |
40_random_14 | AC | 773 ms | 250624 KB |
40_random_15 | AC | 770 ms | 250624 KB |
40_random_16 | AC | 771 ms | 250624 KB |
40_random_17 | AC | 803 ms | 250624 KB |
40_random_18 | AC | 800 ms | 250624 KB |
40_random_19 | AC | 800 ms | 250624 KB |
40_random_9 | AC | 764 ms | 250624 KB |
40_sorted_3 | AC | 760 ms | 250624 KB |
40_sorted_4 | AC | 759 ms | 250624 KB |
40_sorted_5 | AC | 754 ms | 250624 KB |
99_Teuchi_00 | AC | 801 ms | 250624 KB |
99_Teuchi_01 | AC | 837 ms | 250624 KB |
99_Teuchi_02 | AC | 859 ms | 250624 KB |