Submission #367546

#	Time	Username	Problem	Language	Result	Execution time	Memory
367546		arnold518	Split the sequence (APIO14_sequence)	C++14	0 / 100	148 ms	5984 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, K;
ll A[MAXN+10];

struct Line
{
	ll a, b; int p;
};

double cross(Line p, Line q) { return (double)(p.b-q.b)/(q.a-p.a); }

struct CHT
{
	vector<Line> S;
	void init()
	{
		S.clear();
		pos=0;
	}
	void update(Line p)
	{
		if(!S.empty() && S.back().a==p.a)
		{
			if(S.back().b<=p.b) return;
			S.pop_back();
		}
		while(S.size()>1 && cross(S[S.size()-2], S[S.size()-1])>=cross(S[S.size()-1], p)) S.pop_back();
		S.push_back(p);
	}
	int pos=0;
	int query(ll x)
	{
		if(pos>=S.size()) pos=S.size()-1;
		else if(pos+1<S.size() && cross(S[pos], S[pos+1])<=x) pos++;
		return S[pos].p;
	}
}cht;

pll dp[MAXN+10];
int memo[MAXN+10];
vector<int> V, ansV;
void solve(ll lambda)
{
	cht.init();
	cht.update({0, 0, 0});
	V.clear();
	for(int i=1; i<=N; i++)
	{
		int t=cht.query(A[i]);
		dp[i].first=dp[t].first+(A[i]-A[t])*(A[i]-A[t])*2+lambda;
		dp[i].second=dp[t].second+1;
		memo[i]=t;
		cht.update({-4*A[i], 2*A[i]*A[i]+dp[i].first, i});
	}
	for(int i=N; i>0;)
	{
		V.push_back(i);
		i=memo[i];
	}
	V.push_back(0);
	reverse(V.begin(), V.end());
	assert(V.size()==dp[N].second+1);
	/*
	printf("%lld : %lld %lld\n", lambda, dp[N].first, dp[N].second);
	for(int i=1; i<=N; i++) printf("%d ", memo[i]); printf("\n");
	*/
}

int main()
{
	scanf("%d%d", &N, &K); K++;
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);

	for(int i=1; i<=N; i++) A[i]+=A[i-1];

	solve(0);
	ll lo=-1, hi=1e16;
	while(lo+1<hi)
	{
		ll mid=lo+hi>>1;
		solve(2*mid+1);
		if(dp[N].second<=K) hi=mid;
		else lo=mid;
	}

	vector<int> L, R;
	solve(2*hi+1); L=V;
	assert(L.size()==dp[N].second+1);
	solve(2*lo+1); R=V;
	assert(R.size()==dp[N].second+1);

	if(L.size()-1==K)
	{
		ansV=L;
	}
	else if(R.size()-1==K)
	{
		ansV=R;
	}
	else
	{
		assert(L.size()-1<K && K<R.size()-1);
		for(int i=0; i+1<R.size(); i++)
		{
			int l=R[i], r=R[i+1];
			int lt=upper_bound(L.begin(), L.end(), l)-L.begin()-1;
			if(L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
			{
				for(int j=0; j<=i; j++) ansV.push_back(R[j]);
				for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
				break;
			}
		}
	}

	solve(2*lo);
	ll ans=dp[N].first/2-hi*K;
	ans=(A[N]*A[N]-ans)/2;
	printf("%lld\n", ans);
	for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
	printf("\n");
}

Compilation message (stderr)

sequence.cpp: In member function 'int CHT::query(ll)':
sequence.cpp:41:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(pos>=S.size()) pos=S.size()-1;
      |      ~~~^~~~~~~~~~
sequence.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   else if(pos+1<S.size() && cross(S[pos], S[pos+1])<=x) pos++;
      |           ~~~~~^~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'void solve(ll)':
sequence.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   70 |  assert(V.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   ll mid=lo+hi>>1;
      |          ~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:96:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   96 |  assert(L.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:98:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   98 |  assert(R.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:100:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |  if(L.size()-1==K)
      |     ~~~~~~~~~~^~~
sequence.cpp:104:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |  else if(R.size()-1==K)
      |          ~~~~~~~~~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:110:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |   assert(L.size()-1<K && K<R.size()-1);
      |          ~~~~~~~~~~^~
sequence.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   assert(L.size()-1<K && K<R.size()-1);
      |                          ~^~~~~~~~~~~
sequence.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i=0; i+1<R.size(); i++)
      |                ~~~^~~~~~~~~
sequence.cpp:115:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |    if(L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                                 ~~~~~~~~~~~~~~~^~~
sequence.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
      |                     ~^~~~~~~~~
sequence.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
      |               ~~~^~~~~~~~~~~~
sequence.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%d%d", &N, &K); K++;
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:80:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~

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