water.c

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>

uint64_t water_on_pillars(uint64_t pillars[], size_t len) {

	if (len < 3) {
		return 0;
	}

	size_t tallest_pos = 0;

	{
		uint64_t tallest = pillars[0];

		for (uint64_t i = 1; i < len; i++) {
			if (pillars[i] > tallest){
				tallest = pillars[i];
				tallest_pos = i;
			}
		}
	}

	uint64_t water = 0;
	
	{
		size_t tallest_from_left = pillars[0];

		for (uint64_t i = 1; i < tallest_pos; i++) {
			if (pillars[i] < tallest_from_left) {
				water += tallest_from_left - pillars[i];
			} else {
				tallest_from_left = pillars[i];
			}
		}
	}

	{
		size_t tallest_from_right = pillars[len - 1];

		for (uint64_t i = len-2; i > tallest_pos; i--) {
			if (pillars[i] < tallest_from_right) {
				water += tallest_from_right - pillars[i];
			} else {
				tallest_from_right = pillars[i];
			}
		}
	}

	return water;
}

int main () {
	size_t n;
	scanf("%u", &n);

	uint64_t *heights = malloc(n*sizeof(uint64_t));

	for (size_t i = 0; i < n; i++) {
		scanf("%d", &heights[i]);
	}

	clock_t before = clock();
	printf("%d\n", water_on_pillars(heights, n));
	clock_t after = clock();

	printf("%dms\n", (after-before) * 1000 / CLOCKS_PER_SEC);

	return 0;
}