結果
問題 | No.1111 コード進行 |
ユーザー | jjjjjjjtgpptmjj |
提出日時 | 2020-07-10 22:50:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 4,080 bytes |
コンパイル時間 | 2,388 ms |
コンパイル使用メモリ | 205,880 KB |
実行使用メモリ | 294,088 KB |
最終ジャッジ日時 | 2024-04-19 18:01:15 |
合計ジャッジ時間 | 10,497 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 175 ms
291,988 KB |
testcase_01 | AC | 174 ms
291,984 KB |
testcase_02 | AC | 173 ms
292,000 KB |
testcase_03 | AC | 205 ms
292,108 KB |
testcase_04 | AC | 148 ms
291,872 KB |
testcase_05 | AC | 146 ms
291,868 KB |
testcase_06 | AC | 147 ms
292,052 KB |
testcase_07 | AC | 144 ms
291,856 KB |
testcase_08 | AC | 145 ms
291,824 KB |
testcase_09 | AC | 143 ms
291,880 KB |
testcase_10 | AC | 143 ms
292,080 KB |
testcase_11 | AC | 146 ms
291,812 KB |
testcase_12 | AC | 148 ms
291,924 KB |
testcase_13 | AC | 146 ms
292,040 KB |
testcase_14 | AC | 149 ms
292,296 KB |
testcase_15 | AC | 145 ms
291,948 KB |
testcase_16 | AC | 244 ms
291,980 KB |
testcase_17 | AC | 120 ms
292,060 KB |
testcase_18 | AC | 116 ms
292,120 KB |
testcase_19 | AC | 114 ms
292,056 KB |
testcase_20 | AC | 116 ms
291,872 KB |
testcase_21 | AC | 115 ms
292,020 KB |
testcase_22 | AC | 117 ms
291,860 KB |
testcase_23 | AC | 113 ms
291,964 KB |
testcase_24 | AC | 114 ms
292,164 KB |
testcase_25 | AC | 116 ms
292,048 KB |
testcase_26 | AC | 119 ms
292,648 KB |
testcase_27 | AC | 115 ms
291,824 KB |
testcase_28 | AC | 115 ms
292,116 KB |
testcase_29 | AC | 112 ms
292,008 KB |
testcase_30 | AC | 154 ms
292,372 KB |
testcase_31 | AC | 115 ms
291,948 KB |
testcase_32 | AC | 169 ms
292,472 KB |
testcase_33 | AC | 191 ms
294,088 KB |
testcase_34 | AC | 116 ms
291,920 KB |
testcase_35 | AC | 113 ms
291,936 KB |
testcase_36 | AC | 114 ms
292,004 KB |
testcase_37 | AC | 113 ms
292,116 KB |
testcase_38 | AC | 156 ms
292,416 KB |
testcase_39 | AC | 258 ms
294,036 KB |
testcase_40 | AC | 274 ms
293,124 KB |
testcase_41 | AC | 116 ms
292,028 KB |
testcase_42 | AC | 115 ms
292,008 KB |
testcase_43 | AC | 230 ms
292,896 KB |
testcase_44 | AC | 115 ms
292,032 KB |
testcase_45 | AC | 116 ms
292,148 KB |
testcase_46 | AC | 118 ms
292,000 KB |
testcase_47 | AC | 119 ms
291,864 KB |
testcase_48 | AC | 120 ms
291,996 KB |
testcase_49 | AC | 117 ms
291,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() #define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; } #define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; } #define dump(x) cerr<<#x<<": "<<x<<endl; #define bit(k) (1LL<<(k)) typedef long long ll; typedef pair<int, int> i_i; typedef pair<ll, ll> l_l; template <class T> using vec = vector<T>; template <class T> using vvec = vector<vec<T>>; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << "{" <<p.first << ", " << p.second << "}"; return os; } 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; } const int INF = (ll)1e9; const ll INFLL = (ll)1e18+1; const ll MOD = (ll)1e9+7; const double PI = acos(-1.0); /* const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const string dir = "DRUL"; */ struct mint { long long x; mint(long long _x=0):x((_x%MOD+MOD)%MOD){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= MOD) x -= MOD; return *this; } mint& operator-=(const mint a) { if ((x += MOD-a.x) >= MOD) x -= MOD; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this; } 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 modpow(long long t) const { if (!t) return 1; mint a = modpow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime MOD mint inv() const { return modpow(MOD-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } friend std::ostream& operator<<(std::ostream& os, const mint& a){ os << a.x; return os; } }; // dp[i][j]:i個決めたときの複雑さjの個数 // ans = dp[N][K]; // その前がなんのコードだったかを持たないといけないからdp[i][j][k]になるか? // 300 ^ 4になって間に合わない // コード進行は有向グラフに落ちるので、そこからなんかできないかなー // bfsで探索しながら、N-1回遷移したら終わる感じにしたらどう? const int sz = 333; mint dp[sz][sz][sz]; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll N, M, K; cin >> N >> M >> K; vvec<l_l> G(sz); rep(i,M){ ll p, q, c; cin >> p >> q >> c; p--, q--; G[p].push_back({q, c}); } rep(i,sz)rep(j,sz)rep(k,sz)dp[i][j][k] = 0; mint ans = 0; /* calc */ // {頂点,移動回数,複雑度合計,個数} queue<pair<l_l,pair<ll, mint>>> q; rep(i,sz)q.push({{i, 1}, {0, 1}}); rep(i,sz)dp[i][1][0] =1; while(not q.empty()){ auto tmp = q.front(); q.pop(); int cur = tmp.first.first; int cnt = tmp.first.second; ll sum = tmp.second.first; mint dp_sum = tmp.second.second; if(cnt == N)continue; if(dp_sum.x != dp[cur][cnt][sum].x)continue; for(auto &p: G[cur]){ int nxt = p.first; int C = p.second; if(sum + C > K)continue; dp[nxt][cnt+1][sum + C] += dp_sum; q.push({{nxt, cnt+1},{sum + C, dp[nxt][cnt+1][sum + C]}}); } } rep(i,sz){ ans += dp[i][N][K]; } cout << ans << endl; }