oj.uz

답안 #43378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43378 2018-03-15T08:23:07 Z milmillin Building Bridges (CEOI17_building) C++14
30 / 100
 209 ms 8740 KB 
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

long long h[100100];
long long w[100100];

struct line {
	long long m, c;
	double left;
	long long eval(long long x) const {
		return m * x + c;
	}
	
	double intersect(const line &r) const {
		return (double)(r.c - c) / (m - r.m);
	}
};

bool operator < (const line &a, const line &b) {
	if (a.m != b.m) return a.m < b.m;
	return a.c < b.c;
}

bool bad(const line &a, const line &b, const line &c) {
	return (c.c - a.c) * (a.m - b.m) < (b.c - a.c) * (a.m - c.m);
}

struct cleft {
	bool operator() (const line &a, const line &b) const {
		if (a.left!=b.left) return a.left < b.left;
		return a < b;
	}
};

set<line> sm;
set < line, cleft > sl;

bool hasLeft(set<line>::const_iterator it, set<line> &s) {
	return it != s.begin();
}

set<line>::const_iterator left(set<line>::const_iterator it) {
	auto tmp = it;
	tmp--;
	return tmp;
}

bool has2Left(set<line>::const_iterator it, set<line> &s) {
	if (!hasLeft(it, s)) return false;
	return hasLeft(left(it), s);
}

bool hasRgt(set<line>::const_iterator it, set<line> &s) {
	it++;
	return it != s.end();
}

set<line>::const_iterator rgt(set<line>::const_iterator it) {
	it++;
	return it;
}

bool has2Rgt(set<line>::const_iterator it, set<line> &s) {
	if (!hasRgt(it, s)) return false;
	return hasRgt(rgt(it), s);
}

void add(const line &x) {
	auto cur = sm.insert(x).first;
	while (has2Rgt(cur, sm)) {
		if (bad(*rgt(rgt(cur)), *rgt(cur), *cur)) {
			sl.erase(*rgt(cur));
			sm.erase(*rgt(cur));
		} else break;
	}
	while (has2Left(cur, sm)) {
		if (bad(*cur, *left(cur), *left(left(cur)))) {
			sl.erase(*left(cur));
			sm.erase(*left(cur));
		} else break;
	}
	if (hasLeft(cur, sm) && hasRgt(cur, sm)) {
		if (bad(*rgt(cur), *cur, *left(cur))) {
			line tmp = *left(cur);
			tmp.left = rgt(cur)->intersect(tmp);
			sl.erase(*left(cur));
			sm.erase(left(cur));
			sm.insert(tmp);
			sl.insert(tmp);
			sm.erase(cur);
			return;
		}
	}
	if (hasRgt(cur, sm)) {
		line tmp = *cur;
		tmp.left = rgt(cur)->intersect(tmp);
		sm.erase(cur);
		cur = sm.insert(tmp).first;
		sl.insert(tmp);
	}
	if (hasLeft(cur,sm)) {
		line tmp = *left(cur);
		tmp.left = cur->intersect(tmp);
		sl.erase(*left(cur));
		sm.erase(left(cur));
		sm.insert(tmp);
		sl.insert(tmp);
	}
	sl.insert(*cur);
}

int main () {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &h[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &w[i]);
		w[i] += w[i - 1];
	}
	add(line{ - 2 * h[1], h[1] * h[1] - w[1],-2e9});
	for (int i = 2; i <= n; i++) {
		auto tmp = sl.upper_bound(line{(long long)2e9, 0, (double)h[i]});
		//printf("yay\n");
		tmp--;
		//printf("%lld %lld\n", tmp->m, tmp->c);
		//for (auto &j : sl) {
			//printf("%lld,%lld,%f ", j.m, j.c, j.left);
		//}
		//printf("\n");
		long long dp = h[i] * h[i] + w[i - 1] + tmp->eval(h[i]);
		//printf("%lld\n", dp);	
		if (i == n) {
			printf("%lld\n", dp);
			return 0;
		}	
		add(line{ - 2 * h[i], dp - w[i] + h[i] * h[i], -2e9});
		//printf("add %lld %lld\n", -2 * h[i], dp - w[i] + h[i] * h[i]);
	}	
	return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:118:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
building.cpp:120:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &h[i]);
                       ^
building.cpp:123:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &w[i]);
                       ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Incorrect 1 ms 428 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 2112 KB Output is correct
2 Correct 209 ms 3368 KB Output is correct
3 Correct 192 ms 4504 KB Output is correct
4 Correct 182 ms 5416 KB Output is correct
5 Correct 142 ms 8740 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Incorrect 1 ms 428 KB Output isn't correct
4 Halted 0 ms 0 KB -