結果

問題 No.10 ＋か×か
ユーザー 久我山菜々久我山菜々
提出日時 2018-09-30 21:39:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,854 bytes
コンパイル時間 1,020 ms
コンパイル使用メモリ 103,040 KB
実行使用メモリ 10,272 KB
最終ジャッジ日時 2024-04-20 13:47:36
合計ジャッジ時間 7,475 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   11 | int count(auto const& map, auto const& as, int depth) {
      |           ^~~~
main.cpp:11:28: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   11 | int count(auto const& map, auto const& as, int depth) {
      |                            ^~~~
main.cpp:23:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   23 | void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
      |            ^~~~
main.cpp:23:23: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   23 | void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
      |                       ^~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<numeric>

static int const INF{100000000};

int count(auto const& map, auto const& as, int depth) {
  int ans{as[0]};
  for(int i{}; i < depth; ++i) {
    if(map[i] == 1) {
      ans += as[i + 1];
    } else {
      ans *= as[i + 1];
    }
  }
  return ans;
}

void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
  if(depth == max_depth) {
    if(total == current) return;
    for(int i{max_depth - 1}; i >= 0; --i) {
      if(map[i] == 1) {
        solve(map, as, max_depth, i, total, count(map, as, i));
        return;
      }
      map[i] = 0;
    }
    throw "never come";
  }
  if(map[depth] == 0) {
    map[depth] = 1;
    if(total >= current + as[depth + 1]) {
      solve(map, as, max_depth, depth + 1, total, current + as[depth + 1]);
    } else {
      solve(map, as, max_depth, depth, total, current);
    }
  } else if(map[depth] == 1) {
    map[depth] = 2;
    if(total >= current * as[depth + 1]) {
      solve(map, as, max_depth, depth + 1, total, current * as[depth + 1]);
    } else {
      solve(map, as, max_depth, depth, total, current);
    }
  } else {
    map[depth] = 0;
    if(map[depth - 1] == 1) {
      solve(map, as, max_depth, depth - 1, total, current - as[depth]);
    } else if(map[depth - 2] == 2)  {
      solve(map, as, max_depth, depth - 1, total, current / as[depth]);
    }
  }
}

int main(int, char**) {
  int n;
  std::cin >> n;
  int total;
  std::cin >> total;
  std::vector<int> as(n);
  for(int i{}; i < n; ++i) {
    std::cin >> as[i];
  }

  std::vector<int> map(n - 1, 0);
  // 0: unknown, 1: plus, 2: mul

  solve(map, as, n - 1, 0, total, as[0]);

  for(auto e: map) {
    std::cout << (e == 1 ? '+' : '*');
  }
  std::cout << std::endl;

  return 0;
}
0