結果

問題 No.10 ＋か×か
コンテスト
ユーザー char134217728
提出日時 2017-08-19 04:48:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,165 ms / 5,000 ms
コード長 1,007 bytes
コンパイル時間 1,487 ms
コンパイル使用メモリ 166,764 KB
実行使用メモリ 15,744 KB
最終ジャッジ日時 2024-12-14 15:40:48
合計ジャッジ時間 4,796 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:16:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef set<int> si;
const int inf = 1e9;
const int mod = 1e9+7;

map<int, ll> mn, mt;
int n, t;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> t;
  int w;
  cin >> w;
  mt[w] = 0;
  FOR(i, 0, n-1){
    int w;
    cin >> w;
    for(map<int, ll>::iterator itr = mt.begin(); itr != mt.end(); itr++){
      int a = itr->first;
      ll  b = itr->second;
      int li[2];
      li[0]= a + w;
      li[1]= a * w;
      FOR(j, 0, 2){
        if(li[j] > t)continue;
        if(mn.find(li[j]) != mn.end()){
          mn[li[j]] = min(mn[li[j]], b * 2 + j);
        }else{
          mn[li[j]] = b * 2 + j;
        }
      }
    }
    mt.clear();
    swap(mt, mn);
  }
  ll an = mt[t];
  FORR(i, n-2, 0){
    cout << (an >> i & 1 ? "*" : "+");
  }
  cout << endl;
}
0