結果
問題 |
No.1111 コード進行
|
ユーザー |
|
提出日時 | 2020-07-10 22:33:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 202 ms / 2,000 ms |
コード長 | 2,402 bytes |
コンパイル時間 | 1,925 ms |
コンパイル使用メモリ | 172,728 KB |
実行使用メモリ | 225,376 KB |
最終ジャッジ日時 | 2024-10-11 09:53:43 |
合計ジャッジ時間 | 9,043 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>void chmin(T&a,const T&b){if(a>b)a=b;} template<class T>void chmax(T&a,const T&b){if(a<b)a=b;} ll nextLong() { ll x; scanf("%lld", &x); return x;} const ll MOD = 1e9 + 7; struct mint { ll x; mint(ll x=0):x((x%MOD+MOD)%MOD){} 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 pow(ll b) const { mint res(1), a(*this); while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } // 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;} }; ostream& operator<<(ostream& os, const mint& a) {os << a.x; return os;} mint dp[305][305][305]; int main2() { const int V = 300; REP(i, 305) REP(j, 305) REP(k, 305) dp[i][j][k] = 0; int N = nextLong(); int M = nextLong(); int K = nextLong(); vector< vector< pair<int, int>> > g(V); REP(m, M) { int P = nextLong() - 1; int Q = nextLong() - 1; int C = nextLong(); g[P].push_back({Q, C}); } REP(i, V) dp[1][i][0] += 1; for (int i = 1; i < N; i++) { for (int k = 0; k <= K; k++) { for (int m = 0; m < V; m++) { mint cur = dp[i][m][k]; if (cur.x == 0) continue; for (auto e : g[m]) { if (k + e.second <= K) { dp[i+1][e.first][k + e.second] += cur; } } } } } mint ans = 0; REP(i, V) ans += dp[N][i][K]; cout << ans << endl; return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }