제출 #855489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855489		vjudge1	수열 (APIO14_sequence)	C++17	0 / 100	571 ms	12892 KiB

sequence

#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define Youarestupid ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) x.begin() , x.end()
#define	pofik continue
#define int long long
#define pb push_back
#define ins insert
#define sz size()
#define F first
#define S second
const int N = 1500 + 77 , inf = 1e18 + 77 , MOD = 1e9 + 7;
const long double eps = 1e-11;
using namespace std;
int T = 1 , sum;
int binpow(int a , int b){
    if (!b) return 1;
    if (b % 2){
        return (a * binpow(a , b - 1)) % MOD;
    }
    else{
        int val = binpow(a , b / 2);
        return (val * val) % MOD;
    }
}

int dp[N][N];

void solve(){
	int n , k;
	cin >> n >> k;
	int a[n + 5];
	int pref[n + 5] , suff[n + 5];
	pref[0] = 0 , suff[n + 1] = 0;
	for(int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i - 1] + a[i]; }
	for(int i = n; i >= 1; i--){ suff[i] = suff[i + 1] + a[i]; dp[i][1] = pref[i] * suff[i + 1]; }
	for(int i = 1; i <= n; i++){
		for(int l = 2; l <= n; l++){
			dp[i][l] = inf;
			for(int j = 1; j < i; j++){
				dp[i][l] = max(dp[j][l - 1] + (pref[i] - pref[j]) * suff[i + 1] , dp[i][j]);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		ans = max(ans , dp[i][k]);
	}
	cout << ans;
}

signed main(){
    Youarestupid
//	cin >> T;
    while(T--){
    	solve();
    }
}
/*
  ___      __                      _
 |   \    | |          _____      | |  _
 | |\ \   | |  __  __ |  __ \     | | (_)
 | | \ \  | | | |  | || |  \_\__ _| |  _
 | |  \ \ | | | |  | || |    / _` | | | |
 | |   \ \| | | |__| || |   / (_| | | | |
 |_|    \___| |______||_|    \_,__|_| |_|

*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29