11246: 【原1246】pyramid

题目描述

author: cheezer 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1246

Description

Jaguar 国王在一场战役大胜后决定建造一个金字塔，一方面作为纪念战争胜利的纪念碑，同时亦用作埋葬在战斗中阵亡将士们的墓地。该金字塔将建在战场的所在地，有一个a列b行的矩形底部。在金字塔的底层内将有一个较小的c列d行的矩形墓室，用来存放阵亡将士们的遗体以及他们所用过的武器。

Input Format

70%: 3 <= n, m <= 10;

80%: 3 <= n, m <= 100;

100%: 3<= n, m <= 1000; 3 <= a <= m, 3 <= b <= n; 1 <= c, d <= a - 2, b - 2; 1 <= h <= 100

Sample Input

``````8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2
``````

Sample Output

``````4 1
6 2
``````

zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1246.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m, a, b, c, d;
int sum[1005][1005] = {0};
int dt[1005][1005];
int res[1005][1005] = {0}, q[1005][2], hd, tl;
void init(){
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] = sum[i][j - 1] + read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] += sum[i - 1][j];
for (int i = d + 1; i < n; ++i){
hd = tl = 0;
for (int j = c + 1; j < m; ++j){
int tt = sum[i][j] - sum[i - d][j] - sum[i][j - c] + sum[i - d][j - c];
dt[i][j] = tt;
while (tl > hd && q[tl - 1][1] >= tt)
--tl;
q[tl][0] = j, q[tl++][1] = tt;
if (q[hd][0] <= j - (a - c - 1))
++hd;
res[i][j] = q[hd][1];
}
}
}
void solve(){
int ansx, ansy, ans = INT_MIN, ans_in;
/* for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j)
cout << res[i][j] << " ";
cout << endl;
} */
for (int j = c + 1; j < m; ++j){
hd = tl = 0;
for (int i = d + 1; i < n; ++i){
while (tl > hd && q[tl - 1][1] >= res[i][j])
--tl;
q[tl][0] = i, q[tl++][1] = res[i][j];
if (q[hd][0] <= i - (b - d - 1))
++hd;
if (i + 1 >= b && j + 1 >= a){
int sm = sum[i + 1][j + 1] - sum[i + 1 - b][j + 1] - sum[i + 1][j + 1 - a] + sum[i + 1 - b][j + 1 - a];
sm -= q[hd][1];
if (sm > ans) ans = sm, ansx = i + 1, ansy = j + 1, ans_in = q[hd][1];
}
}
}
ansx -= b - 1, ansy -= a - 1;
// cout << ansx << " " << ansy << " " << ans_in << endl;
for (int i = d; i < b - 1; ++i)
for (int j = c; j < a - 1; ++j){
if (ans_in == dt[i + ansx][j + ansy]){
printf("%d %d\n%d %d\n", ansy, ansx, ansy + j - c + 1, ansx + i - d + 1);
return ;
}
}
}
int main(){
init();
solve();
return 0;
}
``````