글 읽기 - 어디가 틀렸는지 모르겠습니다..

hazxz 8년 전 0

처음에 생각한건

DT[x][y][k] 라는 배열을 만듭니다. (x,y)에서 오른쪽 k칸까지 더해서 저장해두는 3차원 배열인데요.

N,M이 최대 300이니깐 300*300*300정도니깐 처음 init 해주고 문제를 풀면 될 것 같았습니다.

답을 출력할때는 i,j,x,y가 입력되면

i~x 까지 각각의 행에서 y-j+1 칸을 더한 값을 DT에서 빼와서 더하면 답이 하나 완성되는 형태로 해서 기본예제case는 맞았습니다.

왜 안되는지 답답해서 그냥 전체탐색법으로 solve2라는 함수를 만들어서 하니 통과하더군라고요.. 대신에 500ms ;;

문제에는 답의 배열의 합이 32bit-int를 벗어나지 않는다고 해서 처음엔 DT를 int 배열로 만들었는데 unsigned를 붙이니 4%인가 8%인가까지 답이 맞는거 같기도 하고..

알고리즘이 틀린건지..아니면 다른 문제가 있는건지 궁금합니다.

#include <stdio.h>

int N,M,K;
unsigned int DT[302][302][302];
int ki[10001], kj[10001], kx[10001], ky[10001], ans[10001];

void init() {
	for(int i=1; i<=300; i++) {
		for(int j=1; j<=300; j++) {
			for(int k=2; j+k<=300; k++) {
				DT[i][j][k] = DT[i][j][k-1]+DT[i][j+k-1][1];
			}
		}
	}
}
void solve() {
	for(int i=0; i<K; i++) {
		int step = ky[i]-kj[i]+1;
		for(int j=ki[i]; j<=kx[i]; j++) {
			ans[i] += DT[j][kj[i]][step];
		}
	}
}
void solve2() {
	for(int k=0; k<K; k++) {
		for(int i=ki[k]; i<=kx[k]; i++) {
			for(int j=kj[k]; j<=ky[k]; j++) {
				ans[k] += DT[i][j][1];
			}
		}
	}
}

int main() {


	scanf("%d %d", &N, &M);
	for(int i=1; i<=N; i++)
		for(int j=1; j<=M; j++)
			scanf("%d", &DT[i][j][1]);
	scanf("%d", &K);
	for(int i=0; i<K; i++)
		scanf("%d %d %d %d", &ki[i], &kj[i], &kx[i], &ky[i]);
	
	init();
	solve();
	//solve2();

	for(int i=0; i<K; i++) {
		printf("%d\n", ans[i]);
	}


	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다..

hazxz 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말