fork(1) download
copy 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <ctime>
  8. #include <deque>
  9. #include <functional>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <list>
  13. #include <map>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <string>
  19. #include <vector>
  20.  
  21. using namespace std;
  22.  
  23. #define FOR(i, N) for(int i = 0; i < N; i++)
  24. #define FOR1e(i, N) for(int i = 1; i <= N; i++)
  25. #define REP(i, M, N) for(int i = M; i < N; i++)
  26. #define REPe(i, M, N) for(int i = M; i <= N; i++)
  27. #define foreach(it, a) for(__typeof((a).begin()) it = (a).begin() ; it != (a).end(); it++)
  28. #define sc(N) scanf("%d", &N)
  29. #define scsc(M, N) scanf("%d %d", &M, &N)
  30. #define scscsc(M, N, O) scanf("%d %d %d", &M, &N, &O)
  31. #define all(s) s.begin(), s.end()
  32. #define gt(s) getline(cin, s)
  33. #define ms(a, v) memset(a, v, sizeof a)
  34. #define mp make_pair
  35. #define pb push_back
  36. #define pq priority_queue
  37. #define ss stringstream
  38.  
  39. typedef long long ll;
  40. typedef pair<int, int> pii;
  41. typedef vector<int> vi;
  42.  
  43. const int oo = 1 << 30;
  44. const int MAX = 1e5 + 1;
  45. const int mod = 1e9 + 7;
  46.  
  47. int dr[] = { 0, -1, 0, 1 };
  48. int dc[] = { 1, 0, -1, 0 };
  49.  
  50. inline int Pow(int b, int p) { if (!p) return 1; int sq = Pow(b, p >> 1); sq *= sq; if (p & 1) sq *= b; return sq; }
  51. inline int gcd(int a, int b) { if (!a) return b; return gcd(b % a, a); }
  52. inline string toString(int x) { ss SS; SS << x; return SS.str(); }
  53.  
  54. int t, n;
  55. ll arr[MAX], m;
  56.  
  57. ll fix(ll a) {
  58. 	return (a % m + m) % m;
  59. }
  60.  
  61. ll Kadane(){
  62. 	ll max_ending_here = fix(arr[0]), max_so_far = fix(arr[0]);
  63. 	ll ans = fix(arr[0]);
  64. 	for (int i = 1; i < n; i++){
  65. 		if (max_ending_here < 0) max_ending_here = fix(arr[i]);
  66. 		else max_ending_here = fix(fix(max_ending_here) + fix(arr[i]));
  67. 		//max_so_far = max(max_so_far, max_ending_here);
  68. 		if (max_ending_here > max_so_far){
  69. 			max_so_far = max_ending_here;
  70. 			ans = max(ans, max_so_far);
  71. 		}
  72. 	}
  73. 	return ans;
  74. }
  75.  
  76. int main(){
  77. 	#ifndef ONLINE_JUDGE
  78. 		freopen("in.txt", "r", stdin);
  79. 	#endif
  80. 	cin >> t;
  81. 	while (t--){
  82. 		cin >> n >> m;
  83. 		FOR(i, n)
  84. 			cin >> arr[i];
  85. 		cout << Kadane() << endl;
  86. 	}
  87. 	return 0;
  88. }
Success #stdin #stdout 0s 3920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8zLkTG
language:
C++14 (gcc 8.3)
created:
9 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!