Submission #489591

# Submission time Handle Problem Language Result Execution time Memory
489591 2021-11-23T10:11:45 Z ssense Split the sequence (APIO14_sequence) C++14
50 / 100
348 ms 7156 KB
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
#define int long long
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
																																int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//ssense
int dp[1005][205];
int par[1005][205];


void solve()
{
	int n, k;
	cin >> n >> k;
	vint a = read(n);
	prefix_sum pref;
	pref.build(a);
	for(int i = 1; i < n; i++)
	{
		dp[i][1] = pref.get(1, i)*pref.get(i+1, n);
	}
	for(int i = 1; i < n; i++)
	{
		for(int nowk = 1; nowk <= k; nowk++)
		{
			for(int t = 1; t < i; t++)
			{
				if(dp[t][nowk-1]+pref.get(t+1, i)*pref.get(i+1, n) >= dp[i][nowk])
				{
					par[i][nowk] = t;
					dp[i][nowk] = max(dp[i][nowk], dp[t][nowk-1]+pref.get(t+1, i)*pref.get(i+1, n));
				}
			}
		}
	}
	int ans = -MX;
	int best = 0;
	for(int i = 1; i < n; i++)
	{
		if(ans < dp[i][k])
		{
			best = i;
		}
		ans = max(ans, dp[i][k]);
	}
	vint ind;
	int nowind = best;
	int nowmove = k;
	while(nowmove != 0)
	{
		ind.pb(nowind);
		nowind = par[nowind][nowmove];
		nowmove--;
	}
	cout << ans << endl;
	reverse(all(ind));
	for(auto x : ind)
	{
		cout << x << " ";
	}
	cout << endl;
}

int32_t main(){
	startt
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}

/*
 7 3
 4 1 3 4 0 2 3
 */

Compilation message

sequence.cpp: In member function 'void prefix_sum::build(std::vector<long long int>)':
sequence.cpp:21:699: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                                 int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//ssense
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 332 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 204 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 332 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 332 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 320 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 332 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 332 KB contestant found the optimal answer: 1 == 1
9 Correct 0 ms 332 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 320 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 332 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 332 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 0 ms 332 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 332 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 332 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 332 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 332 KB contestant found the optimal answer: 999919994 == 999919994
# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 460 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 460 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 460 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 0 ms 460 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 460 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 460 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 0 ms 460 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 460 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 0 ms 460 KB contestant found the optimal answer: 29000419931 == 29000419931
# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 844 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 14 ms 896 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 844 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 10 ms 956 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 15 ms 908 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 14 ms 908 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 4 ms 940 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 2 ms 844 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 5 ms 972 KB contestant found the optimal answer: 490686959791 == 490686959791
# Verdict Execution time Memory Grader output
1 Correct 5 ms 3532 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 3 ms 3532 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 341 ms 3420 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 6 ms 3532 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 338 ms 3520 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 281 ms 3540 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 348 ms 3660 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 338 ms 3480 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 72 ms 3520 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 141 ms 3420 KB contestant found the optimal answer: 12345131038664 == 12345131038664
# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7156 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -