/** 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 = 1e5;
const int maxk = 200;
i64 dp[maxn + 2] , g[maxn + 2] , a[maxn + 2] , pre[maxn + 2];
int trace[maxk + 2][maxn + 2];
int n , k;
void solve(int idx)
{
Convex_hull bag1;
for (int i = 1; i <= n; ++i) dp[i] = LLONG_MAX;
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;
}
if (g[i] != LLONG_MAX)
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 << -g[ks] << '\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 |
5980 KB |
contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 999 == 999 |
| 3 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 0 == 0 |
| 4 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 1542524 == 1542524 |
| 5 |
Correct |
2 ms |
8028 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
| 6 |
Incorrect |
1 ms |
5980 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 |
5976 KB |
contestant found the optimal answer: 1093956 == 1093956 |
| 2 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 302460000 == 302460000 |
| 3 |
Correct |
3 ms |
24412 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
| 4 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
| 5 |
Correct |
2 ms |
8024 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
| 6 |
Correct |
2 ms |
8028 KB |
contestant found the optimal answer: 933702 == 933702 |
| 7 |
Correct |
2 ms |
14172 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
| 8 |
Incorrect |
2 ms |
10076 KB |
contestant didn't find the optimal answer: 681371 < 687136 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5980 KB |
contestant found the optimal answer: 610590000 == 610590000 |
| 2 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 311760000 == 311760000 |
| 3 |
Correct |
10 ms |
82008 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
| 4 |
Correct |
1 ms |
5980 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
| 5 |
Incorrect |
8 ms |
59440 KB |
contestant didn't find the optimal answer: 1019625816 < 1019625819 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5980 KB |
contestant found the optimal answer: 21503404 == 21503404 |
| 2 |
Correct |
1 ms |
5976 KB |
contestant found the optimal answer: 140412195 == 140412195 |
| 3 |
Correct |
13 ms |
82012 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
| 4 |
Correct |
1 ms |
6232 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
| 5 |
Correct |
15 ms |
82044 KB |
contestant found the optimal answer: 679388326 == 679388326 |
| 6 |
Correct |
14 ms |
71768 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
| 7 |
Correct |
15 ms |
81996 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
| 8 |
Incorrect |
14 ms |
82012 KB |
contestant didn't find the optimal answer: 31092578772 < 31093317350 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6624 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
| 2 |
Correct |
3 ms |
6492 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
| 3 |
Correct |
99 ms |
82836 KB |
contestant found the optimal answer: 4973126687469639 == 4973126687469639 |
| 4 |
Correct |
3 ms |
6816 KB |
contestant found the optimal answer: 3748491676694116 == 3748491676694116 |
| 5 |
Correct |
63 ms |
51744 KB |
contestant found the optimal answer: 1085432199 == 1085432199 |
| 6 |
Correct |
79 ms |
60184 KB |
contestant found the optimal answer: 514790755404 == 514790755404 |
| 7 |
Correct |
87 ms |
64288 KB |
contestant found the optimal answer: 1256105310476641 == 1256105310476641 |
| 8 |
Incorrect |
77 ms |
54060 KB |
contestant didn't find the optimal answer: 3099384768442 < 3099592898816 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
14496 KB |
contestant found the optimal answer: 19795776960 == 19795776960 |
| 2 |
Correct |
19 ms |
13324 KB |
contestant found the optimal answer: 19874432173 == 19874432173 |
| 3 |
Correct |
949 ms |
90716 KB |
contestant found the optimal answer: 497313449256899208 == 497313449256899208 |
| 4 |
Correct |
18 ms |
13608 KB |
contestant found the optimal answer: 374850090734572421 == 374850090734572421 |
| 5 |
Correct |
1154 ms |
90244 KB |
contestant found the optimal answer: 36183271951 == 36183271951 |
| 6 |
Correct |
768 ms |
64196 KB |
contestant found the optimal answer: 51629847150471 == 51629847150471 |
| 7 |
Correct |
872 ms |
72144 KB |
contestant found the optimal answer: 124074747024496432 == 124074747024496432 |
| 8 |
Incorrect |
738 ms |
60648 KB |
contestant didn't find the optimal answer: 309938524037863 < 309959349080800 |
| 9 |
Halted |
0 ms |
0 KB |
- |
