Submission #703027

#	Time	Username	Problem	Language	Result	Execution time	Memory
703027		vjudge1	Kas (COCI17_kas)	C++11	100 / 100	176 ms	1868 KiB

kas

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10