#include <iostream>
#include <iomanip>
#include <chrono>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::fixed;
using std::to_string;
using std::make_pair;
using std::upper_bound;
using std::lower_bound;
using std::setprecision;
using std::cin;
using std::cout;
using std::set;
using std::map;
using std::list;
using std::pair;
using std::less;
using std::tuple;
using std::stack;
using std::queue;
using std::deque;
using std::string;
using std::vector;
using std::bitset;
using std::greater;
using std::priority_queue;
typedef long double ld;
typedef unsigned ui;
typedef long long lli;
typedef unsigned long long ulli;
typedef vector<int32_t> vi;
typedef vector<ld> vld;
typedef vector<ui> vui;
typedef vector<lli> vlli;
typedef vector<ulli> vulli;
typedef list<int32_t> lsi;
typedef list<ld> lsld;
typedef list<ui> lsui;
typedef list<lli> lslli;
typedef list<ulli> lsulli;
typedef set<int32_t> si;
typedef set<ld> sld;
typedef set<ui> sui;
typedef set<lli> slli;
typedef set<ulli> sulli;
typedef pair<int32_t, int32_t> pii;
typedef pair<lli, lli> pll;
#define int int64_t
#define endl "\n"
#define inp(n) int n; cin >> n
#define Inp(n) lli n; cin >> n
#define inpstr(s) string s; cin >> s
#define inp2(a,b) int a,b; cin >> a >> b
#define Inp2(a,b) lli a,b; cin >> a >> b
#define inparr(arr,n) int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n) lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r) for(int32_t i=(l); i < (r); i++)
#define rep1(i,l,r) for(int32_t i=(l); i <= (r); i++)
#define testIn cin >> test
#define tests for(int32_t testNo=1; testNo <= (test); testNo++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define asrt(v) sort(all(v))
#define dsrt(v) sort(rall(v))
#define revStr(str) string(rall(str))
#define len(a) ((int64_t)(a).size())
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define yes cout << "yes" << endl
#define no cout << "no" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define finish return 0
#define clean fflush(stdout)
#define Inf (int32_t)(1e9)
#define INF (lli)(1e18)
#define Eps (ld)(1e-9)
#define EPS (ld)(1e-18)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
#define MXN (int32_t)(1e5+7)
template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
template<typename dataType>
dataType partitionProbDiff(dataType* arr, dataType n) {
dataType sum = 0;
for (int32_t i = 0; i < n; i++) sum += arr[i];
bool dp[n + 1][sum + 1];
for (int32_t i = 0; i <= n; i++) dp[i][0] = true;
for (int32_t i = 1; i <= sum; i++) dp[0][i] = false;
for (int32_t i = 1; i <= n; i++) {
for (int32_t j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (arr[i - 1] <= j)
dp[i][j] |= dp[i - 1][j - arr[i - 1]];
}
}
for (int32_t j = sum / 2; j >= 0; j--) {
if (dp[n][j] == true) {
return (sum - 2 * j);
}
}
}
template<typename dataType>
bool subsetSumProblem(dataType set[], dataType n, dataType sum) {
bool subset[n + 1][sum + 1];
for (int32_t i = 0; i <= n; i++)
subset[i][0] = true;
for (int32_t i = 1; i <= sum; i++)
subset[0][i] = false;
for (int32_t i = 1; i <= n; i++) {
for (int32_t j = 1; j <= sum; j++) {
if (j < set[i - 1])
subset[i][j] = subset[i - 1][j];
if (j >= set[i - 1])
subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
}
}
return subset[n][sum];
}
bool isPrefix(string &s, string &y) {
if(s.length() > y.length()) return false;
f0(i, s.length()) if(s[i] != y[i]) return false;
return true;
}
bool ispalindrom(string s) {
f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
return true;
}
template<typename dataType>
dataType gcd(dataType a, dataType b) {
while (b != 0) {
dataType c = b;
b = (lli)a % (lli)b;
a = c;
}
return a;
}
template<typename dataType>
void allPrimeBoolArray(dataType n, bool* prime) {
memset(prime, true, sizeof(prime));
for (int32_t p = 2; p * p <= n; p++) {
if (prime[p]) {
for (dataType i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
bool prime[n+1];
memset(prime, true, sizeof(prime));
for (int32_t p = 2; p * p <= n; p++) {
if (prime[p]) {
for (dataType1 i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for (int32_t p = 2; p <= n; p++)
if (prime[p])
primeList.pb(p);
}
template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
string s = bitset<64>(n).to_string();
return s.substr(64-k);
}
template<typename dataType>
string decimalToBinary(dataType n) {
string s = bitset<64>(n).to_string();
const auto loc1 = s.find('1');
if(loc1 != string::npos)
return s.substr(loc1);
return "0";
}
template<typename dataType>
dataType val(char c) {
if (c >= '0' && c <= '9')
return (dataType)c - '0';
else
return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
int32_t len = str.length();
int32_t power = 1;
dataType num = 0;
for (int32_t i = len - 1; i >= 0; i--) {
num += (val<dataType>(str[i]) * power);
power *= base;
}
return num;
}
template<typename dataType>
char reVal(dataType num) {
if (num >= 0 && num <= 9)
return (char)(num + '0');
else
return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
string res = "";
while (inputNum > 0) {
res += reVal(inputNum % base);
inputNum /= base;
}
if (res == "")
res = "0";
return revStr(res);
}
template<typename dataType1, typename dataType2>
dataType1 smallFactor(dataType1 n, dataType2 &primes) {
for (dataType1 x:primes) {
if(n % x == 0) {
return x;
break;
} else if (x > sqrt(n)) {
return n;
break;
}
}
return 7;
}
template<typename dataType>
dataType phi(dataType n) {
dataType result = n;
for(int32_t p = 2; p * p <= n; ++p) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
if (n == 0) return 1;
if (n % 2 == 0) {
int64_t t_pow = (int64_t)powMod(base, n/2, mod);
return ((t_pow*t_pow) % mod);
}
int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
if(isPrime) return powMod(n, mod-2, mod);
return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}
//define a compare function for pair
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
bool compare(pair<dataType1, dataType2> &a, pair<dataType3, dataType4> &b) {
return a.first < b.first;
}
// Solver functions
int32_t solve1(int32_t);
int32_t solve2(int32_t);
int32_t solve3(int32_t);
template<typename dataType>
dataType segtree_operator(dataType a, dataType b) {
return a + b;
}
template<typename dataType>
struct segtree {
int size;
vector<dataType> tree;
dataType init_val;
template<typename dataType1>
segtree(int n, dataType1 &arr, dataType init) {
init_segtree(n, init);
for (int32_t i = 0; i < n; i++) {
tree[size+i] = arr[i];
}
for (int32_t i = size-1; i > 0; i--) {
tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
}
}
segtree(int n, dataType* arr, dataType init) {
init_segtree(n, init);
for (int32_t i = 0; i < n; i++) {
tree[size+i] = arr[i];
}
for (int32_t i = size-1; i > 0; i--) {
tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
}
}
void init_segtree(int n, dataType init) {
size = 1;
init_val = init;
while (size < n) size *= 2;
tree.resize(size*2, init_val);
}
dataType query(int l, int r) {
int base = 1;
while (base < size) base *= 2;
l += base;
r += base;
dataType res = init_val;
while (l <= r) {
if (l % 2 == 1) res = segtree_operator(res, tree[l]);
if (r % 2 == 0) res = segtree_operator(res, tree[r]);
l = (l+1) / 2;
r = (r-1) / 2;
}
return res;
}
};
int32_t main() {
#if defined __has_include
#if __has_include("LOCAL.hh")
#include "LOCAL.hh"
#endif
#endif
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
using namespace std::chrono;
cout << fixed << setprecision(9);
auto begin = steady_clock::now();
#else
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
// Previous code
// Main code
int32_t test = 1;
// testIn;
tests {
solve1(testNo);
}
#ifdef LOCAL
auto end = steady_clock::now();
cout << "\nTime : "
<< (ld)duration_cast<nanoseconds>
(end - begin).count()/1000000000
<< "s" << endl;
#endif
finish;
}
int32_t solve1(int32_t testNo) {
// cout << "Case #" << testNo << ": ";
// cout << endl;
inp2(n, k);
inparr(arr, n);
int ans = 0;
f0(i, n) ans += arr[i];
ld avg = ((ld)ans) / ((ld)k);
ans *= ans;
vi partition(k+2, -1);
vi sum(k+1, 0);
partition[0] = 0;
partition[k+1] = n;
int cursum = 0, ind = 0;
f1(i, k) {
while (ind < n && cursum + arr[ind] < avg*i) {
cursum += arr[ind];
ind++;
}
if((avg*i - cursum > cursum + arr[ind] - avg*i) && ind < n-1) {
cursum += arr[ind];
ind++;
}
partition[i] = ind;
}
f0(i, k+1) {
for(int j = partition[i]; j < partition[i+1]; j++) {
sum[i] += arr[j];
}
}
bool optimal = false;
while(!optimal) {
optimal = true;
f0(i, k) {
if(partition[i+1] != n-1) if(abs(sum[i] - sum[i+1]) > abs(sum[i] + arr[partition[i+1]] - sum[i+1] + arr[partition[i+1]])) {
optimal = false;
sum[i] += arr[partition[i+1]];
sum[i+1] -= arr[partition[i+1]];
partition[i+1]++;
}
if(partition[i+1] != 0) if(abs(sum[i] - sum[i+1]) > abs(sum[i] - arr[partition[i+1] - 1] - sum[i+1] - arr[partition[i+1] - 1])) {
optimal = false;
sum[i] -= arr[partition[i+1] - 1];
sum[i+1] += arr[partition[i+1] - 1];
partition[i+1]--;
}
}
if(optimal) {
f0(i, k) {
if(partition[i+1] != 0) if(abs(sum[i] - sum[i+1]) >= abs(sum[i] - arr[partition[i+1] - 1] - sum[i+1] - arr[partition[i+1] - 1])) {
sum[i] -= arr[partition[i+1] - 1];
sum[i+1] += arr[partition[i+1] - 1];
partition[i+1]--;
}
}
f0(i, k) {
if(partition[i+1] != n-1) if(abs(sum[i] - sum[i+1]) > abs(sum[i] + arr[partition[i+1]] - sum[i+1] + arr[partition[i+1]])) {
optimal = false;
sum[i] += arr[partition[i+1]];
sum[i+1] -= arr[partition[i+1]];
partition[i+1]++;
}
if(partition[i+1] != 0) if(abs(sum[i] - sum[i+1]) > abs(sum[i] - arr[partition[i+1] - 1] - sum[i+1] - arr[partition[i+1] - 1])) {
optimal = false;
sum[i] -= arr[partition[i+1] - 1];
sum[i+1] += arr[partition[i+1] - 1];
partition[i+1]--;
}
}
f0(i, k) {
if(partition[i+1] != n-1) if(abs(sum[i] - sum[i+1]) >= abs(sum[i] + arr[partition[i+1]] - sum[i+1] + arr[partition[i+1]])) {
sum[i] += arr[partition[i+1]];
sum[i+1] -= arr[partition[i+1]];
partition[i+1]++;
}
}
f0(i, k) {
if(partition[i+1] != n-1) if(abs(sum[i] - sum[i+1]) > abs(sum[i] + arr[partition[i+1]] - sum[i+1] + arr[partition[i+1]])) {
optimal = false;
sum[i] += arr[partition[i+1]];
sum[i+1] -= arr[partition[i+1]];
partition[i+1]++;
}
if(partition[i+1] != 0) if(abs(sum[i] - sum[i+1]) > abs(sum[i] - arr[partition[i+1] - 1] - sum[i+1] - arr[partition[i+1] - 1])) {
optimal = false;
sum[i] -= arr[partition[i+1] - 1];
sum[i+1] += arr[partition[i+1] - 1];
partition[i+1]--;
}
}
if(optimal) break;
}
}
f0(i, k+1) {
ans -= sum[i]*sum[i];
}
cout << ans/2 << endl;
for(int i = 1; i <= k; i++) {
cout << partition[i] << " ";
}
finish;
}
int32_t solve2(int32_t testNo) {
// cout << "Case #" << testNo << ": ";
// cout << endl;
finish;
}
int32_t solve3(int32_t testNo) {
// cout << "Case #" << testNo << ": ";
// cout << endl;
finish;
}
Compilation message
sequence.cpp: In function 'bool isPrefix(std::string&, std::string&)':
sequence.cpp:92:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | #define f0(i,n) for(int32_t i = 0; i < (n); i++)
| ^
sequence.cpp:196:5: note: in expansion of macro 'f0'
196 | f0(i, s.length()) if(s[i] != y[i]) return false;
| ^~
sequence.cpp: In function 'bool ispalindrom(std::string)':
sequence.cpp:92:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | #define f0(i,n) for(int32_t i = 0; i < (n); i++)
| ^
sequence.cpp:200:5: note: in expansion of macro 'f0'
200 | f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
1 ms |
212 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
1 ms |
212 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Incorrect |
1 ms |
212 KB |
contestant didn't find the optimal answer: 1542521 < 1542524 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
contestant found the optimal answer: 1093956 == 1093956 |
| 2 |
Incorrect |
0 ms |
212 KB |
contestant didn't find the optimal answer: 301650081 < 302460000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
contestant found the optimal answer: 610590000 == 610590000 |
| 2 |
Incorrect |
0 ms |
212 KB |
contestant didn't find the optimal answer: 308685420 < 311760000 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
contestant didn't find the optimal answer: 20507504 < 21503404 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
contestant didn't find the optimal answer: 1794250000 < 1818678304 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1096 KB |
declared answer doesn't correspond to the split scheme: declared = 25439157759, real = 18996706815 |
| 2 |
Halted |
0 ms |
0 KB |
- |
