oj.uz

Submission #652802

# Submission time Handle Problem Language Result Execution time Memory
652802 2022-10-24T15:03:55 Z ymm Building Bridges (CEOI17_building) C++17
100 / 100
 1639 ms 5596 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,
	                        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	base64_decode(find_min, find_min_base64, find_min_len);
	mprotect(find_min, find_min_len, PROT_EXEC);
	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 1485 ms 5280 KB Output is correct
2 Correct 1509 ms 5144 KB Output is correct
3 Correct 1534 ms 5356 KB Output is correct
4 Correct 1472 ms 5332 KB Output is correct
5 Correct 1496 ms 5132 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 1485 ms 5280 KB Output is correct
7 Correct 1509 ms 5144 KB Output is correct
8 Correct 1534 ms 5356 KB Output is correct
9 Correct 1472 ms 5332 KB Output is correct
10 Correct 1496 ms 5132 KB Output is correct
11 Correct 1468 ms 5596 KB Output is correct
12 Correct 1586 ms 5240 KB Output is correct
13 Correct 1497 ms 5508 KB Output is correct
14 Correct 1628 ms 5408 KB Output is correct
15 Correct 1543 ms 5160 KB Output is correct
16 Correct 1639 ms 5064 KB Output is correct
17 Correct 1476 ms 5332 KB Output is correct
18 Correct 1468 ms 5368 KB Output is correct