?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
137041441 |
Practice: newbie_forever_at_cp |
1614D2 - 59 | C++17 (GCC 7-32) | Memory limit exceeded on test 16 | 2479 ms | 1048576 KB | 2021-11-26 16:53:01 | 2021-11-26 16:53:09 |
#include<bits/stdc++.h> #define pb push_back //#define mp make_pair #define fastread ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define openfile ifstream cin; ofstream cout; cin.open("input.txt"); cout.open("output.txt"); #define f(i, x, y) for(ll i = x; i < y; i++) #define all(X) X.begin(), X.end() // #define int long long #define ll long long #define key pair<ll, ll> #define keyy pair<pair<ll, ll>, ll> #define keyyy pair<pair<ll, ll>, pair<ll, ll>> // #define ordered_set<T> tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> #define keyd pair<double, double> #define ff first #define ss second #define double long double const ll mod = 1e9 + 7; // const ll mod = 998244353; // const ll mod = 360 * 12 * (double)1e10; const ll inf = 1e18 + 5; const ll infi = 2e9; using namespace std; const int siz = 2e7 + 5; int cnt[siz], se[siz]; int pm[siz]; ll dp[siz]; vector<int> d[siz]; main() { fastread; f(i, 1, siz) se[i] = i; f(i, 2, siz) { if(se[i] != i) continue; for(int j = i; j < siz; j += i) se[j] = i; } fastread; int n; cin>>n; //n = 1e5 + 5; int a[n+1]; f(i, 1, n+1) a[i] = siz-i; int a[n+1]; f(i, 1, n+1) cin>>a[i]; f(i, 1, n+1) { int t = a[i]; int p = 0, c = 0; while(t > 1) { if(se[t] == p) c++; else { pm[p] = max(pm[p], c); c = 1; p = se[t]; } t /= se[t]; } pm[p] = max(pm[p], c); } d[1].pb(1); f(i, 2, siz) { bool fl = true; int t = i, p = 0, c = 0;; while(t > 1) { if(se[t] == p) c++; else { if(c > pm[p]){ fl = false; break; } c = 1; p = se[t]; } t /= se[t]; } if(c > pm[p]) fl = false; if(not fl) continue; c = 0; int pr = se[i]; t = i; while(t%pr == 0) { t /= pr; c++; } d[i] = d[t]; for(int j : d[t]) { int p = pr; f(k, 1, c+1) { d[i].pb(j*p); p *= pr; } } } f(i, 1, n+1) for(int j : d[a[i]]) cnt[j]++; ll ans = n; cnt[1] = dp[1] = n; f(i, 2, siz) { for(int j : d[i]) dp[i] = max(dp[i], dp[j] + (ll)cnt[i] * (i - j)); ans = max(ans, dp[i]); } // f(i, 1, 30) cout<<pm[i]<<" "; cout<<"\n"; // f(i, 1, 30){ cout<<i<<" "; for(int j : d[i]) cout<<j<<" "; cout<<"\n"; } cout<<"\n"; // f(i, 1, 30) cout<<dp[i]<<" "; cout<<"\n"; cout<<ans<<"\n"; }
?
?
?
?