Submission #51554

#	Time	Username	Problem	Language	Result	Execution time	Memory
51554		tranxuanbach	Split the sequence (APIO14_sequence)	C++17	100 / 100	758 ms	85928 KiB

sequence

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000000
#define inf 1000000000000000000ll
#define N 100005
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
#define loloi pair<lolo, int>
using namespace std;
 
int n, k, x, ptr;
ll dp[2][N], pre[N];
int tut[201][100001];
vector <loloi> v;
 
ll res(lolo line, ll x){
	return line.st * x + line.nd;
}
 
ll get(ll val){
	while (ptr + 1 < sz(v) &&
	       res(v[ptr].st, val) < res(v[ptr + 1].st, val)){
	    ptr++;
	}
	return res(v[ptr].st, val);
}
 
lf inter(lolo line1, lolo line2){
	return 1.0 * (line2.nd - line1.nd) / (line1.st - line2.st);
}
 
void up(ll a, ll b, int ind){
	while (sz(v) > 1 && 
	       inter({a,b}, v[sz(v) - 1].st) <= inter({a, b}, v[sz(v) - 2].st)){
		v.ppb();
	}
	v.pb({{a, b}, ind});
	ptr = min(ptr, sz(v) - 1);
}
 
void clear(){
	ptr = 0;
	v.clear();
}
 
int main(){
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++){
		scanf("%d", &x);
		pre[i] = pre[i - 1] + x;
	}
	for (int i = 1; i <= k; i++){
		clear();
		up(pre[i], -pre[i] * pre[i] + dp[0][i], i);
		for (int j = i + 1; j <= n; j++){
			dp[1][j] = get(pre[j]);
			tut[i][j] = v[ptr].nd;
			up(pre[j], -pre[j] * pre[j] + dp[0][j], j);
			dp[0][j] = dp[1][j];
		}
	}
	printf("%lld\n", dp[0][n]);
	for (int i = tut[k][n]; i >= 1; i = tut[k][i]){
		k--;
		printf("%d ", i);
	}
	assert(k == 0);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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