oj.uz

Submission #740911

# Submission time Handle Problem Language Result Execution time Memory
740911 2023-05-13T08:55:36 Z dsyz Kas (COCI17_kas) C++17
100 / 100
 406 ms 391724 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8148 KB Output is correct
2 Correct 8 ms 8140 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8132 KB Output is correct
2 Correct 8 ms 8156 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 9 ms 8916 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9648 KB Output is correct
2 Correct 12 ms 10500 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10500 KB Output is correct
2 Correct 12 ms 10504 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 27720 KB Output is correct
2 Correct 33 ms 31572 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35540 KB Output is correct
2 Correct 38 ms 39456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 156832 KB Output is correct
2 Correct 191 ms 195888 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 235148 KB Output is correct
2 Correct 320 ms 313368 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 352552 KB Output is correct
2 Correct 406 ms 391724 KB Output is correct