thiet ke website

[C++] SPOJ.COM – Problem Bonus – VOI 2011 Phần thưởng

Để bài:

(Nguồn: SPOJ) Tuấn là người chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j] (1 <= i, j <= n)

Đề nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận được.

phần thưởng

Dữ liệu:
• Dòng thứ nhất chứa hai sô nguyên dương n, k (n <= 1000, n/3 <= k <= n).
• Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dương, số thứ j là a[i,j] (a[i,j] <= 1000)

Kết quả: Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được.

Ví dụ:
SPOJ-Bonus 2011Ràng buộc: 50% số test ứng với 50% số điểm của bài có n <= 100.

Sourcecode C++

#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;

int n,k;
static int a[1000][1000];
static long l[1000];
long tmax=-1;

void readfile() {
  ifstream fi("bonus.inp");
  if (fi.is_open()) {
      fi>>n;
      fi>>k;

      for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) fi>>a[i][j];

      fi.close();
   }
}

void maximizetmp(long &tmp) {
  if (tmp>tmax) tmax=tmp;
}

void initiate() {
  long tmp=0;

  for (int i=1; i<=n; i++)
    for (int j=1; j<=k; j++) l[i]+=a[i][j];

  for (int i=1; i<=n-k+1; i++) {
      tmp=0;
      for (int j=i; j<=i+k-1; j++) tmp+=l[j];
      maximizetmp(tmp);
    }
}

void solve() {
  long tmp=0;
  for (int column=1; column<=n-k; column++) {
      for (int i=1; i<=n; i++) l[i]=l[i] - a[i][column] + a[i][column+k];

      for (int i=1; i<=n-k+1; i++) {
          tmp=0;
          for (int j=i; j<=i+k-1; j++) tmp+=l[j];
          maximizetmp(tmp);
        }
    }
}

void writefile() {
  ofstream fo("bonus.out");
  if (fo.is_open()) fo<<tmax;
}

int main() {
  readfile();
  initiate();
  solve();
  writefile();
  return 0;
}
Thiet ke logo

Bài viết liên quan

[Java cơ bản] Bài 39: Constructor (Phần 1)

[Java cơ bản] Bài 39: Constructor (Phần 1)

Video này sẽ giới thiệu về Constructor trong Java. Chúc các bạn học tập tốt và đạt kết quả.

[Java cơ bản] Bài 5: Lớp và phương thức

[Java cơ bản] Bài 5: Lớp và phương thức

Trong bài này giải thích về lớp và phương thức trong hướng đối tượng. Chúc các bạn học tập vui vẻ 😀

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Ban đầu, DevExpress phát triển UI Controls cho Borland Delphi/C++ Builder, ActiveX Controls cho Microsoft Visual Studio. Hiện nay, DevExpress hướng tới lập trình viên sử dụng Delphi/c++ Builder, Visual Studio và HTML5/Javascript. DevExpress là bộ công cụ hữu ích hỗ trợ các lập trình…

[Java cơ bản] Bài 17: Cấu trúc vòng lặp Do-While

[Java cơ bản] Bài 17: Cấu trúc vòng lặp Do-While

Cấu trúc lệnh do while tương tự cấu trúc lệnh while. Khác nhau là do while dù biểu thức điều kiện sai nó vẫn thực hiện vòng lặp ít nhất một lần, còn while nếu biểu thức điều kiện sai thì nó sẽ không làm…

Bình luận ()