| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 342172 | ezdp | 수열 (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x)
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;
#define row vector<ll>
#define row_matrix vector<ll>
#define matrix vector<row_matrix>
#define ordered_set_T int
using namespace std;
using namespace __gnu_pbds;
typedef tree<ordered_set_T, null_type, less<ordered_set_T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x) -> how many elements are smaller than x
/// insert(x) -> inserts x into the set
const ll MAXN = 1e6 + 5;
const ll MAXK = 256;
ll n, k, prefix[MAXN], A[MAXN], dp[MAXK][MAXN], opt[MAXK][MAXN];
ll f(ll l, ll r){
return (l == 0 ? 0 : prefix[l - 1]) * (prefix[r] - (l == 0 ? 0 : prefix[l - 1]));
}
void solve(ll i, ll l, ll r, ll tl, ll tr){
if(l > r){
return;
}
ll m = (l + r) / 2;
for(ll _t = max(tl, i - 1); _t <= min(tr, m); _t ++){
if(dp[i - 1][_t - 1] + f(_t, m) > dp[i][m]){
opt[i][m] = _t;
dp[i][m] = dp[i - 1][_t - 1] + f(_t, m);
}
}
solve(i, l, m - 1, tl, opt[i][m]);
solve(i, m + 1, r, opt[i][m], tr);
}
int main(){
/// ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> A[i];
prefix[0] = A[0]; for(int i = 1; i < n; i ++) prefix[i] = prefix[i - 1] + A[i];
for(int _k = 2; _k <= k + 1; _k ++){
solve(_k, 0, n - 1, 0, n - 1);
}
cout << dp[k + 1][n - 1] << endl;
row v;
ll tmp = opt[k + 1][n - 1], r = k;
while(tmp){
v.pb(tmp);
tmp = opt[r --][tmp - 1];
}
reverse(all(v));
for(auto x : v) cout << x << " "; cout << endl;
}
/**
*/