oj.uz

답안 #126828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126828 2019-07-08T13:43:50 Z abacaba Kas (COCI17_kas) C++14
100 / 100
 305 ms 87336 KB 
#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9;
const int M = 1e5 + 15;
const int N = 5e2 + 15;
int n, a[N], summ, ans = inf;
int dp[N][M];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		summ += a[i];
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = M - 1; j >= 0; --j) {
			if(!j || dp[i-1][j]) {
				dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i-1][j] + a[i]);
				dp[i][abs(j - a[i])] = max(dp[i][abs(j - a[i])], dp[i-1][j] + a[i]);
				dp[i][j] = max(dp[i][j], dp[i-1][j]);
			}
		}
	}
	cout << summ - dp[n][0] + dp[n][0] / 2;
    return 0;
}

Compilation message

kas.cpp: In function 'int main()':
kas.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
kas.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 4 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Output is correct
2 Correct 11 ms 760 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 632 KB Output is correct
2 Correct 13 ms 760 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 16760 KB Output is correct
2 Correct 65 ms 6008 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 18708 KB Output is correct
2 Correct 135 ms 23468 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 41144 KB Output is correct
2 Correct 305 ms 87336 KB Output is correct