daily pastebin goal
26%
SHARE
TWEET

T157T1

yicongli Mar 20th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=1e7+5;
  17.  
  18. int n;
  19. ll c[N];
  20.  
  21. inline void insert(int x,ll v){
  22.     for(int i=x;i<=n;i+=(i&-i)){
  23.         c[i]=max(c[i],v);
  24.     }
  25. }
  26.  
  27. inline ll query(int x){
  28.     if(x<=0)return 0;
  29.     ll ret=0;
  30.     for(int i=x;i;i^=(i&-i)){
  31.         ret=max(c[i],ret);
  32.     }
  33.     return ret;
  34. }
  35.  
  36. ll f[N];
  37. int t[N];
  38. int a[N];
  39.  
  40. vector<int>G[N];
  41.  
  42. int main(){
  43.     freopen("fc.in","r",stdin);
  44.     freopen("fc.out","w",stdout);
  45.     r(n);
  46.     for(int i=1;i<=n;++i){
  47.         r(t[i]);
  48.         if(i+t[i]<=n)G[i+t[i]].push_back(i);
  49.     }
  50.     for(int i=1;i<=n;++i){
  51.         r(a[i]);
  52.         for(int j=0;j<G[i].size();++j){
  53.             insert(G[i][j],f[G[i][j]]);
  54.         }
  55.         f[i]=query(i-t[i])+(ll)a[i]*t[i];
  56.     }
  57.     ll ans=0;
  58.     for(int i=1;i<=n;++i){
  59.         ans=max(ans,f[i]);
  60.     }
  61.     printf("%lld\n",ans);
  62.     return 0;
  63. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top