Submission #1111803

#TimeUsernameProblemLanguageResultExecution timeMemory
1111803ljtunasSplit the sequence (APIO14_sequence)C++17
0 / 100
40 ms131072 KiB
// author : anhtun_hi , nqg #include <bits/stdc++.h> #define ll long long #define ii pair<ll, ll> #define fi first #define se second #define all(x) x.begin(), x.end() #define reset(h, v) memset(h, v, sizeof h) #define Forv(i, a) for(auto& i : a) #define For(i, a, b) for(int i = a; i <= b; ++i) #define Ford(i, a, b) for(int i = a; i >= b; --i) #define c_bit(i) __builtin_popcountll(i) #define Bit(mask, i) ((mask >> i) & 1LL) #define onbit(mask, i) ((mask) bitor (1LL << i)) #define offbit(mask, i) ((mask) &~ (1LL << i)) using namespace std; namespace std { template <typename T, int D> struct _vector : public vector <_vector <T, D - 1>> { static_assert(D >= 1, "Dimension must be positive!"); template <typename... Args> _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {} }; template <typename T> struct _vector <T, 1> : public vector <T> { _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {} }; template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;} template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;} } const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5; const int MAXN = 1e5 + 5; const ll mod = 1e9 + 7; const ll oo = 1e18; //#define int long long int n, k; ll dp[MAXN][205], a[MAXN]; struct convexhulltrick{ struct point { ll x, y; ll dot(point p) { return x * p.x + y * p.y; } ll cross(point p) { return x * p.y - y * p.x; } point conj() { return {-y, x}; } point vt(point p) { return {x - p.x, y - p.y}; } }; vector<point> hull, vec; void add(ll a, ll b) { auto p = point{a, b}; while (vec.size() >= 1 && vec.back().dot(p.vt(hull.back())) <= 0) { // <= 0 neu max vec.pop_back(); hull.pop_back(); } if (!hull.empty()) vec.push_back(p.vt(hull.back()).conj()); hull.push_back(p); } ll get(ll x) { auto query = point{x, 1}; auto it = lower_bound(vec.begin(), vec.end(), query, [](point a, point b) { return a.cross(b) < 0; // <0 neu max }); return query.dot(hull[it - vec.begin()]); } } cvh[205]; void Solve() { cin >> n >> k; For(i, 1, n) cin >> a[i], a[i] += a[i - 1]; reset(dp, -0x3f); dp[0][0] = 0; cvh[0].add(0, 0); For(i, 1, n) { For(_k, 1, min(i, k)){ // For(j, 0, i - 1){ // maximize(dp[i][_k], dp[j][_k - 1] + a[i] * (a[n] - a[i]) + (- a[j]) * (a[n] - a[i])); // } dp[i][_k] = cvh[_k - 1].get(a[n] - a[i]) + a[i] * (a[n] - a[i]); } For(_k, 1, min(i, k)){ cvh[_k].add(-a[i], dp[i][_k]); } } ll ans = 0, i;; int _k = k; For(j, 1, n) if(maximize(ans, dp[j][k])) i = j; vector<int> List; while(i){ // cerr << i << '\n'; List.push_back(i); Ford(j, i - 1, 0) if(dp[i][_k] == dp[j][_k - 1] + a[i] * (a[n] - a[i]) + (- a[j]) * (a[n] - a[i])){ --_k; i = j; break; } } cout << ans << '\n'; reverse(all(List)); Forv(x, List) cout << x << ' '; } int32_t main() { cin.tie(0) -> sync_with_stdio(0); if(fopen("APIO14_sequence.inp", "r")) { freopen("APIO14_sequence.inp", "r", stdin); freopen("APIO14_sequence.out", "w", stdout); } int t = 1; // cin >> t; for (int test = 1; test <= t; test++) { Solve(); } return 0; }

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("APIO14_sequence.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("APIO14_sequence.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'void Solve()':
sequence.cpp:103:23: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
  103 |         List.push_back(i);
      |         ~~~~~~~~~~~~~~^~~
#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...