Submission #745031

#	Time	Username	Problem	Language	Result	Execution time	Memory
745031		sudheerays123	Split the sequence (APIO14_sequence)	C++17	0 / 100	9 ms	2516 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 10+5 , K = 200+5 , INF = 1e18 , MOD = 1e9+7;

ll n,k;
ll dp[N][K],opt[N][K];
vector<ll> presum(N);

void dnc(ll l , ll r , ll j , ll optl , ll optr){

	if(l > r) return;

	ll mid = (l+r)/2;
	if(dp[mid][j] != -1) return;

	ll ind, ans = -INF;

	for(ll i = optl; i <= min(optr,mid); i++){
		ll cost = dp[i-1][j-1] + presum[i-1]*(presum[mid]-presum[i-1]);
		if(cost > ans){
			ans = cost;
			ind = i;
		}
	}

	dp[mid][j] = ans;
	opt[mid][j] = ind;

	dnc(l,mid-1,j,optl,ind);
	dnc(mid+1,r,j,ind,optr);
}

void solve(){

	cin >> n >> k;

	vector<ll> a(n+5);
	for(ll i = 1; i <= n; i++) cin >> a[i];
	for(ll i = 1; i <= n; i++) presum[i] = presum[i-1]+a[i];

	memset(dp,-1,sizeof dp);
	for(ll i = 1; i <= n+2; i++) dp[i][0] = -INF;
	dp[0][0] = 0;

	for(ll i = 1; i <= k+1; i++) dnc(1,n,i,1,n);

	cout << dp[n][k+1] << "\n";

	ll curi = opt[n][k+1] , curj = k;
	vector<ll> path;

	while(true){
		curi = opt[curi][curj];
		curj--;
		if(curi == 0) break;
		path.push_back(curi);
	}

	reverse(path.begin(),path.end());
	for(auto u : path) cout << u << " ";
}

int main(){

	fast;

	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void dnc(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:31:5: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |  dnc(l,mid-1,j,optl,ind);
      |  ~~~^~~~~~~~~~~~~~~~~~~~

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