fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "VISITPLACE"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+7;
  49. const int maxn=1e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71.  
  72. const int N = 50,M = 505,K = 205,V = 250;
  73. const ll INF = 1ll << 60;
  74.  
  75. int L;
  76. struct Mat{
  77. 	ll a[V][V];
  78. 	inline void init(){
  79. 		for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j) a[i][j] = -INF;
  80. 	}
  81. };
  82. struct Vec{
  83. 	ll a[V];
  84. 	inline void init(){
  85. 		for (int i = 0; i < L; ++i) a[i] = -INF;
  86. 	}
  87. };
  88. Mat operator * (const Mat A,const Mat B){
  89. 	static Mat T; T.init();
  90. 	for (int k = 0; k < L; ++k) for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j)
  91. 		if (A.a[i][k] + B.a[k][j] > T.a[i][j]) T.a[i][j] = A.a[i][k] + B.a[k][j];
  92. 	return T;
  93. }
  94. Vec operator * (const Mat A,const Vec B){
  95. 	static Vec T; T.init();
  96. 	for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j)
  97. 		if (A.a[j][i] + B.a[j] > T.a[i]) T.a[i] = A.a[j][i] + B.a[j];
  98. 	return T;
  99. }
  100.  
  101. int n,m,T,k,c[N];
  102. int ex[M],ey[M],ez[M];
  103. Mat I,Tr,A[30];
  104. Vec st; int nowt;
  105. int id[N][5];
  106. struct Festival{
  107. 	int t,x,y;
  108. }ev[K];
  109.  
  110. int main(){
  111.     rf();
  112. 	int i,j;
  113. 	cin >> n >> m >> T >> k;
  114. 	I.init(); L = n * 5;
  115. 	for (i = 0; i < n; ++i) cin >> c[i];
  116. 	for (i = 0; i < n; ++i) I.a[i][i] = 0;
  117. 	for (i = 0; i < n; ++i) for (j = 0; j < 5; ++j) id[i][j] = j * n + i;
  118. 	for (i = 1; i <= m; ++i) cin >> ex[i] >> ey[i] >> ez[i],--ex[i],--ey[i];
  119. 	Tr.init();
  120. 	for (i = 0; i < n; ++i)
  121. 	for (j = 1; j < 5; ++j) Tr.a[id[i][j]][id[i][j-1]] = (j==1) ? (c[i]) : (0);
  122. 	for (i = 1; i <= m; ++i) Tr.a[id[ex[i]][0]][id[ey[i]][ez[i]-1]] = (ez[i]==1) ? (c[ey[i]]) : (0);
  123. 	A[0] = Tr;
  124. 	for (i = 1; i < 30; ++i) A[i] = A[i-1] * A[i-1];
  125.  
  126. 	for (i = 1; i <= k; ++i) cin >> ev[i].t >> ev[i].x >> ev[i].y,--ev[i].x;
  127. 	for (i = 1; i <= k; ++i) for (j = i+1; j <= k; ++j) if (ev[j].t < ev[i].t) swap(ev[i],ev[j]);
  128. 	if (ev[k].t != T){ ++k; ev[k].t = T,ev[k].x = ev[k].y = 0; }
  129. 	st.init(); st.a[id[0][0]] = c[0]; nowt = 0;
  130. 	for (i = 1; i <= k; ++i){
  131. 		int dt = ev[i].t - nowt;
  132. 		for (j = 0; j < 30; ++j) if (dt>>j&1) st = A[j] * st;
  133. 		if (st.a[ev[i].x] >= 0) st.a[ev[i].x] += ev[i].y;
  134. 		nowt = ev[i].t;
  135. 	}
  136. 	if (st.a[0] < 0) st.a[0] = -1;
  137. 	cout << st.a[0] << '\n';
  138. }
  139.  
Success #stdin #stdout 0.01s 21400KB
comments (?)
stdin 
4 8 16 3
3 1 2 4
1 2 1
1 3 1
1 3 2
3 4 3
2 3 2
3 2 1
4 2 1
4 1 5
3 3 5
1 2 5
5 4 20
stdout 
39
https://ideone.com/4kYGAY
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!