제출 #142528

#제출 시각아이디문제언어결과실행 시간메모리
142528meatrow수열 (APIO14_sequence)C++17
0 / 100
91 ms7416 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //#pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int mod = 1e9 + 7; const int N = 1e5 + 5; const int K = 205; struct Line { ll k, b; int pos; ll eval(ld x) { return k * x + b; } }; inline ld isec(Line &p, Line &q) { return ((ld)p.b - q.b) / (q.k - p.k); } struct CHT { int s; Line l[N]; int pt; void clr() { s = 0, pt = 0; } void add(Line a) { while(s >= 2 && isec(l[s - 2], l[s - 1]) >= isec(l[s - 1], a)) s--, pt = min(pt, s - 1); l[s++] = a; } pair<ll, int> get(ll x) { while(pt != s - 1 && isec(l[pt], l[pt + 1]) <= x) pt++; return { l[pt].eval(x), l[pt].pos }; } }; int a[N]; ll pref[N]; ll dp[K][N]; int way[K][N]; CHT cht; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for (int i = 1; i <= k; i++) { cht.clr(); for (int j = 1; j <= n; j++) { if (j > i) { auto p = cht.get(pref[j]); dp[i][j] = p.first; way[i][j] = p.second; } if (pref[j]) { cht.add({ pref[j], dp[i - 1][j] - pref[j] * pref[j], j }); } } } cout << dp[k][n] << '\n'; int kek = n; vector<int> ans; for (int i = k; i > 0; i--) { ans.push_back(way[i][kek]); kek = way[i][kek]; } reverse(ans.begin(), ans.end()); for (int i : ans) { cout << i << ' '; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...