// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
void solve(long long N, long long K, vector<long long> a, vector<long long> a0, long long K0) {
if (K0>K) {
long long tval = 0;
for (long long i=0;i<N;i++) {
tval += a[i];
}
tval = tval*tval;
deque<long long> d[K+1];
long long dsums[K+1];
for (long long i=0;i<=K;i++) {
dsums[i]=0;
}
for (long long i=0;i<N;i++) {
d[0].push_back(a[i]);
dsums[0] += a[i];
}
for (long long t=0;t<(2*N);t++) {
for (long long i=0;i<K;i++) {
while (1) {
long long r = d[i].back();
if ((max(dsums[i]-r,dsums[i+1]+r)<max(dsums[i],dsums[i+1]))||((max(dsums[i]-r,dsums[i+1]+r)==max(dsums[i],dsums[i+1]))&&(dsums[i+1]!=0))) {
d[i].pop_back();
d[i+1].push_front(r);
dsums[i]=dsums[i]-r;
dsums[i+1]=dsums[i+1]+r;
} else {
break;
}
}
}
}
for (long long i=0;i<=K;i++) {
tval -= dsums[i]*dsums[i];
/*cout << "i="<<i<<", dsums="<<dsums[i]<<"\n";
for (long long x: d[i]) {
cout << "term: "<<x<<"\n";
}*/
}
tval = tval/2;
cout << tval <<"\n";
int del = K0-K;
set<int> noninc;
for (int i=0;i<(a0.size()-1);i++) {
noninc.insert(i);
}
int llnz = -1;
for (int i=0;i<a0.size();i++) {
if (a0[i] != 0) {
llnz = i;
}
}
for (int i=0;i<a0.size();i++) {
if ((a0[i] != 0)) {
if (i != llnz) {
noninc.erase(i);
}
}
}
for (int i=0;i<del;i++) {
noninc.erase(noninc.begin());
}
string outstr;
for (int i=0;i<(a0.size()-1);i++) {
if (noninc.find(i)==noninc.end()) {
outstr += to_string(i+1);
outstr += " ";
}
}
outstr = outstr.substr(0,(outstr.length()-1));
cout << outstr;
} else {
long long tval = 0;
for (long long i=0;i<N;i++) {
tval += a[i];
}
tval = tval*tval;
deque<long long> d[K+1];
long long dsums[K+1];
for (long long i=0;i<=K;i++) {
dsums[i]=0;
}
for (long long i=0;i<N;i++) {
d[0].push_back(a[i]);
dsums[0] += a[i];
}
for (long long t=0;t<(2*N);t++) {
for (long long i=0;i<K;i++) {
while (1) {
long long r = d[i].back();
if (max(dsums[i]-r,dsums[i+1]+r)<max(dsums[i],dsums[i+1])) {
d[i].pop_back();
d[i+1].push_front(r);
dsums[i]=dsums[i]-r;
dsums[i+1]=dsums[i+1]+r;
} else {
break;
}
}
}
}
for (long long i=0;i<=K;i++) {
tval -= dsums[i]*dsums[i];
/*cout << "i="<<i<<", dsums="<<dsums[i]<<"\n";
for (long long x: d[i]) {
cout << "term: "<<x<<"\n";
}*/
}
tval = tval/2;
cout << tval <<"\n";
string ans;
int rtot = 0;
for (int q=0;q<K;q++) {
int count = 0;
while (count<(d[q].size())) {
if (a0[rtot] != 0) {
count++;
}
rtot++;
}
ans += to_string(rtot);
if (q != (K-1)) {
ans += " ";
}
}
cout << ans;
}
}
int main() {
long long N,K; cin >> N >> K;
vector<long long> a;
vector<long long> a0;
for (long long i=0;i<N;i++) {
long long x; cin >> x;
a0.push_back(x);
if (x != 0) {
a.push_back(x);
}
}
int K0 = K;
K = min(K,(long long) (a.size()-1));
solve(a.size(),K,a,a0,K0);
}
Compilation message
sequence.cpp: In function 'void solve(long long int, long long int, std::vector<long long int>, std::vector<long long int>, long long int)':
sequence.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i=0;i<(a0.size()-1);i++) {
| ~^~~~~~~~~~~~~~
sequence.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i=0;i<a0.size();i++) {
| ~^~~~~~~~~~
sequence.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i=0;i<a0.size();i++) {
| ~^~~~~~~~~~
sequence.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i=0;i<(a0.size()-1);i++) {
| ~^~~~~~~~~~~~~~
sequence.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | while (count<(d[q].size())) {
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
1 ms |
348 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer 200 violates the range [1, 199] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Integer 1000 violates the range [1, 999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
contestant didn't find the optimal answer: 1695400000 < 1818678304 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
3784 KB |
contestant didn't find the optimal answer: 19795776955 < 19795776960 |
| 2 |
Halted |
0 ms |
0 KB |
- |
