제출 #949378

#제출 시각아이디문제언어결과실행 시간메모리
949378tnknguyen_수열 (APIO14_sequence)C++14
0 / 100
547 ms16444 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int sz = 1e4 + 5; long long a[sz], s[sz]; int n, k; namespace SUB123{ bool ok(){ return (n <= 200); } void solve(){ vector<vector<int>> f(n+5, vector<int>(k+5, 0)); for(int j=1; j<=k+1; ++j){ for(int i=1; i<=n; ++i){ int L = 0, R = s[n] - s[i]; for(int g=i; g>=j; --g){ L += a[g]; f[i][j] = max(f[i][j], f[g-1][j-1] + (L * R)); } } } cout<<f[n][k+1]; //--------------------- exit(0); } } int f[sz][205]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("main.inp","r",stdin); //freopen("main.out","w",stdout); cin>>n>>k; for(int i=1; i<=n; ++i){ cin>>a[i]; s[i] = s[i-1] + a[i]; } // SUB123::solve(); for(int j=1; j<=k+1; ++j){ for(int i=1; i<=n; ++i){ int L = 0, R = s[n] - s[i]; for(int g=i; g>=j; --g){ L += a[g]; f[i][j] = max(f[i][j], f[g-1][j-1] + (L * R)); } } } cout<<f[n][k+1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...