Submission #257547

#TimeUsernameProblemLanguageResultExecution timeMemory
257547vaavenSplit the sequence (APIO14_sequence)C++14
0 / 100
73 ms131076 KiB
/* `-:://:::- `//:-------:/:` .+:--.......--:+` `+:--..`````..--//` .o:--..`` ``..--:o` .o:--...```..---+/` `/y+o/---....---:+o. `...````-os+/:---:/+o/--.` `-/+++++/:. `...` :h+d+oooo+/+-` ... `/++//:::://++-`....` -.`//````````:` `..` `o+/::------://o/` `-` -. -` `..` `---.-o/:./o/::-..``..-ЗАПУСКАЕМ .. .. -` `... ``..`` `....o+:-++/:--.```..-://s. `-` .- -` `-o: .-//::::/:-` `:s+/:--....-::/+s-` .- `- -` -///:--------:/:` ./s+//:::::://oo-``..НЕЙРОННУЮ: СЕТЬ:::::::-`РАБОТЯГИ `+:--........--:/` .:ooo+++++osso-` `.:-...`/` ./::-------:/:` -` :+--..``````.--:+:...-+:-` `.-/+++++/+-.-` -. ``:so:/:--.......--:+` `-```````o+/+--..`````..--:o/-..:s+:. ```````:``.. `-` -` `+:--..`````..--/+-.../.`````..-o:--.......---/o. ` `: `:- -. .o:--..`` ``..--:o` `-` `:o+:--------:+o-` `-`-... .. .o/--...```..--:+/` `-` `oy/so/////++o/.` -/` `-` `- ``+s/o/:---...---:++. `-` .-../d://///:-.` `.---..``-..- .-/..`````-oo+/:::::/+o+- `-``-` `-. ```` `:++++/+++++- ..``.-/:` /y-:/++o++/:.`..` ./. `- -++/::::::://+/..:-``:` .. `-.` ```.``` `..` `..`-` `- `` -o//:--....-::/++` -.-` `-`.-` `..`..` `-.- -----ss+:++/:--.```..-://s. /. `:: `-:. ./` `````/:..+o/::-..``.--:/+s. ..-` `-``-` ..` `-` `-`-` `-s+/::-----::/+oo---``-` .. .:- ``` .-` .-.- `-` `:oo+//::://+os/..:`..-/:` :y.-:::::::.`.-` ./-` `-` `./+oooooooo+/.`- .-:...`.. .//:-------://` `- `..` `:. ``.-::::-.``-/` `-` `- `oo:+:--.......--:/` `- `.:--h.``..``` -.-`.- .- `+:--..`````..--//` `- /s-//::::::::. -` `/- .. .o:--..`` ``..--:o.```.- `//:--------://` -` .-`.-` -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+` ..`-. `-. ``:os:o/:---...---:++. `- ``///+:-..``````.--:+-````-.` `.:///////.-` .:-..` -``-+o+/:::::/+o/. `- `:+:-..`````..--:o/:--/ys+- `-++///////+o/. ``....`-. :` `.:++++++/:.` .- -o/---......---/o. `.` `++//:-----::/+o:..` .-` : ``````` .- `+so+:--------:++-` `````:-``:o/::-..`..--:/+o` -. `- .- `../../+o+////+o+:.` -----syo/o+/:--.```..-://s. .-` `- .- `... ``-:////:-`` .` `/s//:--....-::/+s. -. `-` .- `..` .+o+/:::--:://+s/-..` .::+y ``` .- `..` ./oo++////+oso-` `.... :y-+:::::::/` ... `.:+oooooo/-` `....-. .//:-------:/:-.` ``...`` /+:+:--.......--:+` `+:--..`````..--//` .o:--..`` ``..--:o` .+/--...```..--:+/` `-o/:---...---:++. `-+o+/:---:/+o/. `.:+oooo+/-.` `````` */ // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("fast-math") // #pragma GCC optimize("section-anchors") // #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") // #pragma GCC optimize("vpt") // #pragma GCC optimize("rename-registers") // #pragma GCC optimize("move-loop-invariants") // #pragma GCC optimize("unswitch-loops") // #pragma GCC optimize("function-sections") // #pragma GCC optimize("data-sections") // #pragma GCC optimize("branch-target-load-optimize") // #pragma GCC optimize("branch-target-load-optimize2") // #pragma GCC optimize("btr-bb-exclusive") // #pragma comment(linker, "/STACK:367077216") #include <iostream> #include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <tuple> #include <math.h> #include <set> #include <stack> #include <bitset> #include <map> #include <queue> #include <random> #include <unordered_set> #include <unordered_map> #define DEBUG #define fi first #define se second #define pqueue priority_queue #define pb(x) push_back(x) //#define endl '\n' #define all(x) x.begin(), x.end() #define int long long #define mk(a, b) make_pair(a, b) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ull> vull; typedef vector<ll> vll; // typedef tuple<ll, ll, ll> tiii; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef vector<bool> vb; typedef vector<string> vs; typedef vector< vector<ll> > vvll; typedef vector<char> vc; const int inf = 1e9 + 228; const ll infll = 1e18; const ll MOD = 1e9 + 7; //static const int maxn = 1e6 + 228; const ld eps = 1e-6; const ld eps2 = 1e-9; const ll MOD2 = 998244353; const ll dosz = 5e5; const ll SZ = (1<<18); const ld PI = atan2l(0, -1); void fast_io(){ ios_base::sync_with_stdio(0); cin.tie(0); // freopen("a.in", "r", stdin); // freopen("logs.out", "w", stdout); } const int maxn = 1e5 + 228; int dp[maxn][201]; int nums[maxn]; int pref[maxn]; int p[maxn][201]; int sum(int l, int r){ return pref[r]-pref[l-1]; } void solve(){ int n, k; cin >> n >> k; for(int i=1; i<=n; i++){ cin >> nums[i]; pref[i] = pref[i-1]+nums[i]; } for(int i=0; i<maxn; i++) for(int j=0; j<201; j++) p[i][j] = -1; for(int i=1; i<=n; i++){ dp[i][1] = sum(1, i)*sum(i+1, n); } for(int j=2; j<=k; j++){ for(int i=j; i<n; i++){ int l = j-1, r = i-1; while(r-l>=3){ int m1 = l+(r-l)/3; int m2 = r-(r-l)/3; int ans1 = dp[m1][j-1] + sum(m1+1, i)*sum(i+1, n); int ans2 = dp[m2][j-1] + sum(m2+1, i)*sum(i+1, n); if(ans1>ans2) r = m2; else l = m1; } for(int d=l; d<=r; d++){ int ans1 = dp[d][j-1] + sum(d+1, i)*sum(i+1, n); if(ans1>dp[i][j]){ dp[i][j] = ans1; p[i][j] = d; } } } } int mx = 0; for(int i=k; i<=n; i++){ if(dp[mx][k]<dp[i][k]) mx = i; } vi ans; int cur = mx; int cnt = k; while(cnt){ ans.pb(cur); cur = p[cur][cnt]; cnt--; } cout << dp[mx][k] << endl; reverse(all(ans)); for(int i:ans) cout << i << " "; } signed main(){ fast_io(); // srand(time(NULL)); // cout << fixed << setprecision(12); int q = 1; // cin >> q; while(q--) solve(); }
#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...