MATRIX

As we all know, we live inside the matrix that is divided into N rows and N columns. An integer is
written into each one of the NxN cells of the matrix. In order to leave the matrix, we must find the
most beautiful square (square-shaped sub-matrix) contained in the matrix.
If we denote by A the sum of all integers on the main diagonal of some square, and by B the sum of
the other diagonal, then the beauty of that square is A - B.
Note: The main diagonal of a square is the diagonal that runs from the top left corner to the bottom
right corner.
INPUT
The first line of input contains the positive integer N (2 ≤ N ≤ 400), the size of the matrix.
The following N lines each contain N integers in the range [-1000, 1000], the elements of the matrix.
OUTPUT
The only line of output must contain the maximum beauty of a square found in the matrix.

SAMPLE TESTS
input

2
1 -2
4 5

output

4
input

3
1 2 3
4 5 6
7 8 9

output

0
input

3
-3 4 5
7 9 -2
1 0 -6

output

5

Solution:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int N;
int a[401][401];
int res = -8000000;

int main()
{
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);

scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
scanf("%d",&a[i][j]);
// res = max(res,a[i][j]);
}
int ii,jj;
int dd;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
for(int d=2;d<=N;d++)
{
if(i+d-1>N || j+d-1 >N) continue;
int temp = 0;
ii = i;
jj = j;
dd =  1;
while(dd<=d)
{
temp += a[ii][jj];
ii++;
jj++;
dd++;
}

ii = i;
jj = j-1+d;
dd = 1;
int temp_ = 0;
while(dd<=d)
{
temp_ += a[ii][jj];
ii++;
jj--;
dd++;
}
res = max(res,temp-temp_);
}
}
cout << res;
return 0;
}

Độ phức tạp. O(N^3). Có thể làm thành O(N^2) nếu sử dụng kỹ thuật PreCompute.

Constest 1 COCI 2011-2012

Đề bài JABUKE:

Mirko has recently discovered an old video game. The screen of this game is divided into N columns.
At the bottom of the screen, there is an M-columns-wide boat (M < N). The player can move this boat
left or right during the game, but the boat must remain completely within the screen at all times. The
boat initially occupies the leftmost M columns.
Apples are being dropped from the top of the screen. Each apple starts its fall at the top of one of the
N columns, falling straight down until it reaches the bottom of the screen. The next apple starts its fall
just after the current one has reached the bottom.
An apple is said to be picked up if the boat is placed so that it occupies the column down which the
apple is falling when it reaches the bottom. The goal of the game is to pick up all of the apples, in a way
that minimizes the distance that the boat must travel.

INPUT
The first line of input contains two space separated integers N and M (1 ≤ M < N ≤ 10).
The second line of input contains an integer J (1 ≤ J ≤ 20), the number of falling apples.
The following J lines contain the column positions of those apples, in the order in which they will fall.
OUTPUT
The only line of output must contain the minimal distance that the boat must travel in order to pick up
all the apples.
SAMPLE TESTS
input
5 1
3
1
5
3
output 
6

input
5 2
3
1
5
3
output
4

Solution here:

#include<iostream>
using namespace std;

int N,J;
int l,r;
int x;
int res = 0;

int main()
{
freopen("TEST.INP","r",stdin);
freopen("TEST.OUT","w",stdout);
cin >> N >> r;
l=1;
cin >> J;
//cout << "l = "<< l << ", r = " << r << endl;
for(int i=0;i<J;i++)
{
cin >> x;

if(x>=l && x<=r) continue;

if(x>r)
{
res += x-r;
l = l + (x-r);
r = x;

}
else
{
res += l-x;
r = r - (l-x);
l = x;
}
//cout << "l = " << l << ", r = " << r << endl;
}
cout << res;
return 0;
}