oj.uz

Submission #126830

# Submission time Handle Problem Language Result Execution time Memory
126830 2019-07-08T13:48:22 Z abacaba Kas (COCI17_kas) C++14
100 / 100
 114 ms 1144 KB 
#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9;
const int M = 1e5 + 15;
int n, x, summ, ans = inf;
int dp[2][M];

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 368 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 888 KB Output is correct
2 Correct 28 ms 504 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 676 KB Output is correct
2 Correct 55 ms 908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1144 KB Output is correct
2 Correct 114 ms 1144 KB Output is correct