Submission #308034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
308034	2020-09-29T23:16:44 Z	avengers	Split the sequence (APIO14_sequence)	C++14	Compilation error	0 ms	0 KB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
typedef struct Line{
	ll p, q;
}line;
int n, k;
ll a[100005];
ll s[100005]={};
ll dp[2][100005]={};
int track[205][100005];
line cht[100005];
ll sz=0;
ll now=0;
double cx(line a, line b)
{
	return 1.0*(double)(b.q-a.q)/(a.p-b.p);
}
void insert(line v)
{
	cht[sz]=v;
	while(sz>1&&cx(cht[sz-2], cht[sz-1])>cx(cht[sz], cht[sz-1]))
	{
		cht[sz-1]=cht[sz];
		sz--;
	}
	sz++;
}
pair <ll, ll> sol(ll x)
{
	ll lo=0;
    ll hi=sz-1;
    while(lo<hi)
    {
      ll mid=(lo+hi)/2;
      if(cx(cht[mid], cht[mid+1])<=x) lo=mid+1;
      else hi=mid;
    }
    return cht[lo].p*x+cht[lo].q;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	ll t;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	line l;
	for(int i=1; i<=k; i++)
	{
		l.p=0;
		l.q=0;
		insert(l);
		for(int j=1; j<=n; j++)
		{
			pair <ll, ll> p=sol(s[j]);
			dp[i%2][j]=p.first;
			track[i][j]=p.second;
			l.p=s[j];
			l.q=dp[(i+1)%2][j]-s[j]*s[j];
			insert(l);
		}
		sz=0;
		now=0;
	}
	cout<<dp[k%2][n]<<'\n';
	vector <int> ans;
	ll cur=n;
	for(int i=k; i>=1; i--)
	{
		ans.push_back(track[i][cur]);
		cur=track[i][cur];
	}
	reverse(ans.begin(), ans.end());
	for(auto i:ans) cout<<i<<' ';
}

Compilation message

sequence.cpp: In function 'std::pair<long long int, long long int> sol(ll)':
sequence.cpp:39:23: error: could not convert '((cht[lo].Line::p * x) + cht[lo].Line::q)' from 'll' {aka 'long long int'} to 'std::pair<long long int, long long int>'
   39 |     return cht[lo].p*x+cht[lo].q;
      |            ~~~~~~~~~~~^~~~~~~~~~
      |                       |
      |                       ll {aka long long int}
sequence.cpp: In function 'int main()':
sequence.cpp:46:5: warning: unused variable 't' [-Wunused-variable]
   46 |  ll t;
      |     ^