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

Proteus 8.0 – Phần mềm giả lập mô phỏng và lập trình vi điều khiển

Proteus 8.0 – Phần mềm giả lập mô phỏng và lập trình vi điều khiển

Đã là dân CNTT, điện tử, chắc hiếm bạn nào không biết đến chương trình mô phỏng mạch điện tử nổi tiếng Proteus 8. Đây là chương trình thiết kế mạch nguyên lý, mô phỏng chạy thử, thiết kế mạch in rất trực quan và…

Cách dùng Desktop ảo trong Windows 10

Cách dùng Desktop ảo trong Windows 10

Desktop ảo (Virtual Desktop) đã được Microsoft tích hợp vào Windows 10. Tính năng này cho phép người dùng mở nhiều chương trình một lúc, thuộc nhiều desktop khác nhau để quản lý chúng tốt hơn, thay vì để lộn xộn trên một desktop như…

[Java cơ bản] Bài 3: Giới thiệu, cài đặt NetBeans và Eclipse

[Java cơ bản] Bài 3: Giới thiệu, cài đặt NetBeans và Eclipse

Video này sẽ hướng dẫn các bạn cách cài đặt NetBeans, Eclipse… sau đó giới thiệu những chức năng cơ bản của 2 ứng dụng này! Chúc các bạn học tập vui vẻ!

Những lập trình viên nổi tiếng nhất đương đại là ai?

Những lập trình viên nổi tiếng nhất đương đại là ai?

Những ứng dụng, trò chơi mà bạn dùng hàng ngày đều được viết bởi những lập trình viên. Những nền tảng hệ điều hành, hệ thống phần cứng, các trang web hay toàn bộ thế giới Internet cũng là công sức nghiên cứu trong thời…

Bình luận ()