Submission #1109089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109089		ind1v	Kas (COCI17_kas)	C++11	100 / 100	196 ms	2120 KiB

kas

#include <bits/stdc++.h>

using namespace std;

const int N = 5e2 + 5;
const int A = 1e5 + 5;

int n;
int c[N];
int f[2][2 * A];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  memset(f[0], 0x3f, sizeof(f[0]));
  f[0][A] = 0;
  for (int i = 1; i <= n; i++) {
    memset(f[i & 1], 0x3f, sizeof(f[i & 1]));
    for (int j = 0; j < 2 * A; j++) {
      f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j] + c[i]);
      if (j >= c[i]) {
        f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j - c[i]]);
      }
      if (j + c[i] < 2 * A) {
        f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j + c[i]]);
      }
    }
  }
  long long sum = accumulate(c + 1, c + n + 1, 0LL);
  cout << (sum - f[n & 1][A]) / 2 + f[n & 1][A] << '\n';
  return 0;
}

Compilation message (stderr)

kas.cpp: In function 'int main()':
kas.cpp:24:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   24 |       f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j] + c[i]);
      |                                        ~~^~~
kas.cpp:26:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |         f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j - c[i]]);
      |                                          ~~^~~
kas.cpp:29:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   29 |         f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j + c[i]]);
      |                                          ~~^~~

• 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