제출 #566414

#제출 시각아이디문제언어결과실행 시간메모리
566414MurotY수열 (APIO14_sequence)C++14
0 / 100
383 ms32724 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define ff first #define ss second using namespace std; const int N=1e4+7, M=1e9+7; ll a[N], dp[N][206], res[N][206], pref[N]; void solve() { int n, k; cin >> n >> k; for (int i=1;i<=n;i++) cin >> a[i]; for (int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i]; for (int i=1;i<=n;i++){ for (int j=i;j<=n;j++){ for (int q=1;q<k;q++){ if (dp[j][q] <= dp[i-1][q-1]+(pref[j]-pref[i-1])*(pref[n]-pref[j])){ dp[j][q] = dp[i-1][q-1]+(pref[j]-pref[i-1])*(pref[n]-pref[j]); res[j][q]=i; } } } } ll ress=0, mx=0; for (int i=1;i<=n;i++){ if (mx < dp[i][k]) mx=dp[i][k], ress=i; } ll jv=res[ress][k]; vector <ll> ans; while (k > 0){ ans.push_back(res[jv][k]); jv=res[jv][k]; k--; } reverse(ans.begin(), ans.end()); cout << mx <<"\n"; for (auto l:ans) cout << l <<" "; return ; } int main() { ios; int t=1; // cin >> t; while (t--){ solve(); cout <<"\n"; } 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...