제출 #855544

#제출 시각아이디문제언어결과실행 시간메모리
855544Nuraly_Serikbay수열 (APIO14_sequence)C++17
50 / 100
2085 ms41048 KiB
//çalışan kazanır// #include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back #define S second #define F first #define all(x) x.begin(),x.end() #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}} const int N = 2e5 + 1; const int INF = 1e18 + 1; const int MOD = 998244353ll; const int MODD = 1070234587ll; const double eps = 0.0001; //const int p = 87; int n, dp[10005][205], a[N], pref[N], suf[N]; int k; void solution () { cin >> n >> k; for (int i = 1; i <= n; ++ i) cin >> a[i]; for (int i = 1; i <= n; ++ i) pref[i] = a[i] + pref[i - 1]; for (int i = n; i >= 1; -- i) suf[i] = suf[i + 1] + a[i]; for (int t = 1; t <= k; ++ t) { for (int i = 1; i <= n; ++ i) dp[i][t] = -INF; } for (int i = 1; i < n; ++ i) dp[i][1] = pref[i] * suf[i + 1]; for (int t = 2; t <= k; ++ t) { for (int i = 1; i < n; ++ i) { for (int j = 1; j < i; ++ j) { dp[i][t] = max (dp[i][t], dp[j][t - 1] + (pref[i] - pref[j]) * suf[i + 1]); } } } int res = 0, bg = 0; for (int i = 1; i <= n; ++ i) { res = max (res, dp[i][k]); if (dp[i][k] == res) bg = i; } cout << res << '\n'; vector <int> ans; ans.pb (bg); for (int t = k - 1; t >= 1; -- t) { for (int i = 1; i < bg; ++ i) { if (dp[i][t] + (pref[bg] - pref[i]) * suf[bg + 1] == res) { bg = i; ans.pb (i); res = dp[i][t]; break; } } } reverse (all (ans)); for (auto i: ans) cout << i << ' '; cout << '\n'; return; } signed main() { YOSIK(); // srand (time(0)); // freopen ("E.in", "r", stdin); // freopen ("E.out", "w", stdout); int TT = 1;// cin >> TT; for (int i = 1; i <= TT; ++ i) { // cout << "Case " << i << ": "; solution (); } 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...