Boj2632_피자판매

Published: by Creative Commons Licence

  • algorithm 헤더의 equal_range를 이용하여 문제 해결!
    • equal_range : lower_bound() 와 upper_bound() 결과를 쌍으로 던져준다.
  • 간단한 정렬로 문제 해결!
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m, want, num;
long long ans;
vector<int> v1, v2,p1,p2;

void input(int n, vector<int> &v) {
	for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		v.push_back(num);
	}
	for (int i = 0; i < n; i++) v.push_back(v[i]);
}

void getPiece(int n, vector<int> &v,vector<int> &p){
	p.push_back(0);
	for (int i = 0; i < n; i++) {
		int  before = 0;
		for (int j = 0; j < n; j++) {
			if (i != 0 && j == n - 1) break;
			p.push_back(before + v[i + j]);
			before += v[i + j];
		}
	}
}

int main() {
	scanf("%d %d %d",&want,&n,&m);
	input(n, v1);
	input(m, v2);
	getPiece(n, v1,p1);
	getPiece(m, v2,p2);
	sort(p1.begin(), p1.end());
	sort(p2.begin(), p2.end());
	for (int i = 0; i < p1.size(); i++) {
		auto iter = equal_range(p2.begin(), p2.end(), want - p1[i]);
		ans += (long long)(iter.second - iter.first);
	}
	printf("%lld", ans);
}