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 26: Thừa kế

[Java cơ bản] Bài 26: Thừa kế

Đây là video giới thiệu về cách thừa kế giữa các class và interface ở trong Java như thế nào. Chúc các bạn học tốt…

Hướng dẫn ẩn ổ đĩa trên Windows bằng Registry

Hướng dẫn ẩn ổ đĩa trên Windows bằng Registry

Video này sẽ hướng dẫn các bạn chi tiết cụ thể cách ẩn ổ đĩa trên máy tính bằng Registry Việc ẩn ổ đĩa (C: D: E: …) không làm hư hại hoặc tổn hại file, dữ liệu lưu trên ổ đĩa Các bạn nên…

Lập trình với Dev-C++ phiên bản mới nhất [Setup + Portable]

Lập trình với Dev-C++ phiên bản mới nhất [Setup + Portable]

Dev-C++ là phần mềm cơ bản để học lập trình C, C++. Ngoài ra còn phần mềm khác có thể sử dụng là Turbo C (gọn nhẹ hơn Dev-C++), mặc dù tương đối “thân thuộc” với những người đã từng học Pascal (vì cùng họ…

Ảnh đen trắng có gì hấp dẫn nhiếp ảnh gia?

Ảnh đen trắng có gì hấp dẫn nhiếp ảnh gia?

Nhiếp ảnh trên thế giới ngày càng đi lên và phát triển mạnh. Khi nhiếp ảnh mới bắt đầu, mọi ảnh được ghi lại đều chỉ có hai mảng màu Đen Trắng. Cho đến lúc có ảnh màu, vẫn rất nhiều người chọn kiểu ảnh…

Bình luận ()