글 읽기 - 왜 맞는걸까요?

kimziou77 2년 전 0

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
12 초 (추가 시간 없음)	1024 MB	21935	5311	2987	22.504%

A+B 배열 -> E // C+D 배열 -> F

E와 F로 투포인터 알고리즘을 통해서 0인 정수쌍 갯수를 찾고 싶다는 생각을 했습니다. 그런데

int로 A,B,C,D 배열을 받고

A와 B배열이 각각 4000개씩이라면 여기서 나오는 (i,j) 조합이 16,000,000개

C와 D배열 또한 마찬가지로 16,000,000개가 나옵니다.

E,F배열은 2^32 + 2^32 값이 들어갈 수 있으므로 long long으로 만들어 주어야 할텐데

---

long long으로 16,000,000개의 원소를, 그것도 E,F 두개씩이나 만드는데

어째서 1024MB의 메모리가 초과가 안터지고 통과하는건가요?

16,000,000 * 8bytes -> 128,000,000 bytes -> 128,000 Mb 이렇게 계산하는게 아닌가요?

왜 메모리초과가 나오지 않을까요? ㅠㅠ 제가 메모리 계산법을 잘못 알고 있는건가요?

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;	cin >> N;
	vector<int> A(N), B(N), C(N), D(N);
	for (int i = 0; i < N; i++)
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	vector<ll> E, F;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			E.push_back((ll)A[i] + B[j]);
			F.push_back((ll)C[i] + D[j]);
		}
	}
	sort(E.begin(), E.end());
	sort(F.begin(), F.end());

	int L = 0, R = E.size()-1;
	ll cnt = 0;
	while (L < E.size() && R >= 0) {
		ll sum = E[L] + F[R];
		if (sum == 0) {
			ll lcnt = 0, rcnt = 0;
			ll q = E[L], w = F[R];
			while (L < E.size() && E[L] == q) L++, lcnt++;
			while (R >= 0 && F[R] == w) R--, rcnt++;
			cnt += lcnt * rcnt;
		}
		else if (sum > 0) {
			R--;
		}
		else if (sum < 0) {
			L++;
		}
	}

	cout << cnt;

	return 0;
}

djm03178 2년 전 1

바이트와 메가바이트 사이에는 킬로바이트라는 단위가 있습니다.

128,000,000 B ~= 128,000 KB ~= 128 MB

kimziou77 2년 전 0

ㅠㅠ.. ㅠㅠㅠㅠㅠ

답변 감사합니다.. 제가 너무 멍청했네요..

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

문제

문제

출처

ICPC

왜 맞는걸까요? - 메모리

kimziou77 2년 전 0

djm03178 2년 전 1

kimziou77 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말