Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5. typedef long long ll;
  6. typedef long double ld;
  7. template<typename T>
  8. using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9. #define X first
  10. #define Y second
  11. #define sz(a) (int)a.size()
  12. #define pb push_back
  13.  
  14. void solve();
  15.  
  16. int main() {
  17. // freopen("schools.in", "r", stdin);
  18. ios_base::sync_with_stdio(0), cin.tie(0);
  19. int t = 1;
  20. // cin >> t;
  21. while(t--) solve();
  22. return 0;
  23. }
  24.  
  25. ll ans, n, m, last[1000005], p;
  26.  
  27. void solve() {
  28. cin >> n >> m >> p;
  29. ll prefix[n + 15][m + 15];
  30. for (ll i = 0; i <= n; ++i) {
  31. for (ll j = 0; j <= m; ++j) {
  32. prefix[i][j] = 0;
  33. }
  34. }
  35. for (ll i = 1; i <= n; ++i) {
  36. for (ll j = 1; j <= m; ++j) {
  37. ll t;
  38. cin >> t;
  39. prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + t;
  40. }
  41. }
  42. // if (n <= m) {
  43. for (ll i = 1; i <= n; ++i) {
  44. for (ll j = i; j <= n; ++j) {
  45. for (ll z = 0; z < p; ++z) last[z] = -1;
  46. for (ll z = 1; z <= m; ++z) {
  47. ll sum = prefix[j][z] - prefix[i - 1][z];
  48. if (sum % p == 0) {
  49. ans = max(ans, sum);
  50. continue;
  51. }
  52. if (last[sum % p] != -1) {
  53. ll sum2 = prefix[j][last[sum % p]] - prefix[i - 1][last[sum % p]];
  54. ans = max(ans, sum - sum2);
  55. } else {
  56. last[sum % p] = z;
  57. }
  58. }
  59. }
  60. }
  61. cout << ans << '\n';
  62. // }
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement