Submission #1159021

#TimeUsernameProblemLanguageResultExecution timeMemory
1159021AlfraganusSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define str string #define endl '\n' #define fs first #define ss second #define all(a) a.begin(), a.end() #define print(a) for(auto x : a) cout << x << ' '; cout << endl; #define printmp(a) for(auto x : a) cout << x[0] << ' ' << x[1] << endl; void solve(){ int n, k; cin >> n >> k; vector<int> a(n); for(int i = 0; i < n; i ++) cin >> a[i]; vector<int> pre(n + 1); for(int i = 0; i < n; i ++) pre[i + 1] = pre[i] + a[i]; int ans = 0; set<array<int, 2>> st; st.insert({0, n - 1}); vector<int> res; for(int i = 0; i < k; i ++){ int mx = 0, lr = 0, mr = 0, rr = 0; for(auto x : st){ for(int y = x[0]; y <= x[1]; y ++){ int a1 = pre[y + 1] - pre[x[0]], a2 = pre[x[1] + 1] - pre[y + 1]; if(a1 * a2 > mx){ mx = a1 * a2; lr = x[0]; mr = y; rr = x[1]; } } } ans += mx; res.push_back(mr + 1); st.erase({lr, rr}); st.insert({lr, mr}); st.insert({mr + 1, rr}); } cout << ans << endl; print(res) } signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while(t --){ solve(); cout << endl; } }
#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...