Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- #define ll long long
- #define ld long double
- #define pii pair <int,int>
- #define endl '\n'
- #define FILE "chaos"
- #pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")
- using namespace std;
- const int mod = 1e9 + 7;
- const int N = 2e5 + 5;
- struct block{
- int l, r, mx, gcd;
- };
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- srand(time(0));
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m, k;
- cin >> n >> m >> k;
- vector <int> a;
- a.pb(0);
- for (int i = 0; i < n; i++){
- int cnt;
- cin >> cnt;
- while (cnt--){
- int x;
- cin >> x;
- a.pb(x);
- }
- }
- vector <int> dp(m, 0);
- dp[0] = 0;
- vector <block> blocks;
- for (int i = 1; i <= m; i++){
- vector <block> nblocks;
- nblocks.pb({i - 1, i - 1, a[i], -1e9});
- int g = a[i];
- for (auto &x : blocks){
- g = __gcd(g, x.gcd);
- x.gcd = g;
- nblocks.pb(x);
- }
- blocks.clear();
- for (int j = 0; j < nblocks.size(); ){
- int l = nblocks[j].l, r = nblocks[j].r, mx = nblocks[j].mx, g = nblocks[j++].gcd;
- while (j < nblocks.size() && nblocks[j].gcd == g){
- l = nblocks[j].l;
- mx = max(mx, nblocks[j++].mx);
- }
- blocks.pb({l, r, g, mx});
- }
- dp[i] = -1e9;
- for (auto &x : blocks){
- if (x.l <= i - k && x.r >= i - k) x.mx = max(x.mx, dp[i - k]);
- dp[i] = max(dp[i], x.mx + x.gcd);
- }
- }
- cout << dp[m] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement