#988926 (C++17) No.2783 4-33 Easy

提出ソース

結果

問題	No.2783 4-33 Easy
ユーザー	mayocorn
提出日時	2024-06-15 00:42:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	19 ms / 2,000 ms
コード長	6,219 bytes
コンパイル時間	4,822 ms
コンパイル使用メモリ	273,440 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-15 00:42:31
合計ジャッジ時間	6,860 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	3 ms 6,812 KB
testcase_02	AC	2 ms 6,812 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	13 ms 6,940 KB
testcase_05	AC	19 ms 6,944 KB
testcase_06	AC	19 ms 6,940 KB
testcase_07	AC	19 ms 6,940 KB
testcase_08	AC	18 ms 6,944 KB
testcase_09	AC	17 ms 6,940 KB
testcase_10	AC	17 ms 6,944 KB
testcase_11	AC	17 ms 6,940 KB
testcase_12	AC	19 ms 6,940 KB
testcase_13	AC	18 ms 6,940 KB
testcase_14	AC	18 ms 6,940 KB
testcase_15	AC	18 ms 6,940 KB
testcase_16	AC	18 ms 6,940 KB
testcase_17	AC	18 ms 6,940 KB
testcase_18	AC	19 ms 6,940 KB
testcase_19	AC	19 ms 6,944 KB
testcase_20	AC	19 ms 6,944 KB
testcase_21	AC	19 ms 6,940 KB
testcase_22	AC	18 ms 6,940 KB
testcase_23	AC	18 ms 6,940 KB
testcase_24	AC	18 ms 6,940 KB
testcase_25	AC	17 ms 6,944 KB
testcase_26	AC	18 ms 6,940 KB
testcase_27	AC	19 ms 6,944 KB
testcase_28	AC	17 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

//\///\/ TYPE //\///\/

using ll = long long;
using i128 = __int128_t;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned;
using pl = pair<ll, ll>;
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
template<class T> using vvv = vector<vv<T>>;
template<class T> using vvvv = vector<vvv<T>>;
template<class T> using vvvvv = vector<vvvv<T>>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define V vector
#define vl v<ll>
#define vp v<pl>
#define vm v<mint>

//\///\/ INOUT //\///\/
 
#define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);
ostream &operator<<(ostream &os, const i128 &v) {
    if(v == 0) { return (os << "0"); }
    i128 num = v;
    if(v < 0) { os << '-'; num = -num; }
    string s;
    for(; num > 0; num /= 10) { s.push_back((char)(num % 10) + '0'); }
    reverse(s.begin(), s.end());
    return (os << s);
}
void Yes(bool b=1) { cout << ( b == 1 ? "Yes" : "No" ) << "\n"; }
void YES(bool b=1) { cout << ( b == 1 ? "YES" : "NO" ) << "\n"; }
void No(bool b=1) { cout << ( b == 1 ? "No" : "Yes" ) << "\n"; }
void NO(bool b=1) { cout << ( b == 1 ? "NO" : "YES" ) << "\n"; }
void CIN() {}
template <typename T, class... U> void CIN(T &t, U &...u) { cin >> t; CIN(u...); }
void COUT() { cout << "\n"; }
template <typename T, class... U, char sep = ' '> void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); }
#define dump(x) cerr << #x << ":"<< x << "\n";
#define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n";
 
//\///\/ MACRO //\///\/

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define rep(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define repr(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
// bitの部分集合の列挙
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define bp __builtin_popcountll
#define ALL(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
template <typename T> T POP(queue<T> &que) { T a = que.front(); que.pop(); return a; }
template <typename T> T POP(deque<T> &que) { T a = que.front(); que.pop_front(); return a; }
template <typename T> T POP(pq<T> &que) { T a = que.top(); que.pop(); return a; }
template <typename T> T POP(pqg<T> &que) { T a = que.top(); que.pop(); return a; }
// R, D, L, U, RU, RD, LD, LU
ll xd[]={0, 1, 0, -1, 1, 1, -1, -1};
ll yd[]={1, 0, -1, 0, 1, -1, -1, 1};

//\///\/ FUNCTION //\///\/

// a / b の床関数（負もOK）
template <typename T> T FLOOR(T a, T b) { return a / b - (a % b && (a ^ b) < 0); }
// a / b の天井関数（負もOK）
template <typename T> T CEIL(T a, T b) { return FLOOR(a + b - 1, b); }
// (divisor - mod) % divisor
// (3, 5) -> (2)
template <typename T> T SUBMOD(T x, T y) { return (y - x % y) % y; }
template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sm = 0;
  for (auto &&a: A) sm += a;
  return sm;
}
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
// lower_boundのindexを取得
#define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x)))
// upper_boundのindexを取得
#define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x)))
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
// topbit (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int tb(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// lowbit (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lb(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
// bitlength (0, 1, 2, 3, 4) -> (0, 1, 2, 2, 3)
int bl(ll x) { return tb(x) + 1; } 
bool OUT(ll x, ll y, ll h, ll w) { return x < 0 || y < 0 || x >= h || y >= w; }
// 「?」 は -1
vl stovl(const string &S, char first_char='0') {
  vl A(S.size());
  rep(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}
// 累積和
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off=1) {
  int N = A.size();
  vector<T> B(N + 1);
  rep(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}
// 二分探索
template <typename F>
ll binary_search(F check, ll ok, ll ng) {
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}
// 二分探索（実数）
template <typename F>
ld binary_search_real(F check, ld ok, ld ng, int iter = 100) {
  rep(iter) {
    double x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return (ok + ng) / 2;
}

//\///\/ CONSTANT //\///\/

long double PI = 3.14159265358979;
#define INF32 2147483647
#define INF64 9223372036854775807
#define INF 922337203685477580
using mint = modint998244353;
// using mint = modint1000000007;

//\///\///\///\///\///\///\///\///\///\///\///\///\///\///\///\///\///\///\///\/

void solve()
{
  ll n;
  cin >> n;
  
  vl a(n), b(n), c(n);
  rep(i, n) cin >> a[i];
  rep(i, n){
    string s;
    cin >> s;
    if(s.back() == 'X'){
      c[i] = 1;
      s = s.substr(0, sz(s) - 1);
      if(s == "") s = "0";
    }
    b[i] = stoll(s);
  }
  
  V dp(5, V(34, V(10, mint(0))));
  dp[0][0][0] = 1;
  rep(i, n){
    if(c[i]) continue;
    V tmp = dp;
    rep(u, 8)rep(x, 5)rep(y, 34){
      ll nx = x + a[i];
      ll ny = y + b[i];
      if(nx <= 4 && ny <= 33) dp[nx][ny][u + 1] += tmp[x][y][u];
    }
  }
  
  mint ans = 0;
  rep(i, n){
    if(!(c[i] == 1 && b[i] == 0)) continue;
    ll px = 4 - a[i];
    ans += dp[px][33][8];
  }
  cout << ans.val() << "\n";
} 

int main()
{
  NYAN
  solve();
  return 0;
}

yukicoder

結果

テストケース

ソースコード