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

Một số bài tập và hướng dẫn lập trình hệ thống Assembly (Phần 2)

Một số bài tập và hướng dẫn lập trình hệ thống Assembly (Phần 2)

Mình xin tiếp tục chia sẻ phần 2 vài bài tập lập trình hệ thống Assembly và code của nó. Chúc các bạn học tập tốt, nếu có thắc mắc các bạn có thể để lại bình luận để cùng mọi người trao đổi ^^…

[Java cơ bản] Bài 29: Import

[Java cơ bản] Bài 29: Import

Ngày hôm chúng ta bước vào bài 29, tìm hiểu từ khóa import trong Java. Hãy xem video và nếu có thắc mắc hãy để lại bình luận cho mình.

Hướng dẫn cài đặt Ubuntu 14.04 LTS

Hướng dẫn cài đặt Ubuntu 14.04 LTS

Video này sẽ hướng dẫn các bạn cài đặt Ubuntu một cách đơn giản và cụ thể nhất. Dành cho những bạn thích vọc cái mới, hehe… Nếu có gì thắc mắc hoặc khó hiểu, các bạn có thể để lại bình luận phía dưới…

[Java cơ bản] Bài 9: Các kiểu dữ liệu trong Java

[Java cơ bản] Bài 9: Các kiểu dữ liệu trong Java

Các kiểu dữ liêu cơ bản trong java gồm: byte: Dùng để lưu kiểu dữ liệu số nguyên có kích thước là 1byte (8 bit). Phạm vi biểu diễn từ -128 đến 127 giá trị mặc định là 0. char: Dùng để lưu kiểu dữ…

Bình luận ()