Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- template<typename T>
- using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
- #define X first
- #define Y second
- #define sz(a) (int)a.size()
- #define pb push_back
- void solve();
- int main() {
- // freopen("schools.in", "r", stdin);
- ios_base::sync_with_stdio(0), cin.tie(0);
- int t = 1;
- // cin >> t;
- while(t--) solve();
- return 0;
- }
- ll ans, n, m, last[1000005], p;
- void solve() {
- cin >> n >> m >> p;
- ll prefix[n + 15][m + 15];
- for (ll i = 0; i <= n; ++i) {
- for (ll j = 0; j <= m; ++j) {
- prefix[i][j] = 0;
- }
- }
- for (ll i = 1; i <= n; ++i) {
- for (ll j = 1; j <= m; ++j) {
- ll t;
- cin >> t;
- prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + t;
- }
- }
- // if (n <= m) {
- for (ll i = 1; i <= n; ++i) {
- for (ll j = i; j <= n; ++j) {
- for (ll z = 0; z < p; ++z) last[z] = -1;
- for (ll z = 1; z <= m; ++z) {
- ll sum = prefix[j][z] - prefix[i - 1][z];
- if (sum % p == 0) {
- ans = max(ans, sum);
- continue;
- }
- if (last[sum % p] != -1) {
- ll sum2 = prefix[j][last[sum % p]] - prefix[i - 1][last[sum % p]];
- ans = max(ans, sum - sum2);
- } else {
- last[sum % p] = z;
- }
- }
- }
- }
- cout << ans << '\n';
- // }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement