oj.uz

Submission #1009903

# Submission time Handle Problem Language Result Execution time Memory
1009903 2024-06-28T07:33:09 Z Phuoc Split the sequence (APIO14_sequence) C++14
0 / 100
 1 ms 348 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 348 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -