Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define pb push_back
  6. #define ll long long
  7. #define ld long double
  8. #define pii pair <int,int>
  9. #define endl '\n'
  10. #define FILE "chaos"
  11.  
  12. #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
  13.  
  14. using namespace std;
  15.  
  16. const int mod = 1e9 + 7;
  17. const int N = 2e5 + 5;
  18.  
  19. struct block{
  20. int l, r, mx, gcd;
  21. };
  22.  
  23. int main() {
  24. ios_base::sync_with_stdio(0);
  25. cin.tie(0);
  26. cout.tie(0);
  27. srand(time(0));
  28. #ifdef LOCAL
  29. freopen("input.txt", "r", stdin);
  30. freopen("output.txt", "w", stdout);
  31. #else
  32. freopen("input.txt", "r", stdin);
  33. freopen("output.txt", "w", stdout);
  34. #endif
  35. int n, m, k;
  36. cin >> n >> m >> k;
  37. vector <int> a;
  38. a.pb(0);
  39. for (int i = 0; i < n; i++){
  40. int cnt;
  41. cin >> cnt;
  42. while (cnt--){
  43. int x;
  44. cin >> x;
  45. a.pb(x);
  46. }
  47. }
  48. vector <int> dp(m, 0);
  49. dp[0] = 0;
  50. vector <block> blocks;
  51. for (int i = 1; i <= m; i++){
  52. vector <block> nblocks;
  53. nblocks.pb({i - 1, i - 1, a[i], -1e9});
  54. int g = a[i];
  55. for (auto &x : blocks){
  56. g = __gcd(g, x.gcd);
  57. x.gcd = g;
  58. nblocks.pb(x);
  59. }
  60. blocks.clear();
  61. for (int j = 0; j < nblocks.size(); ){
  62. int l = nblocks[j].l, r = nblocks[j].r, mx = nblocks[j].mx, g = nblocks[j++].gcd;
  63. while (j < nblocks.size() && nblocks[j].gcd == g){
  64. l = nblocks[j].l;
  65. mx = max(mx, nblocks[j++].mx);
  66. }
  67. blocks.pb({l, r, g, mx});
  68. }
  69. dp[i] = -1e9;
  70. for (auto &x : blocks){
  71. if (x.l <= i - k && x.r >= i - k) x.mx = max(x.mx, dp[i - k]);
  72. dp[i] = max(dp[i], x.mx + x.gcd);
  73. }
  74. }
  75. cout << dp[m] << endl;
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement