Submission #740911

#	Time	Username	Problem	Language	Result	Execution time	Memory
740911		dsyz	Kas (COCI17_kas)	C++17	100 / 100	406 ms	391724 KiB

kas

#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (200005)
ll dp[505][MAXN];
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll N;
    cin>>N;
    ll arr[N];
    ll total = 0;
    for(ll i = 0;i < N;i++){
		cin>>arr[i];
		total += arr[i];
	}
	for(ll i = 0;i < N;i++){
	    for(ll j = 0;j < MAXN;j++){
	        dp[i][j] = -1e9;
	    }
	}
	dp[0][100001] = 0;
	dp[0][100001 + arr[0]] = arr[0];
	dp[0][100001 - arr[0]] = 0;
	for(ll i = 1;i < N;i++){
		for(ll j = 0;j < MAXN;j++){
			dp[i][j] = dp[i - 1][j];
			if(j + arr[i] < MAXN) dp[i][j] = max(dp[i][j],dp[i - 1][j + arr[i]]);
			if(j - arr[i] >= 0) dp[i][j] = max(dp[i][j],dp[i - 1][j - arr[i]] + arr[i]);
		}
	}
	cout<<dp[N - 1][100001] + (total - 2 * dp[N - 1][100001])<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10