Submission #401042

#	Time	Username	Problem	Language	Result	Execution time	Memory
401042		AriaH	Split the sequence (APIO14_sequence)	C++17	78 / 100	1673 ms	85700 KiB

sequence

/** Im the best because i work as hard as i possibly can **/
 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int                  ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"
 
const int N = 1e5 + 10;
const ll inf = 1e18;

int n, k, par[210][N];

ll dp[2][N], ps[N], A[N];
 
inline ll calc(int l, int m)
{
	return (ps[n] - ps[m]) * (ps[m] - (l <= 0? 0 : ps[l - 1]));
}
 
void solve(int j, int l, int r, int le, int ri)
{
	int j2 = j & 1;
	if(l > r) return;
	int mid = (l + r) >> 1;
	dp[j2][mid] = -inf;
	for(int i = le; i <= min(ri, mid); i ++)
	{
		ll cu = dp[1 ^ j2][i - 1] + calc(i, mid);
		if(cu > dp[j2][mid])
		{
		    dp[j2][mid] = cu;
		    par[j][mid] = i - 1;
		}
	}
	if(par[j][mid] != -1) solve(j, l, mid - 1, le, par[j][mid] + 1);
	solve(j, mid + 1, r, max(le, par[j][mid] + 1), ri);
}
 
int main()
{
	scanf("%d%d", &n, &k);
	k ++;
	for(int i = 1; i <= n; i ++)
	{
		scanf("%lld", &A[i]);
		ps[i] = ps[i - 1] + A[i];
	}
	memset(par, -1, sizeof par);
	for(int i = 1; i < N; i ++) dp[0][i] = -inf;
	for(int j = 1; j <= k; j ++)
	{
		solve(j, 1, n, 1, n);
	}
	printf("%lld\n", dp[k & 1][n]);
	vector < int > ans;
	int i = n, j = k;
	while(j > 0 && i > 0 && par[j][i] > 0)
	{
		ans.push_back(par[j][i]);
		i = par[j][i];
		j --;
	}
	reverse(all(ans));
	for(auto x : ans) printf("%d ", x);
	return 0;
}

Compilation message (stderr)

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

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