이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = 1e6+50, inf = 1e17;
//int mod = 998244353
//int mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
struct line{
int m, c, i;
line(int _m,int _c, int _i) : m(_m), c(_c), i(_i){
};
int calc(int x){
return m * x + c;
};
double xnt(line & other){
return (long double)(c - other.c)/(m - other.m);
};
};
void solve(){
int n, k;
cin >> n >> k;
vector<int> v(n+1);
for(int i = 1; i<= n; i++){cin >> v[i];v[i] += v[i-1];}
vector<vector<int>> dp(2, vector<int> (n+2, 0));
vector<vector<int>> from(n+2, vector<int> (k+2));
for(int j = 1; j <= k; j++){
//cout << 1 << '\n';
deque<line> dq;
dq.pb({0,0,0});
for(int i = 1; i <= n; i++){
int ps = v[n] - v[i];
while(dq.size() > 1 && dq.back().calc(ps) <= dq[dq.size()-2].calc(ps))
dq.pop_back();
dp[1][i] = dq.back().calc(ps) + v[i] * ps;
from[i][j] = dq.back().i;
line nw = {-v[i], dp[0][i], i};
while(dq.size() > 1 && nw.xnt(dq[0]) >= dq[0].xnt(dq[1]))
dq.pop_front();
dq.push_front(nw);
}
dp[0] = dp[1];
}
pair<int,int> ans = {-1, 0};
for(int i = 1; i < n; i++){
ans = max(ans, {dp[0][i], i});
}
cout << ans.ff << '\n';
vector<int> res;
while(ans.ss > 0 && k > 0){
res.pb(ans.ss);
ans.ss = from[ans.ss][k--];
}reverse(all(res));
for(int i:res)cout << i << ' ';
cout << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |