求组hack数据
查看原帖
求组hack数据
156353
GoldenFishX楼主2021/7/15 15:10
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const long long Mod = 998244353;

long long a[MAXN], b[MAXN], sum1, sum2, ans = -114514;
int aa[MAXN], bb[MAXN];
bool visa[MAXN], visb[MAXN];
int cntaa, cntbb;
long long n, x;
int cnta, cntb;

void dfs(int x, long long sum) {
  if (x == n) {
    ans = max(ans, sum);
    return;
  }
  for (int i = 0; i < cntaa; i++) {
    if (!visa[i]) {
      visa[i] = 1;
      dfs(x + 1, sum + aa[i]);
      visa[i] = 0;
    }
  }
  for (int i = 0; i < cntbb; i++) {
    if (!visb[i]) {
      visb[i] = 1;
      dfs(x + 1, sum * bb[i]);
      visb[i] = 0;
    }
  }
}

int main() {
  char c;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> c >> x;
    if (c == '+') {
      if (x > 0) {
        sum1 = (sum1 + x) % Mod;
      } else if (x < 0) {
        sum2 = (sum2 + x) % Mod;
      }
      aa[cntaa++] = x;
    } else {
      if (x > 0) {
        a[cnta++] = x;
      } else if (x < 0) {
        b[cntb++] = -x;
      }
      bb[cntbb++] = x;
    }
  }
  if (n <= 9) {
    dfs(0, 0);
    cout << (ans + Mod) % Mod;
  } else if (cntb == 0 && sum2 == 0) {
    ans = sum1;
    for (int i = 0; i < cnta; i++) {
      ans = (ans * a[i]) % Mod;
    }
    cout << ans;
  } else if (cntb == 0) {
    ans = sum1;
    if (ans > 0) {
      for (int i = 0; i < cnta; i++) {
        ans = (ans * a[i]) % Mod;
      }
    }
    ans += sum2;
    cout << (ans + Mod) % Mod;
  } else if (sum2 == 0) {
    ans = sum1;
    for (int i = 0; i < cnta; i++) {
      ans = (ans * a[i]) % Mod;
    }
    sort(b, b + cntb);
    for (int i = cntb % 2; i < cntb; i++) {
      ans = (ans * b[i]) % Mod;
    }
    cout << ans;
  } else {
    sort(b, b + cntb);
    if (cntb % 2) {
      ans = -sum2 * b[0] % Mod;
      ans += sum1;
      for (int i = 1; i < cntb; i++) {
        ans = (ans * b[i]) % Mod;
      }
      for (int i = 0; i < cnta; i++) {
        ans = (ans * a[i]) % Mod;
      }
    } else {
      ans = (sum2 + sum1 * b[0] + Mod) % Mod;
      for (int i = 1; i < cntb; i++) {
        ans = (ans * b[i]) % Mod;
      }
      for (int i = 0; i < cnta; i++) {
        ans = (ans * a[i]) % Mod;
      }
    }
    cout << ans;
  }
}
2021/7/15 15:10
加载中...