fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define mt make_tuple
  3. #define mp make_pair
  4. #define pu push_back
  5. #define INF 1000000001
  6. #define MOD 1000000007
  7. #define ll long long int
  8. #define ld long double
  9. #define vi vector<int>
  10. #define vll vector<long long int>
  11. #define sc(n) scanf("%d",&n);
  12. #define scll(n) scanf("%lld",&n);
  13. #define scld(n) scanf("%Lf",&n);
  14. #define scr(s) {char temp[1000000];scanf("%s",temp);s = temp;}
  15.  
  16. using namespace std;
  17.  
  18. ll max1 = -1*INF;
  19.  
  20. int check(ll o,ll o1,ll d,ll sum1)
  21. {
  22.   // cout<<o<<" "<<o1<<" "<<d<<" "<<sum1<<endl;
  23.   if(sum1<=d && o1<=o) return 1;
  24.   return 0;
  25. }
  26.  
  27. ll max(ll x, ll y)
  28. {
  29.   if(x>y) return x;
  30.   return y;
  31. }
  32.  
  33. int main()
  34. {
  35.   int t;
  36.   sc(t);
  37.   for(int h=1;h<=t;h++)
  38.   {
  39.     max1 = -1*INF;
  40.     ll n,o,d;
  41.     scll(n);scll(o);scll(d);
  42.     vector<ll> v;
  43.     ll x1,x2,a,b,c,m,l;
  44.     scll(x1);scll(x2);scll(a);scll(b);scll(c);scll(m);scll(l);
  45.     v.pu(x1);v.pu(x2);
  46.     for(int i=2;i<n;i++) v.pu(((a*v[i-1])%m+(b*v[i-2])%m + c)%m);
  47.     for(int i=0;i<v.size();i++) v[i]+=l;
  48.     // for(int i=0;i<n;i++){ll a;scll(a);v.pu(a);}
  49.     int left = 0,right = 0;
  50.     ll sum1 = v[0],o1 = 0;
  51.     if(v[0]%2) o1 = 1;
  52.     // for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl;
  53.     while(right<n && left<=right)
  54.     {
  55.       // cout<<"here"<<endl;
  56.       while(right<n && check(o,o1,d,sum1))
  57.       {
  58.         // cout<<"left: "<<left<<" right: "<<right<<" o1: "<<o1<<" sum1: "<<sum1<<endl;
  59.         max1 = max(max1,sum1);
  60.         right++;
  61.         if(v[right]%2) o1++;
  62.         ll k = sum1;
  63.         sum1+=v[right];
  64.         // while(sum1<=d && left<right)
  65.         // {
  66.         //   if(v[left]%2) o1--;
  67.         //   sum1-=v[left];
  68.         //   left++;
  69.         // }
  70.         // if(k>sum1 && sum1<=0) break;
  71.       }
  72.       if(v[left]%2) o1--;
  73.       sum1-=v[left];
  74.       left++;
  75.     }
  76.     while(right==n && left<n)
  77.     {
  78.       if(check(o,o1,d,sum1)) {max1 = max(max1,sum1);}
  79.       if(v[left]%2) o1--;
  80.       sum1-=v[left];
  81.       left++;
  82.     }
  83.     if(max1!=-1*INF) printf("Case #%d: %lld\n",h,max1);
  84.     else printf("Case #%d: IMPOSSIBLE\n",h);
  85.   }
  86.   return 0;
  87. }
  88.  
  89. /*
  90. 1
  91. 6 1 -100
  92. 1 1 1 1 0 100 0
  93.  
  94. */
  95.  
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
5
6 1 1000000000000000
1 1 1 1 0 100 0
6 1 -100
1 1 1 1 0 100 0
10 1 8
4 3 4 1 5 20 -10
10 2 8
4 3 4 1 5 20 -10
10 1 8
4 3 4 1 5 20 -19
stdout
copy 
Case #1: 13
Case #2: IMPOSSIBLE
Case #3: 7
Case #4: 8
Case #5: -5
https://ideone.com/zrYSlH
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!