#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 110000
int n, k, a[maxn], ps[maxn], dp[maxn][2];
set<pair<pair<int,int>,pair<int,int>>> cht, chtlr;
//cht -> a,b,l,r
//chtlr -> l,r,a,b
int f(int a, int b, int x) {
return a*x + b;
}
dbl interx(int a1, int b1, int a2, int b2) {
return (dbl) (b2-b1)/(a1-a2);
}
void resetcht() {
cht.clear();
chtlr.clear();
cht.insert(mp(mp(0,0),mp(-inf1,+inf1)));
chtlr.insert(mp(mp(-inf1,+inf1),mp(0,0)));
}
void attcht(int a, int b) {
//f(x) = a*x + b
//pega qual o lugar que eu seria colocado no set
auto it = cht.upper_bound(mp(mp(a,b),mp(0,0)));
//left = (beg,it-1)
//right = (it,end-1)
vector<pair<pair<int,int>,pair<int,int>>> rem, add;
int ansr = -inf1;
int ansl = +inf1;
//primeiro tiro tudo da esquerda
auto itl = it;
while(itl != cht.begin()) {
itl--; //ve se consegue tirar it1
int al = itl->fr.fr;
int bl = itl->fr.sc;
int l = itl->sc.fr;
int r = itl->sc.sc;
//se em l o novo for melhor que o antigo, entao apaga o antigo
if(f(a,b,l) >= f(al,bl,l)) {
ansl = l;
ansr = max(ansr,r);
rem.pb(mp(mp(al,bl),mp(l,r)));
}
else if(f(a,b,r) >= f(al,bl,r)) {
//find the intersect (a,b) and (al,bl)
//a != al
//f(a,b) >= f(al,bl) in ceil(x)
int x = ceil(interx(a,b,al,bl));
rem.pb(mp(mp(al,bl),mp(l,r)));
add.pb(mp(mp(al,bl),mp(l,x-1)));
ansr = max(ansr,r);
ansl = x;
break;
}
else {
break;
}
}
auto itr = it;
while(itr != cht.end()) {
//ve se consegue tirar itr
int ar = itr->fr.fr;
int br = itr->fr.sc;
int l = itr->sc.fr;
int r = itr->sc.sc;
//se em r o novo for melhor que o antigo, entao apaga o antigo
if(f(a,b,r) >= f(ar,br,r)) {
ansr = r;
ansl = min(ansl,l);
rem.pb(mp(mp(ar,br),mp(l,r)));
}
else if(f(a,b,l) >= f(ar,br,l)) {
//find the intersect (a,b) and (ar,br)
//a != ar
//f(a,b) >= f(ar,br) at floor(x)
int x = floor(interx(a,b,ar,br));
rem.pb(mp(mp(ar,br),mp(l,r)));
add.pb(mp(mp(ar,br),mp(x+1,r)));
ansr = x;
ansl = min(ansl,l);
break;
}
else {
break;
}
itr++;
}
for(auto x : rem) {
cht.erase(x);
chtlr.erase(mp(x.sc,x.fr));
}
for(auto x : add) {
cht.insert(x);
chtlr.insert(mp(x.sc,x.fr));
}
if(ansl <= ansr) {
cht.insert(mp(mp(a,b),mp(ansl,ansr)));
chtlr.insert(mp(mp(ansl,ansr),mp(a,b)));
}
}
int qrr(int x) {
auto it = chtlr.upper_bound(mp(mp(x,inf),mp(0,0)));
it--;
int a = it->sc.fr;
int b = it->sc.sc;
return f(a,b,x);
}
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
ps[i] = ps[i-1] + a[i];
}
for(int j = 0; j <= k; j++) {
resetcht();
//dp[0][j] = 0
for(int i = 1; i <= n; i++) {
auto qr = qrr(ps[i]);
dp[i][j&1] = qrr(ps[i]);
attcht(ps[i],dp[i][(j+1)&1]-ps[i]*ps[i]);
}
}
cout << dp[n][k&1] << endl;
cout << "1 3 5 " << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
Compilation message
beads.cpp: In function 'void solve()':
beads.cpp:151:18: warning: unused variable 'qr' [-Wunused-variable]
151 | auto qr = qrr(ps[i]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
