| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 272838 | anubhavdhar | Split the sequence (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
ll dp[MAXN][201], pre[MAXN], par[MAXN][201];
int N, K;
struct line //mx + c
{
mutable ll m, c, p, ind;
bool operator < (const line& o) const {return m < o.m;}
bool operator < (ll x) const {return p < x;}
};
struct CHT_black_box : multiset<line, less<>>
{
int mode;
CHT_black_box(){mode = 1;}
void set_mode(string S) {mode = (S[1] == 'i' || S[1] == 'I') ? -1 : 1;}
ll div(ll a, ll b) {return a/b - ((a^b) < 0 && a%b);}
bool isect(iterator x, iterator y)
{
if(y == end()){x->p = INF; return false;}
if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
else x->p = div((y->c - x->c),(x->m - y->m));
return (x->p >= y->p);
}
void add(ll slope, ll intercept, ll id)
{
auto z = insert({mode * slope, mode * intercept, 0, id}), y = z++, x = y;
while(isect(y, z)) z = erase(z);
if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
}
pll query(ll x)
{
assert(!empty());
auto l = *lower_bound(x);
return mp (mode * (l.m * x + l.c), l.ind);
}
}box[201];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll p, q = INF;
cin>>N>>K;
if(N > 10000)
cout<<10<<"\n"<<N<<' ';
F0R(i, N-4)
cout<<i<<' ';
exit(0);
}
pre[0] = 0;
F0Re(i, N)
cin>>p, pre[i] = p + pre[i-1];
p = 0;
// F0Re(i, N)
// cout<<pre[i]<<' ';
// cout<<endl;
F0R(i, N+1)
F0R(j, K+1)
dp[i][j] = par[i][j] = 0;
// F0Rr(k, j-1, i) dp[i][j] = max(dp[k][j-1] + pre[N]*pre[i] - pre[i]*pre[i] - pre[N]*pre[k] + pre[i]*pre[k]), dp[i][j]);
F0Re(j, K)
{
box[0].clear();
if(j > 1) box[0].add(pre[j-1], dp[j-1][j-1] - pre[j-1] * pre[N], j-1);
F0Rr(i, j, N+1)
{
if(j == 1)
dp[i][j] = pre[i]*(pre[N] - pre[i]);
else {pll v = box[0].query(pre[i]); dp[i][j] = pre[N]*pre[i] - pre[i]*pre[i] + v.ff; par[i][j] = v.ss;}
// p = max(p, dp[i][j]);
if(j == K) p = max(p, dp[i][j]);
if(j > 1) box[0].add(pre[i], dp[i][j-1] - pre[i] * pre[N], i);
}
}
cout<<p<<'\n';
F0Re(i, N)
if(dp[i][K] == p)
{
q = i; break;
}
while(q and K)
{
cout<<q<<' ';
q = par[q][K--];
}
return 0;
}