Submission #367510

#	Time	Username	Problem	Language	Result	Execution time	Memory
367510		arnold518	Split the sequence (APIO14_sequence)	C++14	0 / 100	325 ms	7524 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();
	}
	void update(Line p)
	{
		if(!S.empty() && S.back().a==p.a)
		{
			if(S.back().b>p.b)
			{
				S.pop_back();
				S.push_back(p);
			}
			return;
		}
		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 query(ll x)
	{
		int lo=0, hi=S.size();
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cross(S[mid], S[mid-1])<=x) lo=mid;
			else hi=mid;
		}
		return S[lo].p;
	}
}cht;

pll dp[MAXN+10];
int memo[MAXN+10];
vector<int> V, ansV;
pll 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({-2*A[i], 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());
	for(auto it : V)
	//printf("%lld : %lld %lld\n", lambda, dp[N].first, dp[N].second);
	return dp[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];

	ll lo=0, hi=1e9;
	while(lo+1<hi)
	{
		ll mid=lo+hi>>1;
		if(solve(2*mid+1).second<=K) hi=mid;
		else lo=mid;
	}

	vector<int> L, R;
	solve(2*hi+1); L=V;
	solve(2*lo+1); R=V;

	if(L.size()-1==K)
	{
		ansV=L;
	}
	else if(R.size()-1==K)
	{
		ansV=R;
	}
	else
	{
		assert(L.size()<K && K<R.size());
		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<R.size(); j++) ansV.push_back(L[j]);
				break;
			}
		}
	}

	ll ans=solve(2*hi).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]);
}

Compilation message (stderr)

sequence.cpp: In member function 'int CHT::query(ll)':
sequence.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |    int mid=lo+hi>>1;
      |            ~~^~~
sequence.cpp: In function 'pll solve(ll)':
sequence.cpp:77:11: warning: unused variable 'it' [-Wunused-variable]
   77 |  for(auto it : V)
      |           ^~
sequence.cpp: In function 'int main()':
sequence.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   ll mid=lo+hi>>1;
      |          ~~^~~
sequence.cpp:101:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |  if(L.size()-1==K)
      |     ~~~~~~~~~~^~~
sequence.cpp:105:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |  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:111:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |   assert(L.size()<K && K<R.size());
      |          ~~~~~~~~^~
sequence.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   assert(L.size()<K && K<R.size());
      |                        ~^~~~~~~~~
sequence.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i=0; i+1<R.size(); i++)
      |                ~~~^~~~~~~~~
sequence.cpp:116:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |    if(L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                                 ~~~~~~~~~~~~~~~^~~
sequence.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int j=lt+1; j<R.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: In function 'pll solve(ll)':
sequence.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^
sequence.cpp: In function 'int main()':
sequence.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d%d", &N, &K); K++;
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:85:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  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