Submission #345202

#TimeUsernameProblemLanguageResultExecution timeMemory
345202DrearyJokeSplit the sequence (APIO14_sequence)C++17
0 / 100
110 ms25068 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<bool> vb; typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;} template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;} template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;} template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;} #define deb(x) cout << '>' << #x << ':' << x << endl; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define END '\n' #define inf 9e18 #define ff first #define ss second #define pb push_back const ll maxVal = 1e18; struct Line { ll m, c, idx; Line (int _m, int _c, int _idx) { m = _m; c = _c; idx = _idx; } ll eval(int x) { return m * x + c; } ll getX(Line L) { if (m == L.m) { if (c > L.c) return maxVal; else return -maxVal; } return (L.c - c) / (m - L.m); } }; struct LowerHull { deque<Line> A; void addLine(ll m, ll c, int idx) { Line now(m, c, idx); while((int)A.size() >= 2 && now.getX(A[0]) >= A[0].getX(A[1])) A.pop_front(); A.push_front(now); } pair<ll, int> query(ll x) { if (A.empty()) return {0, 0}; while((int)A.size() >= 2 && A.back().eval(x) <= A[(int)A.size() - 2].eval(x)) A.pop_back(); return {A.back().eval(x), A.back().idx}; } }; void solve(){ int n, k; cin >> n >> k; vll A(n + 1), pref(n + 1, 0), suf(n + 2, 0); for (int i = 1; i <= n; ++i) cin >> A[i], pref[i] = pref[i - 1] + A[i]; for (int i = n; i; --i) suf[i] = suf[i + 1] + A[i]; vvll dp(n + 1, vll(k + 1, 0)); vvi par(n + 1, vi(k + 1, 0)); ll ans = 0; int beg; vector<LowerHull> hulls(k + 1); for (int i = 1; i < n; ++i) { for (int j = 1; j <= k; ++j) { // cout << "CURRENT: " << i << " " << j << " " << l << END; // cout << dp[l - 1][j - 1] << " " << pref[i] << " " << pref[l - 1] << " " << suf[i + 1] << END; ll x = suf[i + 1]; auto u = hulls[j - 1].query(x); ll val = pref[i] * suf[i + 1] + u.ff; // ll val = dp[l - 1][j - 1] + (pref[i] - pref[l - 1]) * (suf[i + 1]); // cout << i << " " << j << " " << u.ff << " " << u.ss << END; if (val >= dp[i][j]) dp[i][j] = val, par[i][j] = u.ss; ll m = -pref[i], c = dp[i][j], idx = i; hulls[j].addLine(m, c, idx); // dp[i][j] = max(dp[i][j], dp[l - 1][j - 1] + (pref[i] - pref[l - 1]) * (suf[i + 1])); if (j == k) { if (dp[i][j] >= ans) ans = dp[i][j], beg = i; ans = max(ans, dp[i][j]); } } } // for (int i = 1; i <= n; ++i) { // for (int j = 1; j <= k; ++j) cout << dp[i][j] << " "; // cout << END; // } // cout << "LO\n"; // for (int i = 1; i <= n; ++i) { // for (int j = 1; j <= k; ++j) cout << par[i][j] << " "; // cout << END; // } int idx = k; vi fin; while(k) fin.pb(beg), beg = par[beg][k--]; cout << ans << END << fin; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; while(t--){ solve(); } return 0; } /* 7 3 4 1 3 4 0 2 3 */

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:105:9: warning: unused variable 'idx' [-Wunused-variable]
  105 |     int idx = k;
      |         ^~~
#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...