Submission #367497

#	Time	Username	Problem	Language	Result	Execution time	Memory
367497		AriaH	Split the sequence (APIO14_sequence)	C++11	49 / 100	391 ms	131076 KiB

sequence

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   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 mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 4e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, k, par[202][N], A[N];

ll dp[202][N], ps[N];

inline ll calc(int l, int m, int r = n)
{
	return (ps[r] - ps[m]) * (ps[m] - ps[l - 1]);
}

void solve(int j, int l, int r, int le, int ri)
{
	if(l > r) return;
	int mid = (l + r) >> 1, opt = le;
	ll best = -inf;
	for(int i = le; i <= min(mid, ri); i ++)
	{
		ll cu = dp[j - 1][i - 1] + calc(i, mid);
		if(cu > best)
		{
			best = cu;
			opt = i;
		}
	}
	dp[j][mid] = best;
	par[j][mid] = opt - 1;
	solve(j, l, mid - 1, le, opt);
	solve(j, mid + 1, r, opt, ri);
}

int main()
{
	scanf("%d%d", &n, &k);
	k ++;
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &A[i]);
		ps[i] = ps[i - 1] + A[i];
	}
	for(int i = 1; i < N; i ++) dp[0][i] = -inf;
	for(int j = 1; j <= k; j ++)
	{
		solve(j, 1, n, 1, n);
	}
	/*for(int j = 0; j <= k; j ++)
	{
		for(int i = 1; i <= n; i ++)
		{
			printf("%lld ", dp[j][i]);
		}
		printf("\n");
	}
	for(int j = 0; j <= k; j ++)
	{
		for(int i = 1; i <= n ;i ++)
		{
			printf("%d ", par[j][i]);
		}
		printf("\n");
	}
	*/
	printf("%lld", dp[k][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 --;
	}
	printf("\n");
	reverse(all(ans));
	for(auto x : ans) printf("%d ", x);
	return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

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

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