oj.uz

Submission #652811

# Submission time Handle Problem Language Result Execution time Memory
652811 2022-10-24T15:22:26 Z ymm Building Bridges (CEOI17_building) C++17
100 / 100
 1440 ms 4400 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 4192 KB Output is correct
2 Correct 1440 ms 4396 KB Output is correct
3 Correct 1347 ms 4148 KB Output is correct
4 Correct 1338 ms 4136 KB Output is correct
5 Correct 1364 ms 4200 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1363 ms 4192 KB Output is correct
7 Correct 1440 ms 4396 KB Output is correct
8 Correct 1347 ms 4148 KB Output is correct
9 Correct 1338 ms 4136 KB Output is correct
10 Correct 1364 ms 4200 KB Output is correct
11 Correct 1295 ms 4232 KB Output is correct
12 Correct 1362 ms 4304 KB Output is correct
13 Correct 1309 ms 4268 KB Output is correct
14 Correct 1280 ms 4228 KB Output is correct
15 Correct 1339 ms 4244 KB Output is correct
16 Correct 1307 ms 4400 KB Output is correct
17 Correct 1245 ms 4376 KB Output is correct
18 Correct 1290 ms 4232 KB Output is correct