제출 #270208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270208		anubhavdhar	수열 (APIO14_sequence)	C++14	50 / 100	120 ms	131076 KiB

sequence

#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  
{
	mutable ll m, c, p, ind, isline;
	bool operator < (const line & o) const {return (o.isline ? (m < o.m) : (p < o.p));}
};
 
struct CHT : multiset<line>
{
	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 sl, ll in, ll i)
	{
		auto z = insert({sl, in, 0, i, 1}), 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)
	{
		if(empty()) while(true) cout<<1;
		auto l = *lower_bound({0, 0, x, 0, 0});
		return mp(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;
	assert(N < MAXN);
	cin>>N>>K;
	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(i, N)
	{
		F0Re(j, min(i, K))
		{
			if(j == 1)
				dp[i][j] = pre[i]*(pre[N] - pre[i]);
			else {pll v = box[j-1].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(i >= K) p = max(p, dp[i][K]);
		F0Re(j,min(i, K))		
			box[j].add(pre[i], dp[i][j] - pre[i] * pre[N], i);
	}
 
 
	cout<<p<<'\n';
 
	F0Re(i, N)
		if(dp[i][K] == p)
		{
			q = i; break;
		}
 	
  	if(N >8000) exit(0);
	while(q and K)
	{
		cout<<q<<' ';
		q = par[q][K--];
	}
 
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29