## 답안 #166604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166604 2019-12-03T02:49:49 Z thiago4532 Building Bridges (CEOI17_building) C++17
30 / 100
3000 ms 4920 KB
```#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], pref[maxn], w[maxn];
int n, dp[maxn];

struct line {
int a, b;

line(int a, int b): a(a), b(b) {

}

bool operator<(line const& l) const {
return a < l.a;
}
};

typedef set<line>::iterator sit;

set<line> lines;

bool hasPrev(sit it)
{
return (it != lines.begin());
}

bool hasNext(sit it)
{
return (next(it) != lines.end() && ++it != lines.end());
}

template<typename Arg>
bool bad(Arg&& l1, Arg&& l2, Arg&& l3) {
return (l2.a - l1.a)*(l3.b - l1.b) <= (l3.a -  l1.a)*(l2.b - l1.b);
}

auto it = lines.lower_bound(l);
if(it != lines.end() && it->a == l.a){
if(it->b <= l.b) return;
lines.erase(it);
}

lines.insert(l);
it = lines.find(l);

if (hasPrev(it) && hasNext(it) && bad(*prev(it), *it, *next(it))) {
lines.erase(it);
return;
}

while(hasNext(it) && hasNext(next(it)) && bad(*it, *next(it), *next(next(it))))
lines.erase(next(it));

while(hasPrev(it) && hasPrev(prev(it)) && bad(*prev(prev(it)), *prev(it), *it))
lines.erase(prev(it));
}

inline int f(line const& l, int x) {
return l.a*x + l.b;
}

int query(int x) {
int res=0x3f3f3f3f3f3f3f3f;
for(auto& e : lines) {
// cout << f(e, x) << " ";
res = min(res, f(e,x));
}
// cout << "\n";
return res;
}

int32_t main() {
cin >> n;
for(int i=1;i<=n;i++)
cin >> h[i];

for(int i=1;i<=n;i++)
cin >> w[i], pref[i] = pref[i-1] + w[i];

dp[1] = 0;
add({-2*h[1], h[1]*h[1] + dp[1] - pref[1]});

for(int i=2;i<=n;i++) {
// dp[i] = 0x3f3f3f3f3f3f3f3f;

// for(int j=1;j<i;j++) {
// 	dp[i] = min(dp[i], dp[j] - pref[j] + h[j]*h[j] - 2*h[j] * h[i]);
// }

dp[i] = query(h[i]);

dp[i] += h[i]*h[i] + pref[i-1];
add({-2*h[i], h[i]*h[i] + dp[i] - pref[i]});
}
cout << dp[n] << "\n";
return 0;
}```

#### Subtask #1 30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct

#### Subtask #2 0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 964 ms 3652 KB Output is correct
2 Correct 954 ms 4636 KB Output is correct
3 Correct 963 ms 4704 KB Output is correct
4 Correct 302 ms 4344 KB Output is correct
5 Execution timed out 3048 ms 4920 KB Time limit exceeded

#### Subtask #3 0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 964 ms 3652 KB Output is correct
7 Correct 954 ms 4636 KB Output is correct
8 Correct 963 ms 4704 KB Output is correct
9 Correct 302 ms 4344 KB Output is correct
10 Execution timed out 3048 ms 4920 KB Time limit exceeded