oj.uz

Submission #308028

# Submission time Handle Problem Language Result Execution time Memory
308028 2020-09-29T23:02:22 Z avengers Split the sequence (APIO14_sequence) C++14
0 / 100
 14 ms 6220 KB 
#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)
{
	while(now<sz-1&&cx(cht[now], cht[now+1])<=x) now++;
	return {cht[now].p*x+cht[now].q, now};
}
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 'int main()':
sequence.cpp:39:5: warning: unused variable 't' [-Wunused-variable]
   39 |  ll t;
      |     ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 384 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 384 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Integer 0 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Integer 0 violates the range [1, 999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1024 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 6220 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -