oj.uz

Submission #1019826

# Submission time Handle Problem Language Result Execution time Memory
1019826 2024-07-11T09:18:24 Z ZeroCool Kas (COCI17_kas) C++14
100 / 100
 159 ms 3588 KB 
#include <bits/stdc++.h>
using namespace std;
  
#define int long long
  
#define ll long long
#define ar array
#define ld long double
  
const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int K = 700;
const int INF = 1e17;
const int LOG = 34;
const int X = 100005;


int dp[2][2 * X];

signed main(){ios::sync_with_stdio(false);cin.tie(0);   
	memset(dp[0], -1, sizeof dp[0]);
	int n;
	cin>>n;
	dp[0][X] = 0;
	int k = 0;
	int sum = 0;
	while(n--){
		
		int x;
		cin>>x;
		sum += x;
		for(int i = 0;i < 2 * X;i++)dp[k ^ 1][i] = dp[k][i];
		for(int i = 0;i < 2 * X;i++){
			if(dp[k][i] == -1)continue;
			if(i - x >= 0)dp[k ^ 1][i-x] = max(dp[k ^ 1][i-x], dp[k][i] + x);
			if(i + x < 2 * X)dp[k ^ 1][i+x] = max(dp[k ^ 1][i+x], dp[k][i] + x);
		}
		k ^= 1;
	}
	cout<<sum - dp[k][X] / 2;
}

// Te molam da raboti!

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3416 KB Output is correct
2 Correct 6 ms 3420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 5 ms 3420 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3420 KB Output is correct
2 Correct 6 ms 3408 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3420 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3420 KB Output is correct
2 Correct 15 ms 3588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3416 KB Output is correct
2 Correct 71 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3420 KB Output is correct
2 Correct 114 ms 3568 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 3560 KB Output is correct
2 Correct 159 ms 3420 KB Output is correct