Submission #745044

#	Time	Username	Problem	Language	Result	Execution time	Memory
745044		sudheerays123	Split the sequence (APIO14_sequence)	C++17	0 / 100	6 ms	3984 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;
 
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(curj == -1) 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