제출 #697615

#제출 시각아이디문제언어결과실행 시간메모리
697615tamthegod수열 (APIO14_sequence)C++17
50 / 100
153 ms3796 KiB
// Make the best become better // No room for laziness #include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e3 + 5; const int maxK = 205; const int mod = 1e9 + 7; const ll oo = 1e18; int n, k, a[maxN], sum[maxN]; int f[maxN][maxK]; void ReadInput() { cin >> n >> k; for(int i=1; i<=n; i++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; } } int get(int l, int r) { if(l > r) return 0; return sum[r] - sum[l - 1]; } void Solve() { //cout << get(1, n);return memset(f, -3, sizeof f); f[0][0] = 0; for(int i=1; i<n; i++) { for(int j=1; j<=k; j++) { for(int t=i; t>=1; t--) { f[i][j] = max(f[i][j], f[t - 1][j - 1] + get(t, i) * get(i + 1, n)); } } } int res = -1; int id = 0; for(int i=k; i<n; i++) { if(res < f[i][k]) { res = f[i][k]; id = i; } } cout << res << '\n'; int tmp = res; vector<int> trace; trace.pb(id); for(int i=id-1; i>=1; i--) { if(f[i][k - 1] + get(i + 1, id) * get(id + 1, n) == res) { trace.pb(i); id = i; res = f[i][k - 1]; k--; } } reverse(trace.begin(), trace.end()); for(int v : trace) cout << v << " "; int sum = 0; int last = 0; for(int v : trace) { sum += get(last + 1, v) * get(v + 1, n); last = v; } assert(sum == tmp); } int32_t main() { // freopen("sol.inp", "r", stdin); // freopen("sol.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); 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...