fork download 
  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. using namespace std;
  4. const int N = 50,M = 505,K = 205,V = 250;
  5. const LL INF = 1ll << 60;
  6.  
  7. int L;
  8. struct Mat{
  9. 	LL a[V][V];
  10. 	inline void init(){
  11. 		for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j) a[i][j] = -INF;
  12. 	}
  13. };
  14. struct Vec{
  15. 	LL a[V];
  16. 	inline void init(){
  17. 		for (int i = 0; i < L; ++i) a[i] = -INF;	
  18. 	}
  19. };
  20. Mat operator * (const Mat A,const Mat B){
  21. 	static Mat T; T.init();
  22. 	for (int k = 0; k < L; ++k) for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j)
  23. 		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];
  24. 	return T;
  25. }
  26. Vec operator * (const Mat A,const Vec B){
  27. 	static Vec T; T.init();
  28. 	for (int i = 0; i < L; ++i) for (int j = 0; j < L; ++j)
  29. 		if (A.a[j][i] + B.a[j] > T.a[i]) T.a[i] = A.a[j][i] + B.a[j];
  30. 	return T;
  31. }
  32.  
  33. int n,m,T,k,c[N];
  34. int ex[M],ey[M],ez[M];
  35. Mat I,Tr,A[30];
  36. Vec st; int nowt;
  37. int id[N][5];
  38. struct Festival{
  39. 	int t,x,y;
  40. }ev[K];
  41. int main(){
  42. //	freopen("delicacy.in","r",stdin);
  43. //	freopen("delicacy.out","w",stdout);
  44. 	int i,j;	
  45. 	cin >> n >> m >> T >> k;
  46. 	I.init(); L = n * 5;
  47. 	for (i = 0; i < n; ++i) cin >> c[i];
  48. 	for (i = 0; i < n; ++i) I.a[i][i] = 0;
  49. 	for (i = 0; i < n; ++i) for (j = 0; j < 5; ++j) id[i][j] = j * n + i;
  50. 	for (i = 1; i <= m; ++i) cin >> ex[i] >> ey[i] >> ez[i],--ex[i],--ey[i];
  51. 	Tr.init();
  52. 	for (i = 0; i < n; ++i)
  53. 	for (j = 1; j < 5; ++j) Tr.a[id[i][j]][id[i][j-1]] = (j==1) ? (c[i]) : (0);
  54. 	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);
  55. 	A[0] = Tr;
  56. 	for (i = 1; i < 30; ++i) A[i] = A[i-1] * A[i-1];
  57.  
  58. 	for (i = 1; i <= k; ++i) cin >> ev[i].t >> ev[i].x >> ev[i].y,--ev[i].x;
  59. 	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]);
  60. 	if (ev[k].t != T){ ++k; ev[k].t = T,ev[k].x = ev[k].y = 0; }	
  61. 	st.init(); st.a[id[0][0]] = c[0]; nowt = 0;
  62. 	for (i = 1; i <= k; ++i){
  63. 		int dt = ev[i].t - nowt;
  64. 		for (j = 0; j < 30; ++j) if (dt>>j&1) st = A[j] * st;
  65. 		if (st.a[ev[i].x] >= 0) st.a[ev[i].x] += ev[i].y; 
  66. 		nowt = ev[i].t;
  67. 	}
  68. 	if (st.a[0] < 0) st.a[0] = -1;
  69. 	cout << st.a[0] << '\n';
  70. }
Success #stdin #stdout 0.01s 21060KB
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/h24fPN
language:
C++14 (gcc 8.3)
created:
3 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!