fork(6) download
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890123456789LL
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. typedef long long cat;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. // palindromic tree is better than splay tree!
  38. #define lld I64d
  39. #endif
  40.  
  41. int main() {
  42. cin.sync_with_stdio(0);
  43. cin.tie(0);
  44. cout << fixed << setprecision(10);
  45. int T;
  46. cin >> T;
  47. while(T--) {
  48. int N;
  49. cin >> N;
  50. vector<int> M(N);
  51. vector< vector<int> > A(N);
  52. for(int i =0; i < N; i++) {
  53. cin >> M[i];
  54. A[i].resize(M[i]);
  55. for(int j =0; j < M[i]; j++) cin >> A[i][j];
  56. }
  57. vector< vector<cat> > S(N);
  58. for(int i =0; i < N; i++) S[i].resize(M[i],0);
  59. for(int i =1; i < N; i++) {
  60. cat max1 =-OVER9000, max2 =-OVER9000;
  61. for(int j =0; j < M[i-1]; j++) {
  62. max1 =max(max1,S[i-1][(j+1)%M[i-1]]-1LL*i*A[i-1][j]);
  63. max2 =max(max2,S[i-1][(j+1)%M[i-1]]+1LL*i*A[i-1][j]);
  64. }
  65. for(int j =0; j < M[i]; j++)
  66. S[i][j] =max(S[i][j],max(max1+1LL*i*A[i][j],max2-1LL*i*A[i][j]));
  67. }
  68. cat ans =0;
  69. for(int i =0; i < M[N-1]; i++) ans =max(ans,S[N-1][i]);
  70. cout << ans << "\n";
  71. }
  72. }
  73.  
  74. // look at my code
  75. // my code is amazing
  76.  
Runtime error #stdin #stdout 0s 16064KB
stdin
Standard input is empty
stdout
Standard output is empty