fork download 
  1. // Vivek
  2. #include <bits/stdc++.h>
  3.  
  4. #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  5. #define ll long long 
  6. using namespace std;
  7.  
  8. #ifdef ONLINE_JUDGE
  9. #define endl '\n'
  10. #endif
  11. template<class T> void smax(T& a, T val) {if (a < val) a = val;}
  12. const int N = 5*1e5 + 10;
  13.  
  14. ll n, m, a, o, d, t, b, c, l;
  15.  
  16. int main(){_
  17.  
  18. 	#define int ll
  19. 	#ifndef ONLINE_JUDGE
  20. 		freopen("input.txt", "r", stdin);
  21. 		freopen("output.txt", "w", stdout);
  22. 	#endif
  23.  
  24. 	cin >> t;
  25.  
  26. 	for (int test = 0; test < t; ++test)
  27. 	{
  28. 		cin >> n >> o >> d;	
  29.  
  30. 		std::vector<ll> x(n+1, 0);
  31. 		cin >> x[1] >> x[2] >> a >> b >> c >> m >> l;
  32.  
  33. 		cout << "Case #" << (test+1)  <<  ": ";
  34.  
  35. 		std::vector<ll> s(n+1);
  36.  
  37. 		s[1] = x[1] + l;
  38. 		s[2] = x[2] + l;
  39.  
  40. 		for (int i = 3; i <= n; ++i)
  41. 		{
  42. 			x[i] = (a*x[i-1] + b*x[i-2] + c) % m;
  43. 			s[i] = x[i] + l;
  44. 		}
  45.  
  46. 		ll i = 1, ans = -2e18, sum = 0, j = 1, co = 0;
  47.  
  48. 		while(i <= n){
  49.  
  50. 			while(j <= n){
  51. 				co += ((s[j] % 2) != 0);
  52. 				if(co > o){
  53. 					--co;
  54. 					break;
  55. 				}
  56. 				if(sum + s[j] > d){
  57. 					co -= ((s[j] % 2) != 0);
  58. 					break;
  59. 				}
  60. 				sum += s[j];
  61. 				if(sum <= d)smax(ans, sum);
  62. 				++j;
  63. 			}
  64.  
  65. 			if(i == j){
  66. 				sum = 0;
  67. 				++i, ++j;
  68. 				co = 0;
  69. 				continue;
  70. 			}
  71.  
  72. 			if(sum <= d)smax(ans, sum);
  73.  
  74. 			if((s[i] % 2) != 0 and i != j){
  75. 				co--;
  76. 			}
  77.  
  78. 			sum -= s[i];
  79. 			++i;
  80. 		}
  81.  
  82. 		if(ans == -2e18){
  83. 			cout << "IMPOSSIBLE" << endl;
  84. 			continue;
  85. 		}
  86.  
  87. 		cout  <<  ans  <<  endl;
  88. 	}
  89.  
  90. 	return 0;
  91. }
Success #stdin #stdout 0s 4140KB
comments (?)
stdin 
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 
Case #1: 13
Case #2: IMPOSSIBLE
Case #3: 7
Case #4: 8
Case #5: -5
https://ideone.com/2dMlad
language:
C++14 (gcc 8.3)
created:
6 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!