trang chủ / đề bài / icpc24_mb_c

Tổng lớn nhất chia hết

Đề bài

Mô tả

Cho ma trận A kích thước N×M gồm các số nguyên được sinh ngẫu nhiên đều trong đoạn [0,k−1]. Các hàng được đánh số từ 1 đến N, các cột được đánh số từ 1 đến M.

Gọi S(r1,c1,r2,c2) là tổng các phần tử của hình chữ nhật con từ hàng r1 đến hàng r2 và từ cột c1 đến cột c2:

S(r1,c1,r2,c2)=∑r1≤i≤r2∑c1≤j≤c2A[i][j].

Hãy tìm giá trị lớn nhất của S(r1,c1,r2,c2) chia hết cho k.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên N, M và k (1≤N×M≤106, 1≤k≤106).
  • N dòng tiếp theo, mỗi dòng chứa M số nguyên trong đoạn [0,k−1].

Dữ liệu ra

In ra một số nguyên là tổng lớn nhất tìm được mà chia hết cho k. Nếu không có hình chữ nhật nào thỏa mãn, in ra 0.

Ràng buộc

  • 1≤N×M≤106
  • 1≤k≤106
  • Các phần tử của ma trận được sinh ngẫu nhiên đều, độc lập trong [0,k−1] (trừ các ví dụ).

Ví dụ

Input Output Giải thích
6 7 5
1 2 0 0 3 3 1
3 0 3 1 0 1 2
1 1 0 2 0 3 2
2 4 1 4 4 0 3
0 2 3 0 2 2 1
0 0 3 0 1 0 4
65 Ví dụ của đề gốc.
3 3 10
3 9 4
8 1 6
7 5 2
20 Ví dụ bổ sung, tính bằng lời giải mẫu. Hình chữ nhật hàng 1 đến 2, cột 2 đến 3 có tổng 9+4+1+6=20. Tổng cả ma trận là 45, không có hình nào có tổng 40 hoặc 30.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0