Submission #879906

#	Time	Username	Problem	Language	Result	Execution time	Memory
879906		iskhakkutbilim	Split the sequence (APIO14_sequence)	C++17	0 / 100	2060 ms	16724 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e17;
const int N = 1e5;
 
/*
 7 3
 4 1 3 4 0 2 3 
*/
signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0); cout.tie(0);
	int n, k; cin >> n >> k;
	vector< vector<int> > dp(n + 1, vector<int>(k + 1, -mod));
	vector< vector<int> > where(n + 1, vector<int>(k + 1, -1));
	vector<int> a(n + 1, 0);
	for(int i = 1;i <= n; i++) cin >> a[i];
	vector<int> suff(n + 2, 0), pref(n + 1, 0);
	suff[n] = a[n];
	for(int i = 1;i <= n; i++) pref[i] = pref[i-1] + a[i];
	for(int i = n-1;i >= 1; i--) suff[i] = suff[i + 1] + a[i];
	dp[0][0] = 0;
	for(int i = 1;i <= n; i++){
		for(int sub = 0; sub <= k; sub++){
			
			if(dp[i][sub] < dp[i-1][sub]){
				dp[i][sub] = dp[i-1][sub];
				where[i][sub] = where[i-1][sub];
			}
			if(sub == 0) continue;
			for(int j = i; j >= 1; j--){
				int pr = pref[i] - pref[j-1];
				if(dp[i][sub] < dp[j-1][sub-1] + (suff[i+1] * pr)){
					dp[i][sub] = dp[j-1][sub-1] + (suff[i + 1] * pr);
					where[i][sub] = j;
				}
			}
		}
	}
	vector<int> path;
	int ans = dp[n][k];
	cout << dp[n][k] << '\n';
	int idx = n, j = k;
	while(idx > 0){
		int to = where[idx][j];
	//	cout << idx << ' ' << j << " = "  << to << '\n';
	if(to < 0) break;
		path.push_back(to);
		j--;
		idx = to;
	}
	reverse(all(path));
	if(path.size() != k) assert(false);
	for(auto x : path) cout << x << ' ';
	
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:58:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |  if(path.size() != k) assert(false);
      |     ~~~~~~~~~~~~^~~~
sequence.cpp:46:6: warning: unused variable 'ans' [-Wunused-variable]
   46 |  int ans = dp[n][k];
      |      ^~~

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