https://www.acmicpc.net/problem/2143


요문제인데


맵 써서

A배열의 부 배열의 합 결과를 맵A에 저장하고

B배열의 부 배열으 합 결과를 맵B에 저장해서


맵 A원소 기준으로 T를 만들수 있는 수가 맵B에 있으면 서로 개수 곱해서 답을 누적 시키는 방법으로 풀었는데


72퍼 정도에서 틀렸다고 뜨는데


반례가 무엇인지 찾아주시면 ㄳ 하겠습니다.


로직 자체가 틀렸으면 72퍼까지도 안갔을꺼 같은데


무었이 문제일까요



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <map>
#define ll long long 
using namespace std;
int A[1001];
int B[1001];
map<ll, int>Asum;
map<ll, int>Bsum;
int T, N, M;
 
void makeSum(map<ll,int> &tmp,int* arr,int n) {
    for (register int i = 1; i <= n; i++) {
        int sum = arr[i];
        auto it = tmp.find(sum);
        if (it == tmp.end()) tmp.insert({ sum,1 });
        else it->second++;
        for (register int j = i + 1; j <= n; j++) {
            sum += arr[j];
            auto it = tmp.find(sum);
            if (it == tmp.end()) tmp.insert({ sum,1 });
            else it->second++;
        }
    }
}
 
inline void init() {
    cin >> T;
    cin >> N;
    for (register int i = 1; i <= N; i++)
        cin >> A[i];
 
    cin >> M;
    for (register int i = 1; i <= M; i++)
        cin >> B[i];
 
    makeSum(Asum, A, N);
    makeSum(Bsum, B, M);
 
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    ll ans = 0;
    for (auto m : Asum) {
        auto it = Bsum.find(T - m.first);
        if (it == Bsum.end()) continue;
        ans += (m.second * it->second);
    }
    cout << ans;
    return 0;
}
 
cs