1 번째 시도
- 연속된 피자 조각을 판매해야 하므로 연속된 부분 수열의 부분합을 이용한다.
- 부분합을 구할 때 피자가 원형이기 때문에 MOD를 이용하여 i부터 N + i - 2까지 input을 더해가면서 부분합을 map에 저장 및 카운트한다.
- N + i - 1 까지 더하면 input을 모두 더한 경우를 여러 번 구하게 된다.
- input을 하나도 더하지 않은 경우와 input을 모두 더한 경우를 따로 추가한다.
- bMap을 vec로 복사한다.
- aMap을 순회하면서 bMap을 binary search로 탐색한다. => $O(N^2logN^2)$
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <functional>
#include <string>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define MAX_N 1010
#define ll long long
int S, N, M;
int a[MAX_N], b[MAX_N];
int aTotal, bTotal;
map<int, int> aMap, bMap;
vector<int> bVec;
int bsearch(int subSum) {
int left = 0;
int right = bVec.size()-1;
while (left <= right) {
int mid = (left + right) / 2;
int sum = bVec[mid] + subSum;
if (sum == S)
return bMap[bVec[mid]];
else if (sum < S)
left = mid + 1;
else
right = mid - 1;
}
return 0;
}
ll solution() {
aMap[0]++; aMap[aTotal]++;
for (int i = 0; i < N; i++) {
for (int j = i, sum = 0; j < N + i - 1; j++) {
sum += a[j%N];
aMap[sum]++;
}
}
bMap[0]++; bMap[bTotal]++;
for (int i = 0; i < M; i++) {
for (int j = i, sum = 0; j < M + i - 1; j++) {
sum += b[j%M];
bMap[sum]++;
}
}
map<int, int>::iterator it;
for (it = bMap.begin(); it != bMap.end(); it++)
bVec.push_back(it->first);
sort(bVec.begin(), bVec.end());
ll res = 0;
for (it = aMap.begin(); it != aMap.end(); it++) {
int sum = it->first;
int cnt = it->second;
res += (ll)cnt * bsearch(sum);
}
return res;
}
int main() {
scanf("%d", &S);
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%d", &a[i]);
aTotal += a[i];
}
for (int i = 0; i < M; i++) {
scanf("%d", &b[i]);
bTotal += b[i];
}
printf("%lld\n", solution());
}
|