Submission #19539236


Source Code Expand

Copy
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;

using namespace std;

#ifdef _DEBUG
#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#else
#define DUMP(x)
#endif
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define EREP(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i)
#define rep(i, n) REP(i, 0, n)
#define erep(i, n) EREP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)
#define ALL(r) begin(r), end(r)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    return (os << "(" << p.first << ", " << p.second << ")");
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &m) {
    bool first = true;
    os << "{";
    for (const auto &e : m) {
        if (!first)
            os << ", ";
        os << "{" << e.first << ": " << e.second << "}";
        first = false;
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
    os << "{";
    bool first = true;
    for (const auto &e : s) {
        if (!first)
            os << ", ";
        os << e;
        first = false;
    }
    os << "}";
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
    os << "{";
    bool first = true;
    for (const auto &e : s) {
        if (!first)
            os << ", ";
        os << e;
        first = false;
    }
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y) {
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
struct in {
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T() {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>() {
        assert(n != 0);
        vector<T> ret(n);
        for (T &x : ret) {
            T tmp = in();
            x = tmp;
        }
        return ret;
    }
    template <typename T, typename U>
    operator pair<T, U>() {
        pair<T, U> ret;
        ret.first = in();
        ret.second = in();
        return ret;
    }
};

namespace fiore::impl {
template <typename T>
inline void out_impl(const T &x, char end_char) {
    std::cout << x << end_char;
}
template <typename T>
inline void out_impl(const vector<T> &x, char end_char) {
    bool first = true;
    for (const auto &e : x) {
        if (!first)
            std::cout << ' ';
        std::cout << e;
        first = false;
    }
    std::cout << end_char;
}
} // namespace fiore::impl
template <typename T>
inline void out(const T &x) {
    fiore::impl::out_impl(x, '\n');
};
template <typename T, typename U, typename... Args>
inline void out(const T &x, const U &y, const Args &... args) {
    fiore::impl::out_impl(x, ' ');
    out(y, args...);
}

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using setint = set<int32_t>;
using qint = queue<int32_t>;
using qpint = queue<pint>;
using ld = long double;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

constexpr int mod = 1'000'000'007;
// constexpr int mod = 998'244'353;
class mint {
private:
    std::int64_t m_x;

public:
    mint(const std::int64_t m_x = 0) : m_x((m_x % mod + mod) % mod) {}
    std::int64_t get() const { return m_x; }
    mint operator-() const { return mint(-m_x); }
    bool operator==(const mint a) const { return m_x == a.get(); }
    bool operator!=(const mint a) const { return !(*this == a); }
    mint &operator+=(const mint a) {
        if ((m_x += a.m_x) >= mod)
            m_x -= mod;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((m_x += mod - a.m_x) >= mod)
            m_x -= mod;
        return *this;
    }
    mint &operator*=(const mint a) {
        (m_x *= a.m_x) %= mod;
        return *this;
    }
    mint &operator++() { return *this += 1; }
    mint operator++(int) {
        mint tmp = *this;
        ++*this;
        return tmp;
    }
    mint operator--() { return *this -= 1; }
    mint operator--(int) {
        mint tmp = *this;
        --*this;
        return tmp;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(const std::int64_t t) const {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint &operator/=(const mint a) { return (*this) *= a.inv(); }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};
istream &operator>>(istream &is, mint &a) {
    ll x;
    is >> x;
    a = x;
    return is;
}
ostream &operator<<(ostream &os, const mint &a) {
    os << a.get();
    return os;
}

mint dp[1005];

void Main() {
    int n = in();
    string s = in();
    vstr t = in(n);
    arrayFill(dp, 0);
    int len = size(s);
    dp[0] = 1;
    rep(i, len) {
        rep(j, n) {
            if (i + size(t[j]) <= len) {
                if (s.substr(i, size(t[j])) == t[j]) {
                    dp[i + size(t[j])] += dp[i];
                }
            }
        }
    }
    out(dp[len]);
}

signed main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

Submission Info

Submission Time
Task B - エターナルスタティックファイナル
User fiore
Language C++ (GCC 9.2.1)
Score 60
Code Size 6984 Byte
Status AC
Exec Time 11 ms
Memory 3612 KB

Compile Error

./Main.cpp: In function ‘void Main()’:
./Main.cpp:284:32: warning: comparison of integer expressions of different signedness: ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  284 |             if (i + size(t[j]) <= len) {
      |                 ~~~~~~~~~~~~~~~^~~~~~

Judge Result

Set Name All
Score / Max Score 60 / 60
Status
AC × 108
Set Name Test Cases
All 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_sample03.txt, 00_sample04.txt, 01_random00.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt, 01_random08.txt, 01_random09.txt, 01_random10.txt, 01_random11.txt, 01_random12.txt, 01_random13.txt, 01_random14.txt, 01_random15.txt, 01_random16.txt, 01_random17.txt, 01_random18.txt, 01_random19.txt, 01_random20.txt, 01_random21.txt, 01_random22.txt, 01_random23.txt, 01_random24.txt, 01_random25.txt, 01_random26.txt, 01_random27.txt, 01_random28.txt, 01_random29.txt, 01_random30.txt, 01_random31.txt, 01_random32.txt, 01_random33.txt, 01_random34.txt, 01_random35.txt, 01_random36.txt, 01_random37.txt, 01_random38.txt, 01_random39.txt, 01_random40.txt, 01_random41.txt, 01_random42.txt, 01_random43.txt, 01_random44.txt, 01_random45.txt, 01_random46.txt, 01_random47.txt, 01_random48.txt, 01_random49.txt, 01_random50.txt, 01_random51.txt, 01_random52.txt, 01_random53.txt, 01_random54.txt, 01_random55.txt, 01_random56.txt, 01_random57.txt, 01_random58.txt, 01_random59.txt, 01_random61.txt, 01_random62.txt, 01_random63.txt, 01_random64.txt, 01_random65.txt, 01_random66.txt, 01_random67.txt, 01_random68.txt, 01_random69.txt, 01_random70.txt, 01_random71.txt, 01_random72.txt, 01_random73.txt, 01_random74.txt, 01_random75.txt, 01_random76.txt, 01_random77.txt, 01_random78.txt, 01_random79.txt, 01_random80.txt, 01_random81.txt, 01_random82.txt, 01_random83.txt, 01_random84.txt, 01_random85.txt, 01_random86.txt, 01_random87.txt, 01_random88.txt, 01_random89.txt, 01_random90.txt, 01_random91.txt, 01_random92.txt, 01_random93.txt, 01_random94.txt, 01_random95.txt, 01_random96.txt, 01_random97.txt, 01_random98.txt, 01_random99.txt, 02_manual00.txt, 02_manual01.txt, 02_manual02.txt, 02_manual03.txt
Case Name Status Exec Time Memory
00_sample00.txt AC 8 ms 3576 KB
00_sample01.txt AC 2 ms 3460 KB
00_sample02.txt AC 2 ms 3460 KB
00_sample03.txt AC 2 ms 3560 KB
00_sample04.txt AC 3 ms 3448 KB
01_random00.txt AC 5 ms 3564 KB
01_random01.txt AC 7 ms 3596 KB
01_random02.txt AC 2 ms 3532 KB
01_random03.txt AC 2 ms 3588 KB
01_random04.txt AC 3 ms 3500 KB
01_random05.txt AC 7 ms 3612 KB
01_random06.txt AC 5 ms 3480 KB
01_random07.txt AC 3 ms 3516 KB
01_random08.txt AC 2 ms 3456 KB
01_random09.txt AC 3 ms 3500 KB
01_random10.txt AC 3 ms 3476 KB
01_random11.txt AC 4 ms 3440 KB
01_random12.txt AC 4 ms 3464 KB
01_random13.txt AC 2 ms 3496 KB
01_random14.txt AC 3 ms 3588 KB
01_random15.txt AC 2 ms 3532 KB
01_random16.txt AC 3 ms 3464 KB
01_random17.txt AC 4 ms 3596 KB
01_random18.txt AC 3 ms 3584 KB
01_random19.txt AC 4 ms 3468 KB
01_random20.txt AC 4 ms 3476 KB
01_random21.txt AC 5 ms 3552 KB
01_random22.txt AC 3 ms 3500 KB
01_random23.txt AC 2 ms 3500 KB
01_random24.txt AC 3 ms 3476 KB
01_random25.txt AC 2 ms 3584 KB
01_random26.txt AC 3 ms 3476 KB
01_random27.txt AC 5 ms 3508 KB
01_random28.txt AC 2 ms 3468 KB
01_random29.txt AC 2 ms 3520 KB
01_random30.txt AC 2 ms 3500 KB
01_random31.txt AC 4 ms 3504 KB
01_random32.txt AC 3 ms 3456 KB
01_random33.txt AC 4 ms 3576 KB
01_random34.txt AC 7 ms 3516 KB
01_random35.txt AC 4 ms 3508 KB
01_random36.txt AC 4 ms 3580 KB
01_random37.txt AC 2 ms 3576 KB
01_random38.txt AC 6 ms 3608 KB
01_random39.txt AC 5 ms 3604 KB
01_random40.txt AC 3 ms 3472 KB
01_random41.txt AC 4 ms 3592 KB
01_random42.txt AC 9 ms 3564 KB
01_random43.txt AC 8 ms 3564 KB
01_random44.txt AC 5 ms 3584 KB
01_random45.txt AC 7 ms 3504 KB
01_random46.txt AC 8 ms 3548 KB
01_random47.txt AC 4 ms 3592 KB
01_random48.txt AC 5 ms 3600 KB
01_random49.txt AC 5 ms 3500 KB
01_random50.txt AC 3 ms 3472 KB
01_random51.txt AC 3 ms 3476 KB
01_random52.txt AC 2 ms 3500 KB
01_random53.txt AC 2 ms 3524 KB
01_random54.txt AC 6 ms 3520 KB
01_random55.txt AC 9 ms 3468 KB
01_random56.txt AC 3 ms 3592 KB
01_random57.txt AC 3 ms 3500 KB
01_random58.txt AC 3 ms 3504 KB
01_random59.txt AC 3 ms 3588 KB
01_random61.txt AC 5 ms 3508 KB
01_random62.txt AC 4 ms 3552 KB
01_random63.txt AC 5 ms 3536 KB
01_random64.txt AC 4 ms 3580 KB
01_random65.txt AC 3 ms 3468 KB
01_random66.txt AC 4 ms 3456 KB
01_random67.txt AC 4 ms 3552 KB
01_random68.txt AC 6 ms 3512 KB
01_random69.txt AC 4 ms 3600 KB
01_random70.txt AC 3 ms 3468 KB
01_random71.txt AC 2 ms 3500 KB
01_random72.txt AC 5 ms 3548 KB
01_random73.txt AC 6 ms 3520 KB
01_random74.txt AC 3 ms 3484 KB
01_random75.txt AC 3 ms 3504 KB
01_random76.txt AC 5 ms 3468 KB
01_random77.txt AC 5 ms 3552 KB
01_random78.txt AC 5 ms 3504 KB
01_random79.txt AC 4 ms 3504 KB
01_random80.txt AC 7 ms 3600 KB
01_random81.txt AC 4 ms 3552 KB
01_random82.txt AC 3 ms 3460 KB
01_random83.txt AC 2 ms 3460 KB
01_random84.txt AC 3 ms 3556 KB
01_random85.txt AC 4 ms 3584 KB
01_random86.txt AC 4 ms 3516 KB
01_random87.txt AC 4 ms 3596 KB
01_random88.txt AC 3 ms 3560 KB
01_random89.txt AC 6 ms 3524 KB
01_random90.txt AC 11 ms 3476 KB
01_random91.txt AC 8 ms 3564 KB
01_random92.txt AC 3 ms 3504 KB
01_random93.txt AC 3 ms 3476 KB
01_random94.txt AC 5 ms 3608 KB
01_random95.txt AC 4 ms 3472 KB
01_random96.txt AC 3 ms 3596 KB
01_random97.txt AC 3 ms 3468 KB
01_random98.txt AC 3 ms 3588 KB
01_random99.txt AC 4 ms 3588 KB
02_manual00.txt AC 10 ms 3592 KB
02_manual01.txt AC 2 ms 3580 KB
02_manual02.txt AC 2 ms 3492 KB
02_manual03.txt AC 2 ms 3568 KB