fork download
copy 
  1. /*
  2. ______________________________
  3.                               |
  4. Shubham Singhal               |
  5.                               |
  6. CodeChef          torque      |
  7. HackerEarth       torque      |
  8. SPOJ              torque      |
  9. HackerRank        torquecode  |
  10. CodeForces        torquecode  |
  11. ______________________________| */
  12.  
  13.  
  14. // If Tyrion dies, I am gonna riot :P
  15.  
  16.  
  17. # include <bits/stdc++.h>
  18. using namespace std;
  19.  
  20. # define MOD         1000000007
  21. # define gc          getchar
  22. # define LL          long long
  23. # define L           long
  24. # define pb          push_back
  25. # define printi(x)   printf("%d",&x);
  26. # define printli(x)  printf("%ld",&x);
  27. # define printlli(x) printf("%lld",&x);
  28. # define mp          make_pair
  29. # define vi          vector<int>
  30. # define MAXN        100005
  31. # define INF         1e9
  32.  
  33.  
  34. template<class T>
  35. void in(T &x)
  36. {
  37.     register T c = gc();
  38.     x = 0;
  39.     T neg = 0;
  40.     for(;((c<48 || c>57) && c != '-');c = gc());
  41.     if(c=='-') {neg=1;c=gc();}
  42.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  43.     if(neg) x=-x;
  44. }
  45.  
  46. int sz,fib[30];
  47. unordered_map<int,int> fibcheck;
  48.  
  49. void fibi()
  50. {
  51.     fib[0]=0;
  52.     fib[1]=1;
  53.     fibcheck[0]=1;
  54.     fibcheck[1]=1;
  55.     sz=2;
  56.     for(int i=2;;i++)
  57.     {
  58.         fib[i]=fib[i-1]+fib[i-2];
  59.         if(fib[i]>100000)
  60.             break;
  61.         fibcheck[fib[i]]=1;
  62.         sz++;
  63.     }
  64. }
  65.  
  66. int dp[50005];
  67.  
  68. int solve(int n)
  69. {
  70.     if(fibcheck[n])
  71.         return 1;
  72.     if(dp[n]!=0)
  73.         return dp[n];
  74.     int ans=100;
  75.     for(int i=sz-1;i>=1;i--)
  76.     {
  77.         if(n-fib[i]<0)
  78.             continue;
  79.         ans=min(ans,1+solve(n-fib[i]));
  80.     }
  81.     return ans;
  82. }
  83. int cnt[100005];
  84. int main()
  85. {
  86.     fibi();
  87.     //cout<<sz<<endl;
  88.     int n,k;
  89.     in(n);
  90.     in(k);
  91.     for(int i=1;i<=50000;i++)
  92.         dp[i]=solve(i);
  93.     int a[n+1],b[n+1];
  94.     for(int i=1;i<=n;i++)
  95.         in(a[i]);
  96.     for(int i=1;i<=n;i++)
  97.         in(b[i]);
  98.  
  99.     int m,l,r;
  100.     in(m);
  101.     while(m--)
  102.     {
  103.         in(l);
  104.         in(r);
  105.         cnt[l]++;
  106.         cnt[r+1]--;
  107.     }
  108.     for(int i=1;i<=n;i++)
  109.         cnt[i]=cnt[i]+cnt[i-1];
  110.     for(int i=1;i<=n;i++)
  111.     {
  112.         if(dp[a[i]]<=k)
  113.             b[i]+=cnt[i];
  114.     }
  115.  
  116.     int q,x;
  117.     in(q);
  118.     while(q--)
  119.     {
  120.         in(x);
  121.         printf("%d\n",b[x]);
  122.     }
  123.  
  124.     return 0;
  125. }
  126.  
Time limit exceeded #stdin #stdout 5s 4048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7JFnp1
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!