Submission #126493

#TimeUsernameProblemLanguageResultExecution timeMemory
126493dragoonSplit the sequence (APIO14_sequence)C++14
71 / 100
2077 ms92520 KiB
//#pragma GCC optimize("Ofast") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma warning(disable:4786) #pragma warning(disable:4996) #include <ctime> #include<list> #include <numeric> #include<bitset> #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<set> #include<map> #include<functional> #include<string> #include<cstring> #include<cstdlib> #include<queue> #include<utility> #include<fstream> #include<sstream> #include<cmath> #include<stack> #include<assert.h> #include<unordered_map> #include<unordered_set> #include <array> using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } template<class c> typename enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) { cerr << boolalpha << i; return *this; } template<class c, int=0> typename enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) { return *this << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define watch(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define MEM(a, b) memset(a, (b), sizeof(a)) #define CLR(a) memset(a, 0, sizeof(a)) #define MAX(a, b) ((a) > (b) ? (a) : (b)) #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) ) #define S(X) ( (X) * (X) ) #define SZ(V) (int )V.size() #define FORN(i, n) for(int i = 0; i < n; i++) #define FORAB(i, a, b) for(int i = a; i <= b; i++) #define ALL(V) V.begin(), V.end() #define IN(A, B, C) ((B) <= (A) && (A) <= (C)) #define AIN(A, B, C) assert(IN(A, B, C)) //typedef int LL; typedef long long int LL; //typedef __int128 LLL; typedef long long LLL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef pair<double, double> PDD; typedef vector<int> VI; typedef vector<LL> VL; typedef vector<PLL > VPL; typedef vector<PII > VP; typedef vector<double> VD; typedef long double ld; template<class T=LL> struct Line { int id; // y = mx + c T m, c; // The line starts from start_x. static const LL MIN_START_X = 0; long double start_x; LL Eval(LL x) { return m * x + c; } long double Eval(long double x) { return m * x + c; } long double Intersect(const Line& other) { // mx + c = other.m * x + other.c long double num = other.c - c; long double den = m - other.m; assert(m != other.m); return num / den; } }; template<class T=LL> struct StaticCHT { static const int MIN_TYPE = 0; static const int MAX_TYPE = 1; int type = MAX_TYPE; // Stores convex hull lines. vector<Line<T>> ch; // Used if the query x is increasing. // id of the current segment. int id = 0; void InsertLine(Line<T> cur) { int sz = ch.size(); if (sz) assert(type == MAX_TYPE || (ch[sz - 1].m > cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c >= cur.c))); if (sz) assert(type == MIN_TYPE || (ch[sz - 1].m < cur.m || (ch[sz - 1].m == cur.m && ch[sz - 1].c <= cur.c))); if (sz) { if (ch[sz - 1].c == cur.c && ch[sz - 1].m == cur.m) return; } while (sz > 1) { double left_side = (double(ch[sz - 1].c - ch[sz - 2].c)) * (ch[sz - 2].m - cur.m); double right_side = (double(ch[sz - 2].m - ch[sz - 1].m)) * (cur.c - ch[sz - 2].c); if ((left_side >= right_side)) { ch.pop_back(); sz--; } else break; } if (!sz) cur.start_x = Line<T>::MIN_START_X; else cur.start_x = ch[sz - 1].Intersect(cur); ch.push_back(cur); } pair<int, T> SlidingEval(T x) { // There should be at least one element. assert(SZ(ch) > 0); // May be ch was updated by the time? id = MIN(id, SZ(ch)); while (id + 1 < SZ(ch) && ((type == MIN_TYPE && ch[id].Eval(x) > ch[id + 1].Eval(x)) || (type == MAX_TYPE && ch[id].Eval(x) < ch[id + 1].Eval(x)))) { id++; } return { ch[id].id, ch[id].Eval(x) }; } pair<int, T> Eval(T x) { int lo = 0, hi = SZ(ch) - 1; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (ch[mid].start_x > x) hi = mid - 1; else lo = mid; } return { ch[lo].id, ch[lo].Eval(x) }; } }; LL num[100005], sum[100005]; int n, k; LL dp[2][100005]; int par[202][100005]; void solve(int ks) { scanf("%d %d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", &num[i]); sum[i] = sum[i - 1] + num[i]; } for (int i = 1; i <= n; i++) dp[1][i] = 0, par[1][i] = -1; int u = 1, v = 0; for (int i = 2; i <= k + 1; i++) { StaticCHT<LL> cht; for (int j = i; j <= n; j++) { cht.InsertLine({j - 1, sum[j - 1], dp[u][j - 1] - S(sum[j - 1])}); auto ret = cht.SlidingEval(sum[j]); dp[v][j] = ret.second; par[i][j] = ret.first; } swap(u, v); } printf("%lld\n", dp[u][n]); VI V; int now = n, cur = k + 1; while (now != -1) { V.push_back(now); now = par[cur][now]; cur--; } for (int i = SZ(V) - 1; i >= 1; i--) { printf("%d", V[i]); if (i > 1) printf(" "); } printf("\n"); } int main() { #ifdef LOCAL double start_time = clock(); freopen("C:\\Home\\ContestCodes\\sample.in", "r", stdin); // freopen("out.out", "w", stdout); #endif if (0) { int T; scanf("%d", &T); //AIN(T, 1, 25); for (int ks = 1; ks <= T; ks++) solve(ks); } else { solve(0); } #ifdef LOCAL double end_time = clock(); fprintf(stderr, "Time = %lf\n", (end_time - start_time) / CLOCKS_PER_SEC); #endif return 0; }

Compilation message (stderr)

sequence.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4786)
 
sequence.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 
sequence.cpp: In function 'void solve(int)':
sequence.cpp:178:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &num[i]);
   ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:222:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T);
   ~~~~~^~~~~~~~~~
#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...