Submission #1009903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009903		Phuoc	Split the sequence (APIO14_sequence)	C++14	0 / 100	1 ms	348 KiB

sequence

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>

using namespace std;

#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)

/* Author: Pham Gia Phuoc */

const ll MOD = 998244353;

template <class T1, class T2>
	void add(T1 &a, T2 b){
		a += b;
		if(a >= MOD) a -= MOD;
	}

template <class T1, class T2>
	bool minimize(T1 &a, T2 b){
		if(a > b){a = b; return true;} return false;
	}

template <class T1, class T2>
	bool maximize(T1 &a, T2 b){
		if(a < b){a = b; return true;} return false;
	}

/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/

const int MAX =  2222;
const ll INF = (ll) 1e18 + 7LL;

int numVal, numSplit;
ll values[MAX];

void init(){
	cin >> numVal >> numSplit;
	for(int i = 1; i <= numVal; i++) cin >> values[i];
}

void solveSubtask1(){
	ll ans = 0;
	ll Mask;
	for(int i = 1; i <= numVal; i++) values[i] += values[i - 1];
	for(ll mask = 0; mask < MASK(numVal - 1); mask++)if(__builtin_popcount(mask) == numSplit){
		int lastBit = 0; ll tmp = 0;
		for(int i = 1; i < numVal; i++) if(BIT(mask, i - 1)){
			tmp += (values[numVal] - values[i]) * (values[i] - values[lastBit]);
			lastBit = i;
		}
		if(maximize(ans, tmp))Mask = mask;
	}
	cout << ans << el;
	for(int i = 1; i < numVal; i++) if(BIT(Mask, i - 1)) cout << i << ' ';
}

void solve(){
	if(numSplit <= 10 && numVal <= 10) solveSubtask1();
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	init();
	solve();
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solveSubtask1()':
sequence.cpp:15:31: warning: 'Mask' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 | #define BIT(mask, i) (((mask) >> (i)) & 1)
      |                               ^~
sequence.cpp:52:5: note: 'Mask' was declared here
   52 |  ll Mask;
      |     ^~~~

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