#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
#define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
//const long long MOD = 1e9 + 7;
const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
is >> p.first;
return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
for (auto &i: v) os << i << ' ';
return os;
}
int tc = 0;
const int N = 1e5 + 15;
const int K = 202;
int dp[N][K];
ll a[N], suf[N];
// dp[i][a] = dp[0..i-1][a-1]
inline void solve_test() {
int n, k;
cin >> n >> k;
//++k;
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = n;i > 0;i--) suf[i] = suf[i+1] + a[i];
//suf[0] = suf[1];
suf[0] = -INF;
for(auto& i : dp)for(auto& j : i) j = -INF / 4;
dp[1][0] =0;
for(int i = 1;i <= n;i++) {
for(int j = 0;j < min(i,k);j++) {
for(int c = 1;c < i;c++) {
//debug()<<imie(suf[i])imie(suf[c])imie(suf[c]-suf[i]);
chmax(dp[i][j+1],dp[c][j] + suf[i] * (suf[c] - suf[i]));
}
}
}
//for(int i = 0;i <= n;i++) {
//for(int j = 0;j <= k;j++) {
//debug()<<imie(i)imie(j)imie(dp[i][j]);
//}
//}
ll ans = 0;
for(int i = 0;i <= n;i++) chmax(ans, dp[i][k]);
cout << ans;
}
int32_t main()
{
//srand(chrono::steady_clock::now().time_since_epoch().count());
//freopen("convention2.in", "r", stdin);
//freopen("convention2.out", "w", stdout);
//cout << "Case #" << tc << ": " << ans << '\n';
//cout << fixed << setprecision(7);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--) {
++tc;
solve_test();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
