daily pastebin goal
40%
SHARE
TWEET

Untitled

a guest Mar 24th, 2019 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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, version;
  26. ll is[1000005];
  27.  
  28. void solve() {
  29.     cin >> n >> m >> p;
  30.     ll prefix[n + 15][m + 15];
  31.     for (ll i = 0; i <= n; ++i) {
  32.         for (ll j = 0; j <= m; ++j) {
  33.             prefix[i][j] = 0;
  34.         }
  35.     }
  36.     for (ll i = 1; i <= n; ++i) {
  37.         for (ll j = 1; j <= m; ++j) {
  38.             ll t;
  39.             cin >> t;
  40.             prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + t;
  41.         }
  42.     }
  43.     if (n <= m) {
  44.         for (ll i = 1; i <= n; ++i) {
  45.             for (ll j = i; j <= n; ++j) {
  46.                 ++version;
  47.                 for (ll z = 1; z <= m; ++z) {
  48.                     ll sum = prefix[j][z] - prefix[i - 1][z];
  49.                     if (sum % p == 0) {
  50.                         ans = max(ans, sum);
  51.                         continue;
  52.                     }
  53.                     if (is[sum % p] == version) {
  54.                         ll sum2 = prefix[j][last[sum % p]] - prefix[i - 1][last[sum % p]];
  55.                         ans = max(ans, sum - sum2);
  56.                     } else {
  57.                         is[sum % p] = version;
  58.                         last[sum % p] = z;
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.         cout << ans << '\n';
  64.     } else {
  65.         for (ll i = 1; i <= m; ++i) {
  66.             for (ll j = i; j <= m; ++j) {
  67.                 ++version;
  68.                 for (ll z = 1; z <= n; ++z) {
  69.                     ll sum = prefix[z][j] - prefix[z][i - 1];
  70.                     if (sum % p == 0) {
  71.                         ans = max(ans, sum);
  72.                         continue;
  73.                     }
  74.                     if (is[sum % p] == version) {
  75.                         ll sum2 = prefix[last[sum % p]][j] - prefix[last[sum % p]][i - 1];
  76.                         ans = max(ans, sum - sum2);
  77.                     } else {
  78.                         is[sum % p] = version;
  79.                         last[sum % p] = z;
  80.                     }
  81.                 }
  82.             }
  83.         }
  84.         cout << ans << '\n';
  85.     }
  86. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top