Luyện thi cấp tốc

Xem PDF

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

XYZ là trung tâm luyện thi đại học lâu đời ở tỉnh Phú Thọ, nơi đây đã sản sinh ra vô số thủ khoa của cả nước. Thành công của trung tâm đến từ bí quyết “Đánh giá năng lực 4.0”. Trung tâm vận hành cách đánh giá dựa trên một siêu máy tính. Giả sử đối tượng học tập còn \(X\) ngày là đến kỳ thi đại học và đối tượng muốn ôn thi \(N\) môn, siêu máy tính sẽ tính được rằng nếu đối tượng học ở trung tâm trong \(j\) ngày để ôn thi môn thứ \(i\) thì sẽ đạt \(A_{i,j}\) điểm. Tất nhiên là càng học nhiều thì điểm sẽ cao lên nên \(A_{i,j} \leq A_{i, j + k} (k \geq 0)\). Dựa vào đánh giá trên trung tâm sẽ tìm ra phương pháp học tập tốt nhất cho đối tượng.

Hôm nay do có một chút trục trặc nên siêu máy tính không thể hoạt động được nữa , bạn hãy viết chương trình giúp trung tâm nhé!!

Input

  • Dòng đầu tiên chứa 2 số nguyên dương \(N\)\(X\).
  • \(N\) dòng tiếp theo, mỗi dòng ghi \(X\) số, số thứ \(j\)\(A_{i,j}\) (\(A_{i,j} \leq 10^6\)) là số điểm đạt được của môn thứ \(i\) nếu học trong \(j\) ngày.

Output

  • Hãy in ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N,X \leq 4\)
  • Subtask \(2\) (\(30\%\) số điểm): \(N \leq 100, X=1\)
  • Subtask \(3\) (\(40\%\) số điểm): \(N,X \leq 100\)

Example

Test 1

Input
3 3
4 8 9
0 5 6
3 6 7
Output
11

Bình luận

  • rodnguyen 9:11 p.m. 28 Tháng 3, 2025 chỉnh sửa 2

    Bình luận này vote lên 20 soi đáp án cho ae:()

    • LK30_LDĐ 8:36 a.m. 8 Tháng 11, 2024

      def main():
      # Đọc đầu vào
      N, X = map(int, input().split()) # N là số môn học, X là số ngày còn lại
      A = []

      for i in range(N):
          A.append(list(map(int, input().split())))  # Đọc bảng điểm cho mỗi môn học
      
      # Khởi tạo mảng dp: dp[j] là điểm số cao nhất có thể đạt được khi sử dụng j ngày
      dp = [0] * (X + 1)  # dp[i] sẽ chứa điểm số lớn nhất với i ngày
      
      # Quá trình tính toán bằng quy hoạch động
      for i in range(N):
          # Chúng ta phải lặp ngược từ X đến 0 để tránh việc dùng lại kết quả của chính vòng lặp này
          for j in range(X, 0, -1):
              for k in range(1, j + 1):  # thử tất cả các ngày từ 1 đến j
                  dp[j] = max(dp[j], dp[j - k] + A[i][k - 1])
      
      # Kết quả là dp[X], tổng điểm lớn nhất có thể đạt được trong X ngày
      print(dp[X])
      

      if name == "main":
      main()

      • PY1FLePhuocMinhHung 8:52 p.m. 9 Tháng 11, 2023

        Ai có thể giải thích cho mình vì sao lại là 11 ko.

        • Dao_Trong_Vinh 9:57 p.m. 20 Tháng 2, 2023

          sao lại là 11 vậy mọi người

          • kienduong 8:56 p.m. 11 Tháng 8, 2021

            Giúp em nữa ạ =((

            • tuanha2 9:15 a.m. 10 Tháng 8, 2021

              Ai giúp em bài này với ạ