fork download
copy 
  1. #include<stdio.h>
  2. #include<set>
  3. #include<algorithm>
  4. using namespace std;
  5. struct xy { long long g, type, w; }G[52252];
  6. bool sort_g(xy a, xy b) {return a.g > b.g;}
  7. int a[25252], b[25252];
  8. set<int>L[2], R[2];
  9. long long cnt[2], ln;
  10. int main() {
  11. 	int i, j;
  12. 	long long A, B, n, m;
  13. 	scanf("%lld%lld%lld%lld", &A, &B, &n, &m);
  14. 	long long ans = B*n + A*m;
  15. 	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
  16. 	for (i = 1; i <= m; i++)scanf("%d", &b[i]);
  17. 	sort(a + 1, a + n + 1), sort(b + 1, b + m + 1);
  18. 	a[n + 1] = A, b[m + 1] = B;
  19. 	cnt[0] = m, cnt[1] = n;
  20. 	for (i = 0; i < n + 1; i++)G[ln++] = { a[i + 1] - a[i],0,i };
  21. 	for (i = 0; i < m + 1; i++)G[ln++] = { b[i + 1] - b[i],1,i };
  22. 	sort(G, G + ln, sort_g);
  23. 	long long ccnt = 0;
  24. 	for (i = 0; i < ln; i++) {
  25. 		long long g = G[i].g, type = G[i].type, w = G[i].w;
  26. 		bool fa = L[type].find(i + 1) != L[type].end();
  27. 		bool fb = R[type].find(i) != R[type].end();
  28. 		if (fa&&fb)L[type].erase(i + 1), R[type].erase(i);
  29. 		else if (fa)L[type].erase(i + 1), L[type].insert(i),cnt[!type]--;
  30. 		else if (fb)R[type].erase(i), R[type].insert(i + 1), cnt[!type]--;
  31. 		else L[type].insert(i), R[type].insert(i + 1), cnt[!type]--;
  32. 		ans -= g*cnt[type];
  33. 		ccnt += cnt[type];
  34. 		if (ccnt == n*m)break;
  35. 	}
  36. 	printf("%lld", ans);
  37. 	return 0;
  38. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
15 15 5 2
2
5
10
6
4
11
3
stdout
copy 
44
https://ideone.com/uTofec
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!