Submission #1152865

#TimeUsernameProblemLanguageResultExecution timeMemory
1152865Nuraly_SerikbaySplit the sequence (APIO14_sequence)C++20
71 / 100
106 ms167100 KiB
#include <bits/stdc++.h> //#include "grader.h" #define respagold ios_base::sync_with_stdio(0), cin.tie(0); #define int long long #define aldik int #define ll long long #define int2 __int128_t #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define pb push_back #define ins insert #define lb lower_bound #define ub upper_bound #define pii pair <int, int> #define mkp make_pair using namespace std; const int N = 1e5 + 123; const int inf = 1e18; aldik a[N], b[N], n, m, k, z, w, x, y, mm[N], cc[N]; int dp[N]; aldik par[N][201]; bool nel[N][201]; mt19937 rng( chrono::steady_clock::now().time_since_epoch().count()); int rand( int l, int r ) { uniform_int_distribution <int> uid( l, r ); return uid( rng ); } int calc( int a, int b ) { if( mm[a] == mm[b] ) return inf; return ( cc[b] - cc[a] ) / ( mm[a] - mm[b] ); } vector <int> ve; pair <int, pii> sv[N], sv1[N]; aldik siz; void add( int nw ) { siz = sz(ve); while( siz > 1 && calc( ve[siz - 2], ve[siz - 1] ) > calc( ve[siz - 1], nw ) ) ve.pop_back(), siz --; ve.pb(nw); } pii get( int x ) { int l = 0, r = sz(ve) - 1, res = 0; while( l <= r ) { int md = ( l + r ) >> 1; if(( md == 0 ? -inf : calc(ve[md], ve[md - 1]) ) < x ) l = md + 1, res = md; else r = md - 1; } return { mm[ve[res]] * x + cc[ve[res]], ve[res] }; } void solve() { cin >> n >> k; FOR( i, 1, n, 1 ) cin >> a[i], b[i] = b[i - 1] + a[i]; mm[0] = cc[0] = 0; sv1[0].F = 0; FOR( bl, 1, k, 1 ) { FOR( i, bl, n - k + bl - 1, 1 ) { // for i find k that ( dp[k] + sum(k + 1, i) * sum(i + 1, n) ) is max // dp[i] = dp[k] + ( b[i] - b[k] ) * ( b[n] - b[i] ) // dp[i] = dp[k] + b[i] * b[n] - b[i] * b[i] - b[k] * b[n] + b[k] * b[i]; // dp[i] = ( dp[k] - b[k] * b[n] ) + ( b[i] * b[n] - b[i] * b[i] ) + ( b[k] * b[i] ) add( sv1[i - 1].F ); pii j = get( b[i] ); dp[i] = j.F + b[i] * b[n] - b[i] * b[i]; sv[i] = { i, { b[i], dp[i] - b[i] * b[n] }}; par[i][bl] = j.S; } ve.clear(); FOR( i, 1, n, 1 ) sv1[i] = sv[i], mm[i] = sv[i].S.F, cc[i] = sv[i].S.S; } int ans = -inf; aldik id = 0; FOR( i, 1, n - 1, 1 ) { if( dp[i] >= ans ) ans = dp[i], id = i; } vector <aldik> v; FORR( blo, k, 1, 1 ) v.pb( id ), id = par[id][blo]; reverse( all( v )); cout << ans << '\n'; for( auto i : v ) cout << i << ' '; } signed main() { // freopen("connect.in", "r", stdin); // freopen("connect.out", "w", stdout); int test = 1; if( !test ) cin >> test; while( test -- ) { solve(); } } // solved by KluydQ
#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...