結果
問題 |
No.297 カードの数式
|
ユーザー |
|
提出日時 | 2016-07-20 22:09:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 1,000 ms |
コード長 | 2,173 bytes |
コンパイル時間 | 1,690 ms |
コンパイル使用メモリ | 170,472 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-12-26 02:32:02 |
合計ジャッジ時間 | 2,904 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; int N; string input; const ll INF = LLONG_MAX; ll maxi[1 << 15][16][2]; ll mini[1 << 15][16][2]; void solve(){ vll pow10(18, 1); rep(i, 17)pow10[i + 1] = pow10[i] * 10; rep(i, 1 << N)rep(j, N + 1)rep(k, 2){ maxi[i][j][k] = -INF; mini[i][j][k] = INF; } maxi[0][0][0] = mini[0][0][0] = 0; const int fin = (1 << N) - 1; auto update = [&](int i, int j, int k, ll ma, ll mi){ smax(maxi[i][j][k], ma); smin(mini[i][j][k], mi); }; rep(mask, (1 << N) - 1)rep(curDigit, N)rep(oper, 2)if(maxi[mask][curDigit][oper] != -INF){ ll ma = maxi[mask][curDigit][oper]; ll mi = mini[mask][curDigit][oper]; rep(i, N)if(!(mask >> i & 1)){ char chara = input[i]; int nextMask = 1 << i | mask; if(chara == '+' || chara == '-'){ if(curDigit < 1 || nextMask == fin)continue; update(nextMask, 0, chara == '+' ? 0 : 1, ma, mi); } else{ ll mul = (oper == 0 ? 1 : -1) * pow10[curDigit]; ll nextMa = ma + mul*(chara - '0'); ll nextMi = mi + mul*(chara - '0'); update(nextMask, curDigit + 1, oper, nextMa, nextMi); } } } ll ansMa = -INF, ansMi = INF; rep(curDigit, N + 1)rep(oper, 2){ smax(ansMa, maxi[fin][curDigit][oper]); smin(ansMi, mini[fin][curDigit][oper]); } cout << ansMa << ' ' << ansMi << endl; } int main(){ while(cin >> N){ input.clear(); char chara; rep(i, N){ cin >> chara; input += chara; } solve(); } }