/** 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;
};
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 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}); else line.push_back({a , getintersec(a , line[n - 1].X)});
return;
}
i64 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);
}
void add(i64 a , i64 b)
{
addline(Line{a , b});
return;
}
};
const int maxn = 1e4;
const int maxk = 200;
i64 dp[maxn + 2][maxk + 2] , g[maxn + 2] , a[maxn + 2] , pre[maxn + 2];
int trace[maxn + 2][maxk + 2];
int n , k;
void solve()
{
for (int used = 1; used <= k; ++used)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j < i; ++j)
if (minimize(dp[i][used] , dp[j][used - 1] - pre[n] * pre[i - 1] + pre[i - 1] * pre[i - 1] - pre[i - 1] * pre[j - 1] + pre[n] * pre[j - 1]))
trace[i][used] = j;
}
}
}
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);
dp[1][0] = 0;
solve();
i64 answer = LLONG_MAX;
int v = 1 , ks = 1;
for (int i = 1; i <= n; ++i)
if (minimize(answer , dp[i][k]))
v = i - 1 , ks = i;
cout << -dp[ks][k] << '\n';
vector<int> recall;
while (k)
{
recall.emplace_back(v);
v = trace[ks][k] - 1;
ks = trace[ks][k];
--k;
}
reverse(recall.begin() , recall.end());
for (auto& v : recall) cout << v << ' ';
}
Compilation message
sequence.cpp: In member function 'i64 Convex_hull::find(i64)':
sequence.cpp:56:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = low + high >> 1;
| ~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 1 == 1 |
7 |
Correct |
5 ms |
18008 KB |
contestant found the optimal answer: 1 == 1 |
8 |
Correct |
5 ms |
18008 KB |
contestant found the optimal answer: 1 == 1 |
9 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
3 ms |
18008 KB |
contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
3 ms |
18008 KB |
contestant found the optimal answer: 805 == 805 |
16 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 900189994 == 900189994 |
17 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 999919994 == 999919994 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
3 ms |
18008 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
4 ms |
17896 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
3 ms |
18012 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
9 ms |
18244 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
7 ms |
18132 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Correct |
8 ms |
18012 KB |
contestant found the optimal answer: 107630884 == 107630884 |
7 |
Correct |
9 ms |
18240 KB |
contestant found the optimal answer: 475357671774 == 475357671774 |
8 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 193556962 == 193556962 |
9 |
Correct |
4 ms |
18240 KB |
contestant found the optimal answer: 482389919803 == 482389919803 |
10 |
Correct |
4 ms |
18012 KB |
contestant found the optimal answer: 490686959791 == 490686959791 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
20308 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
5 ms |
20060 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
146 ms |
20292 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
5 ms |
20312 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
158 ms |
20280 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
122 ms |
20288 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
145 ms |
20060 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
138 ms |
20304 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
32 ms |
20060 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
60 ms |
20312 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
299 ms |
24408 KB |
contestant found the optimal answer: 1818678304 == 1818678304 |
2 |
Correct |
383 ms |
24408 KB |
contestant found the optimal answer: 1326260195 == 1326260195 |
3 |
Execution timed out |
2057 ms |
24144 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
141 ms |
48972 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |