oj.uz

Submission #703027

# Submission time Handle Problem Language Result Execution time Memory
703027 2023-02-25T16:02:14 Z vjudge1 Kas (COCI17_kas) C++11
100 / 100
 176 ms 1868 KB 
#include <bits/stdc++.h>
using namespace std;

const int MxN = 100010;
int dp[2][2 * MxN + 1];

int main(){
	int q = 1;
	//scanf("%d", &q);
	while(q--){
		int n, sum = 0;
		scanf("%d", &n);
		memset(dp, -1, sizeof dp);
		dp[0][MxN] = 0;
		for(int i=1, x; i<=n; ++i){
			scanf("%d", &x);
			memcpy(dp[i & 1], dp[i & 1 ^ 1], sizeof dp[i & 1]);
			for(int sum=0; sum<=2*MxN; ++sum){
				if(dp[i & 1 ^ 1][sum] == -1){
					continue;
				}
				if(sum - x >= 0){
					dp[i & 1][sum - x] = max(dp[i & 1][sum - x], dp[i & 1 ^ 1][sum] + x);
				}
				if(sum + x <= 2 * MxN){
					dp[i & 1][sum + x] = max(dp[i & 1][sum + x], dp[i & 1 ^ 1][sum] + x);
				}
			}
			sum += x;
			//memcpy(dp[i & 1 ^ 1], dp[i & 1], sizeof dp[i & 1 ^ 1]);
			//memset(dp[i & 1 ^ 1], -1, sizeof dp[i & 1 ^ 1]);
		}
		printf("%d", sum - dp[n & 1][MxN] / 2);
	}
	return 0;
}

Compilation message

kas.cpp: In function 'int main()':
kas.cpp:17:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   17 |    memcpy(dp[i & 1], dp[i & 1 ^ 1], sizeof dp[i & 1]);
      |                         ~~^~~
kas.cpp:19:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   19 |     if(dp[i & 1 ^ 1][sum] == -1){
      |           ~~^~~
kas.cpp:23:56: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   23 |      dp[i & 1][sum - x] = max(dp[i & 1][sum - x], dp[i & 1 ^ 1][sum] + x);
      |                                                      ~~^~~
kas.cpp:26:56: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |      dp[i & 1][sum + x] = max(dp[i & 1][sum + x], dp[i & 1 ^ 1][sum] + x);
      |                                                      ~~^~~
kas.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
kas.cpp:16:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1748 KB Output is correct
2 Correct 13 ms 1868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1848 KB Output is correct
2 Correct 16 ms 1864 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1848 KB Output is correct
2 Correct 70 ms 1848 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1848 KB Output is correct
2 Correct 117 ms 1748 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 1844 KB Output is correct
2 Correct 170 ms 1840 KB Output is correct