#include <iostream>
#include <vector>
using namespace std;
int main()
{
long long n, k;
cin >> n >> k;
long long a[n+1];
a[0] = 0;
for(long long i = 1; i <= n; i++)
{
cin >> a[i];
a[i] += a[i-1];
}
vector<long long> split(k+2); //The i'th split occurs between split[i] and split[i+1]
for(long long i = 0; i <= k; i++) split[i] = i;
split[k+1] = n;
bool flag = 0;
long long x, y, m;
long long segA, segB;
while(flag == 0)
{
flag = 1;
for(long long i = k; i >= 1; i--)
{
segA = a[split[i]] - a[split[i-1]];
segB = a[split[i+1]] - a[split[i]];
if(segA == segB)
{
continue;
}
if(segA > segB)
{
if(segA - (a[split[i]] - a[split[i]-1]) < segB)
{
continue;
}
}
if(segB > segA)
{
if(segB - (a[split[i]+1] - a[split[i]]) < segA)
{
continue;
}
}
flag = 0;
x = split[i-1] + 1;
y = split[i+1] - 1;
while(y - x > 1)
{
m = (x+y)/2;
segA = a[m] - a[split[i-1]];
segB = a[split[i+1]] - a[m];
if(segA == segB)
{
x = y = m;
}
else if(segA > segB)
{
y = m;
if(segA - (a[m] - a[m-1]) < segB)
x = m;
}
else
{
x = m;
if(segA > segB - (a[m+1] - a[m]))
y = m;
}
}
if(x == y) split[i] = x;
else split[i] = ((a[split[i+1]] - a[y] > a[x] - a[split[i]]) ? y : x);
}
}
long long res = a[n] * a[n];
for(long long i = 1; i <= k+1; i++) res -= (a[split[i]] - a[split[i-1]]) * (a[split[i]] - a[split[i-1]]);
cout << res/2 << '\n';
for(long long i = 1; i <= k; i++) cout << split[i] << ' ';
cout << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Execution timed out |
2074 ms |
364 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2048 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
0 ms |
364 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
1 ms |
364 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Execution timed out |
2078 ms |
364 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2039 ms |
364 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Execution timed out |
2061 ms |
364 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
1132 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
2 |
Correct |
17 ms |
1132 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
3 |
Incorrect |
74 ms |
1132 KB |
contestant didn't find the optimal answer: 497304059415273010 < 497313449256899208 |
4 |
Halted |
0 ms |
0 KB |
- |