Submission #401028

#	Time	Username	Problem	Language	Result	Execution time	Memory
401028		AriaH	Split the sequence (APIO14_sequence)	C++11	49 / 100	415 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[205][N], A[N], ps[N];
 
ll dp[205][N];
 
inline ll calc(int l, int m, int r = n)
{
	return 1ll * (ps[r] - ps[m]) * (ps[m] - ps[l - 1]);
}
 
void solve(int j, int l, int r, int le, int ri)
{
	if(l > r || le > ri) 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;
	if(j > mid)
	{
		dp[j][mid] = -inf;
		par[j][mid] = -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);
	}
	printf("%lld\n", 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 --;
	}
	reverse(all(ans));
	for(auto x : ans) printf("%d ", x);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   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