Submission #636572

#	Time	Username	Problem	Language	Result	Execution time	Memory
636572		rainboy	Sightseeing in Kyoto (JOI22_kyoto)	C11	100 / 100	33 ms	3124 KiB

kyoto

#include <stdio.h>

#define N	100000
#define M	100000
#define INF	0x3f3f3f3f3f3f3f3f

long long cross2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
	return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

int main() {
	static int aa[N], bb[M], ii[N], jj[M];
	int n, m, i, j, cnt;
	long long ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (j = 0; j < m; j++)
		scanf("%d", &bb[j]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt >= 2 && cross(ii[cnt - 2], aa[ii[cnt - 2]], ii[cnt - 1], aa[ii[cnt - 1]], i, aa[i]) <= 0)
			cnt--;
		ii[cnt++] = i;
	}
	n = cnt;
	cnt = 0;
	for (j = 0; j < m; j++) {
		while (cnt >= 2 && cross(jj[cnt - 2], bb[jj[cnt - 2]], jj[cnt - 1], bb[jj[cnt - 1]], j, bb[j]) <= 0)
			cnt--;
		jj[cnt++] = j;
	}
	m = cnt;
	i = 0, j = 0, ans = 0;
	while (i + 1 < n || j + 1 < m)
		if (j + 1 == m || i + 1 < n && cross2(ii[i + 1] - ii[i], aa[ii[i + 1]] - aa[ii[i]], jj[j + 1] - jj[j], bb[jj[j + 1]] - bb[jj[j]]) >= 0)
			ans += (long long) bb[jj[j]] * (ii[i + 1] - ii[i]), i++;
		else
			ans += (long long) aa[ii[i]] * (jj[j + 1] - jj[j]), j++;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

kyoto.c: In function 'main':
kyoto.c:41:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |   if (j + 1 == m || i + 1 < n && cross2(ii[i + 1] - ii[i], aa[ii[i + 1]] - aa[ii[i]], jj[j + 1] - jj[j], bb[jj[j + 1]] - bb[jj[j]]) >= 0)
      |                     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kyoto.c:20:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
kyoto.c:22:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
kyoto.c:24:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d", &bb[j]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60