/** author : _RAIN_ **/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ui64 = unsigned long long;
#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
template<class T>
bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
T lcm(T x , T y) {return (x * y) / gcd(x , y);}
#define sz(x) (int)((x).size())
struct Line
{
i64 a , b;
Line(i64 a , i64 b) : a(a) , b(b) {};
};
struct Hull
{
Line X;
double intersec;
int idx;
};
class Convex_hull
{
public:
vector<Hull> line;
double getintersec(Line x , Line y)
{
return (double)(y.b - x.b) / (x.a - y.a);
}
i64 getval(Line a , i64 x)
{
return a.a * x + a.b;
}
void addline(Line a , int idx)
{
int n = sz(line);
while (n > 1 && getintersec(line[n - 2].X , a) <= getintersec(line[n - 1].X , line[n - 2].X))
line.pop_back() , --n;
if (!sz(line))
line.push_back({a , LLONG_MIN , idx});
else line.push_back({a , getintersec(a , line[n - 1].X), idx});
return;
}
pair<i64 , int> find(i64 val)
{
int low = 0 , high = sz(line) - 1 , p = 0;
while (low <= high)
{
int mid = low + high >> 1;
if (line[mid].intersec <= val) p = mid , low = mid + 1;
else high = mid - 1;
}
return {getval(line[p].X , val) , line[p].idx};
}
void add(i64 a , i64 b , int idx)
{
addline(Line{a , b} , idx);
return;
}
};
const int maxn = 1e4;
const int maxk = 200;
i64 dp[maxn + 2] , g[maxn + 2] , a[maxn + 2] , pre[maxn + 2];
int trace[maxn + 2][maxk + 2];
int n , k;
void solve(int idx)
{
Convex_hull bag1;
for (int i = 1; i <= n; ++i)
{
if (bag1.line.size())
{
pair<i64 , int> val = bag1.find(pre[i - 1]);
dp[i] = val.first - pre[n] * pre[i - 1] + pre[i - 1] * pre[i - 1];
trace[idx][i] = val.second;
}
bag1.add(-pre[i - 1] , pre[n] * pre[i - 1] + g[i] , i);
}
for (int i = 1; i <= n; ++i) g[i] = dp[i];
}
int32_t main(void)
{
cin.tie(nullptr)->sync_with_stdio(false);
const string name = "main";
if (fopen((name + ".inp").c_str() , "r"))
{
(void)!freopen((name + ".inp").c_str() , "r" , stdin);
(void)!freopen((name + ".out").c_str() , "w+", stdout);
}
cin >> n >> k;
memset(pre , 0 , sizeof pre);
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
memset(dp , 0x3f , sizeof dp);
memset(g , 0x3f , sizeof g);
g[1] = 0;
for (int i = 1; i <= k; ++i) solve(i);
i64 answer = LLONG_MAX;
int v = 1 , ks = 1;
for (int i = 1; i <= n; ++i)
if (minimize(answer , g[i]))
v = i - 1 , ks = i;
cout << -answer << '\n';
vector<int> recall;
while (k)
{
recall.emplace_back(v);
v = trace[k][ks] - 1;
ks = trace[k][ks];
--k;
}
reverse(recall.begin() , recall.end());
for (auto& v : recall) cout << v << ' ';
}
Compilation message
sequence.cpp: In member function 'std::pair<long long int, int> Convex_hull::find(i64)':
sequence.cpp:58:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int mid = low + high >> 1;
| ~~~~^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Incorrect |
0 ms |
604 KB |
contestant didn't find the optimal answer: 0 < 1 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
0 ms |
600 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
1 ms |
760 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
1 ms |
600 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Incorrect |
0 ms |
604 KB |
declared answer doesn't correspond to the split scheme: declared = -4557430888798143263, real = 687136 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
1 ms |
860 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
0 ms |
604 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
1 ms |
604 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
1 ms |
860 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
2 ms |
860 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Incorrect |
1 ms |
604 KB |
declared answer doesn't correspond to the split scheme: declared = -4557430888605273437, real = 193556962 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
604 KB |
declared answer doesn't correspond to the split scheme: declared = 21503404, real = 21502183 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1252 KB |
declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1814947614 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
1116 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |