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

Kinh nghiệm nâng cao kỹ năng lập trình

Kinh nghiệm nâng cao kỹ năng lập trình

0. Bắt đầu Để trở thành một lập trình viên tốt hơn, bạn cần biết rất là nhiều thứ như: thuật toán, cấu trúc dữ liệu, lập trình hướng đối tượng, testing … Lập trình bao gồm rất nhiều kỹ năng, có nghĩa là không…

6 thủ thuật chụp ảnh đen trắng cổ điển nhờ ánh sáng tự nhiên

6 thủ thuật chụp ảnh đen trắng cổ điển nhờ ánh sáng tự nhiên

Chụp ảnh chân dung đen trắng theo phong cách cổ điển không chỉ đơn giản là ngắm và chụp. Bức ảnh cần có chiều sâu, có hình khối và phản ánh tốt tâm trạng nhân vật. Chụp bằng ánh sáng tự nhiên lại càng khó….

Những website viết code trực tuyến cho dân lập trình

Những website viết code trực tuyến cho dân lập trình

Ngoài cách viết code bằng các phần mềm soạn thảo thông thường, bạn có thể sử dụng các công cụ trực tuyến. Lúc đó, bạn sẽ dễ dàng có thể chia sẻ code cho bạn bè mình thông qua các URL. Jsbin.com JS Bin là…

[Java cơ bản] Bài 38: Enum (Phần 2)

[Java cơ bản] Bài 38: Enum (Phần 2)

Hôm nay sẽ nói về Enum phần 2, nó cũng đóng phần khá quan trọng trong lập trình Java, chúc các bạn thành công.

Bình luận ()