# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
994993 | Baytoro | 수열 (APIO14_sequence) | C++17 | 71 ms | 131072 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
#define ll long long
const int N=1e5+5;
int n;
struct line{
ll m, b;
ll operator *(int x){
return m*x+b;
}
int operator ^(line x){
return ceil((b-x.b)/(x.m-m));
}
};
struct CHT{
deque<int64_t> a, b;
deque<int> c;
void init() {
a.clear();
b.clear();
c.clear();
}
void push(int64_t n, int64_t m, int v) {
while (a.size() > 1 &&
(b[b.size() - 2] - b.back()) * (n - a.back()) >= (b.back() - m) * (a.back() - a[a.size() - 2])) {
a.pop_back();
b.pop_back();
c.pop_back();
}
a.push_back(n);
b.push_back(m);
c.push_back(v);
}
pair<int64_t, int> query(int64_t x) {
while (a.size() > 1 && (a[1] - a[0]) * x > (b[0] - b[1])) {
a.pop_front();
b.pop_front();
c.pop_front();
}
return make_pair(a[0] * x + b[0], c[0]);
}
};
vector<int> dp_cur(N),dp_prev(N);
int p[N][205];
void solve(){
int n,k;cin>>n>>k;
vector<int> a(n+1),pref(n+1);
for(int i=0;i<n;i++){
cin>>a[i];
pref[i+1]=a[i]+pref[i];
}
for(int i=0;i<n-1;i++){
dp_prev[i]=pref[i+1]*(pref[n]-pref[i+1]);
p[i][1]=-1;
}
for(int j=2;j<=k;j++){
CHT cht;
dp_cur[0]=0;
for(int i=1;i<n-1;i++){
cht.push(pref[i],dp_prev[i-1],i);
auto it=cht.query(pref[i+1]-pref[n]);
dp_cur[i]=it.fr+pref[i+1]*pref[n]-pref[i+1]*pref[i+1];
p[i][j]=it.sc-1;
}
dp_prev=dp_cur;
}
int ans=0,c=0;
for(int i=0;i<n-1;i++){
if(ans<dp_prev[i]){
ans=dp_prev[i];
c=i;
}
}
cout<<ans<<endl;
for(int i=0;i<k;i++){
cout<<c+1<<' ';
c=p[c][k-i];
}
}
signed main(){
//fopn("paint");
int t=1;//cin>>t;
while(t--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |