글 읽기 - 시간 초과가 나오는데 ㅠㅠ

ckdtjs505 5년 전 0

안녕하세요 시간초과가 나오는데

동적계획법으로 잘풀었습니다.'결과값도 맘에들게 나옵니다.

그런데 제출하면 시간초과로 문제가 나옵니다.

왜 시간초과가 나오는 이유을 알려주세요

어떻게 하면 시간초과를 해결 할 수 있는지 지도해주시면

더욱 감사하겠습니다 ㅠㅠ

#include <iostream>
#define   MAX  1025
using namespace std;
int main (){
	int n, m, t;
	int d[MAX][MAX] = {0}; 
	int ary[MAX][MAX]; 
	scanf("%d %d", &n ,&m);
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <=m ; j++){
			scanf("%d", &ary[i][j]);
		}
	}
	scanf("%d",&t) ;
	while(t--){
		int i, j, x, y;
		scanf("%d %d %d %d",&i, &j,&x,&y);		
		for(int k = i; k <= x ; k++){		
			for(int u = j; u <=y ; u++){
				d[k][u] = d[k][u-1]+d[k-1][u]-d[k-1][u-1]+ary[k][u];
			}
		}
		printf("%d\n",d[x][y]);
	}
}

jh05013 5년 전 1

시간복잡도를 계산해 보세요. DP를 계산하는 부분이 저기에 들어 있으면 안 됩니다.

ckdtjs505 5년 전 0

선생님이 지도해주신데로 시간초과 문제는 해결했습니다.

실례가 안된다면. 반례를 하나만이라도 받을 수 있을까요?

#include <iostream>
#define   MAX  1025

using namespace std;
int main (){
	ios_base::sync_with_stdio(false); 
	int n, m, t;
	long long int d[MAX][MAX] = {0}; 
	long long int ary[MAX][MAX]; 
	cin.tie(NULL);
	cin>> n >> m;
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <=m ; j++){
			cin >> ary[i][j];
			d[i][j] = d[i][j-1]+d[i-1][j]-d[i-1][j-1]+ary[i][j];
		}
	}
	cin >> t;
	while(t--){
		int i, j, x, y;
		cin >> i >> j >> x >> y;	
		cout << d[x][y] -d[i][j] +ary[i][j] <<'\n';
	}
}

ckdtjs505 5년 전 0

제발 지나치지 마시고 한번만 봐주세요 ~~ ㅠㅠㅠ

jh05013 5년 전 1

전 24시간 내내 접속해 있는 사람이 아닙니다...

예제 말고 다른 입력을 직접 만들어서 넣어 보세요. 거의 무조건 반례가 나옵니다.

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

문제

문제

출처

ICPC

시간 초과가 나오는데 ㅠㅠ

ckdtjs505 5년 전 0

jh05013 5년 전 1

ckdtjs505 5년 전 0

ckdtjs505 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말