oj.uz

Submission #289596

# Submission time Handle Problem Language Result Execution time Memory
289596 2020-09-02T18:48:43 Z FlashGamezzz Kas (COCI17_kas) C++14
90 / 100
 898 ms 524288 KB 
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>

using namespace std;

long dp[501][100001] = {};
long sum, notes[500];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> notes[i];
		sum += notes[i];
	}
	for (int i = 0; i <= n; i++){
		for (long j = 0; j < 100001; j++){
			dp[i][j] = 100001;
		}
	}
	dp[0][0] = 0;
	for (int i = 0; i < n; i++){
		for (long j = 0; j < 100001; j++){
			dp[i+1][j] = min(dp[i+1][j], dp[i][j]+notes[i]);
			dp[i+1][abs(j-notes[i])] = min(dp[i+1][abs(j-notes[i])], dp[i][j]);
			dp[i+1][j+notes[i]] = min(dp[i+1][j+notes[i]], dp[i][j]);
		}
	}
	cout << sum-(sum-dp[n][0])/2 << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8960 KB Output is correct
2 Correct 8 ms 9088 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8960 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10480 KB Output is correct
2 Correct 10 ms 11264 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11364 KB Output is correct
2 Correct 13 ms 11296 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 32 ms 32384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 36352 KB Output is correct
2 Correct 39 ms 40312 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 157688 KB Output is correct
2 Correct 183 ms 197112 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 235940 KB Output is correct
2 Correct 286 ms 314232 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 353396 KB Output is correct
2 Runtime error 898 ms 524288 KB Execution killed with signal 11