글 읽기 - 문제 접근법이 잘못됬는지 메모리 초과가 납니다 ㅜㅜ

unilep 6년 전 0

sa배열에는 첫번째 배열(a) 에서

연속부분합 들이 저장되어있고

sb배열에는 두번째 배열의

연속부분합 들이 저장되어 있습니다.

a) 1, 3, 1, 2

sa) 1, 4(1+3), 5(1+3+1), 7(1+3+1+2), 3, 4(3+1), 6(3+1+2), 1, 3(1+2, 2

이런식으로요..

sa와 sb를 sort한 뒤

sa는 작은거부터 sb는 큰거부터

합을 구하여 구하고자 하는 값이랑 일치할 경우 그 숫자들의 갯수 를 세는 방식으로 구현했습니다..

72퍼에서 틀리길래 범위문제인줄 알고 배열을

long long 으로 바꿨지만 아예 메모리초과가 나버리네요.

접근법 자체가 잘못된 것일까요? ...

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int T, N, M, ta, tb, a[1001], b[1001];
ll sa[2000001], sb[2000001], l, r, sum, ans;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;

	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	for (int i = 0; i < N; i++) {
		sa[ta++] = sum = a[i];
		for (int j = i+1; j < N; j++) {
			sum += a[j];
			sa[ta++] = sum;
		}
	}
	sort(sa, sa + ta);
	
	cin >> M;
	for (int i = 0; i < M; i++) cin >> b[i];
	for (int i = 0; i < M; i++) {
		sb[tb++] = sum = b[i];
		for (int j = i + 1; j < M; j++) {
			sum += b[j];
			sb[tb++] = sum;
		}
	}
	sort(sb, sb + tb);

	l = 0;
	r = tb - 1;

	while (l < ta && r >= 0) {
		int m = sa[l] + sb[r];
		if (m == T) {
			int atmp = sa[l];
			int btmp = sb[r];
			int acnt = 0;
			int bcnt = 0;
			while (sa[l] == atmp) {
				l++;
				acnt++;
			}
			while (sb[r] == btmp) {
				r--;
				bcnt++;
			}
			ans += acnt*bcnt;
		}
		else if (m > T) r--;
		else l++;
	}
	cout << ans;
}

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

문제

문제

출처

ICPC

문제 접근법이 잘못됬는지 메모리 초과가 납니다 ㅜㅜ

unilep 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말