Submission #652811

#	Time	Username	Problem	Language	Result	Execution time	Memory
652811		ymm	Building Bridges (CEOI17_building)	C++17	100 / 100	1440 ms	4400 KiB

building

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#include <sys/mman.h>

const int N = 100'032;
double h[N], w[N];
double dp[N], suf_sum[N];
double dsw[N];
int n;

char find_min_base64[] = "SYnISGPHSGPOSDnID42eAgAAVUgpwUiJ18X7ENhIjVH/SYnDSInlU0iD+gIPhoMCAABIicvE4n0ZycTifRnAMdJIwesCSI00xQAAAABIweMFTI0UN0wBxkyNS+BJwekFSYPBAUGD4QcPhL8AAABJg/kBD4SVAAAASYP5AnR4SYP5A3RbSYP5BHQ+SYP5BXQhSYP5Bg+F9gEAAMTBfVwUEsXtWdLF7VgUFkiDwiDF9V3KxMF9XBQSxe1Z0sXtWBQWSIPCIMX1XcrEwX1cFBLF7VnSxe1YFBZIg8IgxfVdysTBfVwUEsXtWdLF7VgUFkiDwiDF9V3KxMF9XBQSxe1Z0sXtWBQWSIPCIMX1XcrEwX1cFBLF7VnSxe1YFBZIg8IgxfVdykg50w+E0QAAAMTBfVwUEkyNSiDF7VnSxe1YFBbF9V3KxMF9XFQSIMXtWdLF7VhUFiDF9V3KxMF9XFQSQMXtWdLF7VhUFkBJjZHgAAAAxfVdysSBfVxUCkDF7VnSxKFtWFQOQMX1XcrEgX1cVApgxe1Z0sShbVhUDmDF9V3KxIF9XJQKgAAAAMXtWdLEoW1YlA6AAAAAxfVdysSBfVyUCqAAAADF7VnSxKFtWJQOoAAAAMX1XcrEgX1clArAAAAAxe1Z0sShbViUDsAAAADF9V3KSDnTD4Uv////xON9GcgBSInKxfldyUiD4vxIAdDF8RXBxfldwUg5ynRhxfh3SCnRSIP5AXQ1TAHaxfsSy8X7EsDF8VwM18XxWcnEwXFYDNBIicpIg+L+SAHQxfFdyMXxFcHF+V3BSDnRdBPF41wMx8XzWcnEwXNYDMDF+13BSItd+MnDDx+AAAAAAMX4d0iLXfjJww8fgAAAAADEwX1cErogAAAAxe1Z0sXtWBbF9V3K6e/9//8PH0QAAMXzEMHDxfMQwTHS6WL///8";
int find_min_len = 704;
char *find_min;
double (*find_min_func)(int l, int r, double h,
                        double inf, double height[], double dsw[]);

inline int base64_decode_char(char c)
{
	if ('A' <= c && c <= 'Z')
		return c - 'A';
	if ('a' <= c && c <= 'z')
		return c - 'a' + 26;
	if ('0' <= c && c <= '9')
		return c - '0' + 52;
	if ('+' == c)
		return 62;
	if ('/' == c)
		return 63;
	return -1;
}

void base64_decode(char *dst, char *src, int len)
{
	int len64 = (len/3*4);
	for (int i = 0, j = 0; i < len64; i += 4, j += 3) {
		int x = 0;
		x ^= base64_decode_char(src[i+0]) << 18;
		x ^= base64_decode_char(src[i+1]) << 12;
		x ^= base64_decode_char(src[i+2]) << 6;
		x ^= base64_decode_char(src[i+3]) << 0;
		char *c = (char *)&x;
		dst[j+0] = c[2];
		dst[j+1] = c[1];
		dst[j+2] = c[0];
	}
	if (len%3) {
		int x = 0;
		x ^= base64_decode_char(src[len64+0]) << 18;
		x ^= base64_decode_char(src[len64+1]) << 12;
		if (len%3 == 2) x ^= base64_decode_char(src[len64+2]) << 6;
		char *c = (char *)&x;
		dst[len - len%3 + 0] = c[2];
		if (len%3 == 2) dst[len - len%3 + 1] = c[1];
	}
}

void prepare_find_min()
{
	find_min = (char *)mmap(NULL, find_min_len, PROT_WRITE | PROT_EXEC,
	                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	base64_decode(find_min, find_min_base64, find_min_len);
	find_min_func = (double (*)(int,int,double,double,double[],double[]))find_min;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		ll x;
		cin >> x;
		h[i] = x;
	}
	Loop (i,0,n) {
		ll x;
		cin >> x;
		w[i] = x;
	}
	suf_sum[n-1] = w[n-1];
	LoopR (i,0,n-1)
		suf_sum[i] = suf_sum[i+1] + w[i];
	dp[0] = 0;
	dsw[0] = dp[0] + suf_sum[0] - w[0];
	prepare_find_min();
	Loop (i,1,n) {
		dp[i] = find_min_func(0,i,h[i], 1e100,h,dsw) - suf_sum[i];
		dsw[i] = dp[i] + suf_sum[i] - w[i];
	}
	cout << (ll)dp[n-1] << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40