[UVA][dp] 11951 - Area
A — Area
Time Limit: 1 sec
Memory Limit: 32 MB
Steve has a dream to move from dormitory where we live now to a private house. He has already earned some money by solving various problems and now wants to make a first move towards his dream. Steve is going to buy a plot for his future house. However, due to high tax rate, he is going to buy only one plot. Certainly Steve wants to maximize its area for the amount of money he owns (and if there are several plots of same area, Steve certainly chooses a cheaper one). Can you help Steve?
The whole district where Steve wants to reside is divided into N * M equal strips. Each strip is sold separately, for its own price Pi;j. According to the country law, plot is defined as a rectangular collection of strips with sides parallel to the district.
INPUT
There is a number of tests T (T ≤ 110) on the first line. After T tests follows. Each test case is defined by three numbers N M K (N; M ≤ 100; K ≤ 109). Next N lines with M numbers each stands for prices of the strips Pi;j (Pi;j ≤ 106).
OUTPUT
For each test print a line formatted as "Case #T: S P", where T stands for test case number
(starting from 1), S for maximal plot area that Steve can afford and P for plot’s total cost.
SAMPLE INPUT
1 5 6 15 10 1 10 20 10 10 30 1 1 5 1 1 50 1 1 20 1 1 10 5 5 10 5 1 40 10 90 1 10 10
SAMPLE OUTPUT
Case #1: 6 10
Problem by: Aleksej Viktorchik; Leonid Sislo
Huge Easy Contest #2
O(n^3)
#include <stdio.h>
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
int main() {
int t, N, M, K;
int g[105][105];
int cases = 0;
int i, j, k, l;
//scanf("%d", &t);
ReadInt(&t);
while(t--) {
//scanf("%d %d %d", &N, &M, &K);
ReadInt(&N);
ReadInt(&M);
ReadInt(&K);
for(i = 0; i < N; i++)
for(j = 0; j < M; j++)
//scanf("%d", &g[i][j]);
ReadInt(&g[i][j]);
int mx = 0, mxv = 0;
long long tmp;
int cnt = 0;
for(i = 0; i < N; i++) {
int sum[105] = {};
for(j = i; j < N; j++) {
for(k = 0, l = 0; k < M; k++) {
sum[k] += g[j][k];
if(k == 0) tmp = 0;
tmp += sum[k];
while(tmp > K)
tmp -= sum[l++];
if((j-i+1)*(k-l+1) > mx)
mx = (j-i+1)*(k-l+1), mxv = K;
if((j-i+1)*(k-l+1) == mx && tmp < mxv)
mxv = tmp;
}
}
}
printf("Case #%d: %d %d\n", ++cases, mx, mxv);
}
return 0;
}