제출 #250666

#제출 시각아이디문제언어결과실행 시간메모리
250666Evirir수열 (APIO14_sequence)C++17
60 / 100
2082 ms93944 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 998244353; struct Line{ mutable ll m,b,p; bool operator<(const Line& o) const { return m < o.m; } bool operator<(ll x) const { return p < x; } inline ll eval(ll x) { return m * x + b; } }; struct ConvexHullDynamic: multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) const ll inf = LLONG_MAX; bool Max = 1; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return false; } if (x->m == y->m) x->p = x->b > y->b ? inf : -inf; else x->p = div(y->b - x->b, x->m - y->m); return x->p >= y->p; } void addline(ll m, ll b) { if(!Max) { m=-m; b=-b; } auto z = insert({m, b, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } Line query(ll x) { if(empty()) return Line{0,0,0}; auto l = *lower_bound(x); return l; } }; const bool DEBUG = 0; const int MAXN = 100005; const int MAXK = 205; int n,K; ll s[MAXN], dp[MAXK][MAXN], nxt[MAXK][MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>K; forn(i,0,n){ cin>>s[i]; if(i>0) s[i]+=s[i-1]; } ConvexHullDynamic cht; fore(i,1,K) { cht.clear(); forn(j,0,n) { Line res = cht.query(s[j]); nxt[i][j] = res.m; dp[i][j] = res.eval(s[j]); cht.addline(s[j], dp[i-1][j]-s[j]*s[j]); } } vi ans; int cur=n-1; for(int i=K;i>=1;i--){ for(int j=cur-1;j>=0;j--){ if(s[j]==nxt[i][cur]){ ans.pb(j); cur=j; break; } } } cout<<dp[K][n-1]<<'\n'; for(ll x: ans) cout<<x+1<<" "; cout<<'\n'; return 0; }
#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...