글 읽기 - 시간초과질문드립니다.

hsu2016 5년 전 0

printf와 scanf를 사용했는데도 시간이 단축되지 않습니다. 도와주세요

#include <iostream>
using namespace std;
int main() {
	int n, m, how, r1, c1, r2, c2, **ptr;
	
	cin >> n >> m >> how;
	ptr = new int *[n];
	for (int i = 0; i < n; i++) {
		ptr[i] = new int[m];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &ptr[i][j]);
		}
	}
	while (how--) {
		int sum = 0;
		int count = 0;

		cin >> r1 >> c1 >> r2 >> c2;
		for (int i = r1 - 1; i <= r2 - 1; i++) {
			for (int j = c1 - 1; j <= c2 - 1; j++) {
				sum = ptr[i][j] + sum;
				count++;
			}
		}
		printf("%d\n", sum / count);
	}
}

gaelim 5년 전 1

만약 사진 크기가 1000* 1000 이 되고, 쿼리 갯수 Q가 가장 큰수인 10,000 이 되고, r1, c1, r2, c2 가 사진 최 좌상단 부터 최우측 하단까지 가게된다면, 위 소스로는 1000* 1000 * 10000 번을 연산하게 됩니다. 10억번 연산하게 되는 셈이니 제한시간이 초과하게되어요.

그래서 쿼리를 어떻게 효율적으로 처리할 수 있을까 고민을 하셔야합니다.

한번 prefix sum에 대해서 검색해보세요.

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

문제

문제

출처

ICPC

시간초과질문드립니다.

hsu2016 5년 전 0

gaelim 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말