제출 #1092382

#제출 시각아이디문제언어결과실행 시간메모리
1092382DangKhoizzzz수열 (APIO14_sequence)C++17
11 / 100
2080 ms117332 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; typedef pair<int,int> pii; const int maxn = 2e5 + 7; int N , K , a[205] , ps[205] , f[205][205][205]; bool vis[205][205][205]; pair <int ,pair<int ,int>> trace[205][205][205]; int sum(int l , int r) { return ps[r] - ps[l-1]; } int solve(int l , int r , int k) { if(k == 0) return 0; if(l > r) return -1e18; if(l == r) return -1e18; if(vis[l][r][k]) return f[l][r][k]; vis[l][r][k] = 1; for(int j = l; j < r; j++) { for(int x = 0; x < k; x++) { int cal = solve(l , j , x) + solve(j+1 , r , k-x-1) + sum(l , j)*sum(j+1 , r); if(f[l][r][k] < cal) { trace[l][r][k].fi = j; trace[l][r][k].se.fi = x; trace[l][r][k].se.se = k - x - 1; f[l][r][k] = cal; } } } return f[l][r][k]; } void dfstrace(int l, int r , int k) { if(l >= r || trace[l][r][k].fi == 0) return; cout << trace[l][r][k].fi << ' '; int j = trace[l][r][k].fi; dfstrace(l , j , trace[l][r][k].se.fi); dfstrace(j+1 , r , trace[l][r][k].se.se); } void data() { cin >> N >> K; for(int i = 1; i <= N; i++) cin >> a[i]; for(int i = 1; i <= N; i++) ps[i] = ps[i-1] + a[i]; cout << solve(1 , N , K) << '\n'; dfstrace(1 , N , K); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); data(); 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...