Submission #701893

#	Time	Username	Problem	Language	Result	Execution time	Memory
701893		sudheerays123	Split the sequence (APIO14_sequence)	C++17	0 / 100	10 ms	7124 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 = 1000+5 , K = 200+5 , INF = 1e18 , MOD = 1e9+7;

vector<ll> a(N),presum(N);
ll dp[N][K],par[N][K];

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

	if(l > r) return;

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

	ll bestval = -INF , opt;
	for(ll i = optl; i <= min(mid,optr); i++){

		ll pre = presum[i-1];
		if(pre == 0) pre = 1;
		ll cost = (((presum[mid]-presum[i-1]))*pre) + dp[i-1][j-1];

		if(cost > bestval){
			bestval = cost;
			opt = i;
		}
	}

	dp[mid][j] = bestval;
	par[mid][j] = opt;

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

void solve(){

	ll n,k;
	cin >> n >> k;

	for(ll i = 1; i <= n; i++) cin >> a[i];
	// reverse(a.begin()+1,a.begin()+n+1);
	for(ll i = 1; i <= n; i++) presum[i] = presum[i-1]+a[i];

	memset(dp,-1,sizeof dp);

	dp[0][1] = 0;
	par[0][1] = 0;
	for(ll i = 1; i <= n; i++){
		dp[i][1] = 0;
		par[i][1] = i;
	}

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

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

	ll curind = n , curk = k+1;
	vector<ll> rev;
	while(curk > 1){
		ll x = par[curind][curk];
		rev.push_back(x-1);
		curind = x-1;
		curk--;
	}
	reverse(rev.begin(),rev.end());
	for(auto u : rev) 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:33:5: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |  dnc(j,l,mid,optl,opt);
      |  ~~~^~~~~~~~~~~~~~~~~~

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