Submission #1152831

#TimeUsernameProblemLanguageResultExecution timeMemory
1152831WebblySplit the sequence (APIO14_sequence)C++20
71 / 100
130 ms196608 KiB
// Problem: P2 - Split the Sequence // Contest: DMOJ - APIO '14 // URL: https://dmoj.ca/problem/apio14p2 // Memory Limit: 128 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // // Solution // Webbly, 27.01.2023 // // // Arsen ne katai // // /////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include<bits/stdc++.h> /** #include <algorithm> #include <iostream> #include <vector> #include <queue> #include <cmath> #include <map> #include <set> #include <time.h> */ //#pragma GCC optimize("O3") //#pragma GCC optimize("fast-loops") //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") /** #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC target("avx") */ #define ll long long #define kebzaro ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define pb push_back #define mp make_pair #define all(x) x.begin(),x.end() #define flush cout.flush() using namespace std; const ll mod = (ll)1e9 + 7, mod3 = 998244353, inf = (ll)2e15, P = 31; void judge(string name){ if (name.size()){ freopen((name + ".in").c_str(), "r", stdin); freopen((name + "out").c_str(), "w", stdout); } } ll rnd(){ ll x = rand(); return rand() ^ x; } ll binpow (ll a, ll b){ ll ans = 1; while(b){ if (b & 1){ ans *= a; ans %= mod; } b >>= 1; a *= a; a %= mod; } return ans; } ll gcd(ll a, ll b){ return (b ? gcd(b, a % b) : a); } ll lcm(ll a, ll b){ return a / gcd(a, b) * b; } struct tr{ ll four, seven, inc, dec; }; struct T{ ll l, r, val, ind; }; ll n, m, k, a[500005], to[500005][205], p[500005], dp[100005][205], L[100005][205]; struct line{ ll k, c, ind; }; ll R[205]; line t[100005][205]; double inter(line a, line b){ if (a.k == b.k) return -1; return (b.c - a.c) / (a.k - b.k); } void add(line cur, ll ver){ if (!R[ver]){ t[++R[ver]][ver] = cur; return; } while(1){ if (R[ver] == 0) break; if (t[R[ver]][ver].k == cur.k && cur.c > t[R[ver]][ver].c){ R[ver]--; } else if (inter(t[R[ver]][ver], cur) < L[R[ver]][ver]){ R[ver]--; } else break; } t[++R[ver]][ver] = cur; if (R[ver] > 1) L[R[ver]][ver] = inter(t[R[ver] - 1][ver], cur); } line get(ll x, ll ver){ ll l = 1, r = R[ver], ans = 1; while (l <= r){ ll mid = (l + r) >> 1; if (L[mid][ver] < x){ ans = mid; l = mid + 1; } else r = mid - 1; } return t[ans][ver]; } void sarsen(){ cin >> n >> k; for (ll i = 1; i <= n; i++){ cin >> a[i]; p[i] = p[i - 1] + a[i]; } for (ll j = 1; j < n; j++){ for (ll i = k; i >= 1; i--){ if (j >= i){ line cur = get(p[j], i - 1); dp[j][i] = cur.c + p[n] * p[j] - p[j] * p[j] + p[j] * cur.k; add({p[j], dp[j][i] - p[n] * p[j], j}, i); to[j][i] = cur.ind; } } } ll from = 1; for (ll i = k; i <= n; i++){ if (dp[i][k] > dp[n][k]) from = i; dp[n][k] = max(dp[n][k], dp[i][k]); } cout << dp[n][k] << '\n'; vector <ll> ans; while(from != 0){ ans.pb(from); from = to[from][k--]; } reverse(all(ans)); for (auto i : ans) cout << i << ' '; } int main(){ kebzaro judge(""); ll TT = 1, tests = 1; //cin >> TT; while(TT--){ //cout << "Case " << tests << ": "; sarsen(); //tests++; } return 0; } /** 1 2 3 4 5 6 1 5 = 20 + 99 = 119 5 1 = 110 + 9 */

Compilation message (stderr)

sequence.cpp: In function 'void judge(std::string)':
sequence.cpp:95:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 freopen((name + ".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:96:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 freopen((name + "out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...