結果
問題 | No.297 カードの数式 |
ユーザー |
![]() |
提出日時 | 2015-11-06 23:00:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 636 ms / 1,000 ms |
コード長 | 3,291 bytes |
コンパイル時間 | 917 ms |
コンパイル使用メモリ | 105,412 KB |
実行使用メモリ | 89,164 KB |
最終ジャッジ日時 | 2024-09-13 13:29:15 |
合計ジャッジ時間 | 3,686 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:41:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 41 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 45 | scanf("%s", buf); | ~~~~~^~~~~~~~~~~
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>#include<unordered_set>#include<unordered_map>using namespace std;vector<int> k;vector<int> val;char buf[3];vector<int> V[1 << 15]; //valuesint pl;int mi;long long int dp[1 << 15][16][16];long long int value[1 << 15];long long int value2[1 << 15];int main() {int n;scanf("%d", &n);int summ = 0;for (int i = 0;i < n;i++) {char s;scanf("%s", buf);s = buf[0];if (s == '+') {k.push_back(1);pl++;}if (s == '-') {k.push_back(-1);mi++;}if (isdigit(s)) {val.push_back(s - '0');summ += s - '0';}}sort(val.begin(), val.end());reverse(val.begin(), val.end());for (int i = 1;i < (1 << val.size());i++) {long long int vv = 0;for (int j = 0;j < val.size();j++) {if ((i >> j) & 1) {vv *= 10LL;vv += val[j];}}value[i] = vv;}for (int i = 1;i < (1 << val.size());i++) {long long int vv = 0;for (int j = val.size()-1;j >=0;j--) {if ((i >> j) & 1) {vv *= 10LL;vv += val[j];}}value2[i] = vv;}for (int ii = 0;ii < (1 << val.size());ii++) {for (int i = 1;i < (1 << val.size());i++) {if ((ii&i)) {}else {V[ii].push_back(i);}}}for (int i = 0;i < (1 << 15);i++) {for (int j = 0;j < 16;j++) {for (int k = 0;k < 16;k++) {dp[i][j][k] = INT_MIN;}}}for (int i = 1;i < (1 << val.size());i++) {dp[i][0][0] = value[i];}for (int i = 0;i < (1 << val.size())-1;i++) {for (int j = 0;j <=pl;j++) {for (int k = 0;k <= mi;k++) {if (dp[i][j][k] == INT_MIN) {continue;}if (j == pl && k == mi) {continue;}for (int kk = 0;kk < V[i].size();kk++) {//plusif (j != pl) {dp[i | V[i][kk]][j + 1][k] = max(dp[i | V[i][kk]][j + 1][k], dp[i][j][k] + value[V[i][kk]]);}if (k != mi) {dp[i | V[i][kk]][j][k+1] = max(dp[i | V[i][kk]][j][k+1], dp[i][j][k] - value2[V[i][kk]]);}}}}}long long int ans = dp[(1 << val.size()) - 1][pl][mi];for (int i = 0;i < (1 << 15);i++) {for (int j = 0;j < 16;j++) {for (int k = 0;k < 16;k++) {dp[i][j][k] = INT_MAX;}}}for (int i = 1;i < (1 << val.size());i++) {dp[i][0][0] = value2[i];}for (int i = 0;i < (1 << val.size()) - 1;i++) {for (int j = 0;j <= pl;j++) {for (int k = 0;k <= mi;k++) {if (dp[i][j][k] == INT_MAX) {continue;}if (j == pl && k == mi) {continue;}for (int kk = 0;kk < V[i].size();kk++) {//plusif (j != pl) {dp[i | V[i][kk]][j + 1][k] = min(dp[i | V[i][kk]][j + 1][k], dp[i][j][k] + value2[V[i][kk]]);}if (k != mi) {dp[i | V[i][kk]][j][k + 1] = min(dp[i | V[i][kk]][j][k + 1], dp[i][j][k] - value[V[i][kk]]);}}}}}long long int ans2 = dp[(1 << val.size()) - 1][pl][mi];printf("%lld %lld\n", ans, ans2);return 0;}