제출 #369929

#제출 시각아이디문제언어결과실행 시간메모리
369929EIMONIM수열 (APIO14_sequence)C++14
11 / 100
75 ms12464 KiB
#include <bits/stdc++.h> #define pb push_back #define all(x) x.begin(),x.end() using namespace std; namespace Orig{ typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 1e5 + 10; const ll maxk = 205; const ll mod = 1e9 + 7; const ll inf = 1e9; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) ll n, k, a[maxn], ps[maxn], dp[2][maxn]; int par[maxk][maxn]; vector<pll> vec; vector<int> v2; void add(ll x, ll y, ll i){ if(vec.empty()){ vec.pb(Mp(x, y)); v2.pb(i); return; } if(vec.back().F == x) return; while(Sz(vec) > 1){ if((y - vec[Sz(vec) - 2].S) * (vec[Sz(vec) - 2].F - vec[Sz(vec) - 1].F) < (vec[Sz(vec) - 1].S - vec[Sz(vec) - 2].S) * (vec[Sz(vec) - 2].F - x)){ vec.pop_back(); v2.pop_back(); } else break; } vec.pb(Mp(x, y)); v2.pb(i); return; } void calc(){ for(ll i = 1; i <= n; i++){ ps[i] = ps[i - 1] + a[i]; dp[0][i] = ps[i] * ps[i]; } for(ll i = 1; i <= k; i++){ vec.clear(); v2.clear(); ll p = 0; for(ll j = i + 1; j <= n; j++){ add(-ps[j - 1], ps[j - 1] * ps[j - 1] + dp[i - 1 & 1][j - 1], j - 1); p = min(p, Sz(vec) - 1); while(p < Sz(vec) - 1 && 2 * ps[j] * (vec[p + 1].F - vec[p].F) <= (vec[p].S - vec[p + 1].S)) p++; dp[i & 1][j] = ps[j] * ps[j] + 2 * ps[j] * vec[p].F + vec[p].S; par[i][j] = v2[p]; } } // cout << (ps[n] * ps[n] - dp[k & 1][n]) / 2 << "\n"; for(ll i = 0; i < k; i++){ n = par[k - i][n]; cout << n << " "; } } }; #define int int64_t #define ii pair<int,int> #define x first #define y second #define vi vector<int> #define vvi vector<vi> #define vii vector<ii> #define vvii vector<vii> #define vb vector<bool> #define vvb vector<vb> #define loop(i,s,e) for(int i=(s);i<(e);i++) #define loopr(i,s,e) for(int i=(e)-1;i>=(s);i--) #define chkmax(a,b) a = max(a,b) #define chkmin(a,b) a=min(a,b) const int INF = 1e18, MOD = 1e9 + 7; /*mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); auto unidist = uniform_int_distribution<int>(0, MAXN);*/ const int N = 2e5; struct CHT { struct Line { int m, b, c; int operator()(int x) { return m * x + b; } } dq[N * 2]; int l, r; void init() { dq[0] = {0, 0, 0}; l = 0, r = 1; } bool better_ins(Line& L, Line& L1, Line& L2) { int b1 = (L.b - L2.b) * (L2.m - L1.m), b2 = (L2.m - L.m) * (L1.b - L2.b); return b1 < b2 || (b1 == b2 && L.c > L1.c); } bool better_qry(Line& L1, Line& L2, int x) { int b1 = L1(x), b2 = L2(x); return b1 > b2 || (b1 == b2 && L1.c < L2.c); } void insert(Line L) { while(r - l >= 2 && better_ins(L, dq[r - 1], dq[r - 2])) --r; dq[r++] = L; } ii query(int x) { while(r - l >= 2 && better_qry(dq[l], dq[l + 1], x)) ++l; return {dq[l](x), dq[l].c}; } } cht; int n, k, a[N], pre[N], dp[N], cnt[N]; void init() { cin >> n >> k; k++; loop(i,0,n) cin >> a[i], pre[i+1] = pre[i] + a[i]; } ii calc(int x) { dp[0] = cnt[0] = 0; cht.init(); loop(i,1,n+1){ ii qry = cht.query(pre[i]); dp[i] = pre[i] * pre[i] + x + qry.x; cnt[i] = qry.y + 1; cht.insert({-2 * pre[i], dp[i] + pre[i] * pre[i], cnt[i]}); } return {dp[n], cnt[n]}; } int solve() { int l = 0, r = pre[n] * pre[n], ans = -1; while(l <= r) { int mid = l + (r - l) / 2; ii res = calc(mid); if(res.y >= k) ans = res.x - k * mid, l = mid + 1; else r = mid - 1; } return ans; } int32_t main(){ init(); cout << (pre[n]*pre[n] - solve())/2 << endl; Orig::n = n, Orig::k = k-1; loop(i,0,n) Orig::a[i+1] = a[i]; Orig::calc(); return 0; } /* color a cls g++ a.cpp -o a & a 7 3 4 1 3 4 0 2 3 for /l %x in (1,1,16) do a < out\big%x.in > out\big%x.out */

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void Orig::calc()':
sequence.cpp:55:62: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   55 |                 add(-ps[j - 1], ps[j - 1] * ps[j - 1] + dp[i - 1 & 1][j - 1], j - 1);
      |                                                            ~~^~~
#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...