QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104623 | #2338. Beautiful Bridges | _skb_ | WA | 2ms | 3720kb | C++17 | 2.7kb | 2023-05-11 13:28:32 | 2023-05-11 13:28:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
#define contPrint { *this << "["; \
int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
*this << "]"; return *this;}
~debug(){cerr << endl;}
template<class c> debug& operator<<(c x) {cerr << x; return *this;}
template<class c, class d>
debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")";
return *this;}
template<class c> debug& operator<<(vector<c> x) contPrint;
#undef contPrint
};
#define dbg(x) "[" << #x << ": " << x << "] "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() <<
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
const i64 INF = 1e18;
int main()
{
int n, h, a, b;
scanf("%d %d %d %d", &n, &h, &a, &b);
vector<int> x(n);
vector<int> y(n);
for(int i = 0; i < n; i++) {
scanf("%d %d", &x[i], &y[i]);
}
auto sqr = [] (i64 i) {
return i * i;
};
auto check = [&] (int l, int r, int m) {
int d = abs(x[r] - x[l]);
if(2 * (h - y[l]) < d || 2 * (h - y[r]) < d) {
return -1;
}
if(abs(x[r] - x[m]) * 2 > d) {
return 2;
}
if((sqr(2 * x[m] - d) + sqr(2 * y[m] - d) > sqr(d)) && (2 * y[m] > 2 * h - d)) {
return -2;
}
return 1;
};
bool l_ok[n][n];
memset(l_ok, 0, sizeof l_ok);
for(int i = 1; i < n; i++) {
int l = 0;
int m = i + 1;
while((x[i] - x[l]) > 2 * (h - y[i])) l++;
for( ; l < i; l++) {
while(check(l, i, m - 1) == 1) {
m--;
}
if(check(l, i, m - 1) == 2) {
l_ok[i][l] = 1;
}
}
}
bool r_ok[n][n];
memset(r_ok, 0, sizeof r_ok);
for(int i = n-2; i >= 0; i--) {
int r = n - 1;
int m = i - 1;
while((x[r] - x[i] > 2 * (h - y[i]))) r--;
for( ; r > i; r--) {
while(check(i, r, m + 1) == 1) {
m++;
}
if(check(i, r, m + 1) == 2) {
r_ok[i][r] = 1;
}
}
}
vector<i64> dp(n, INF);
dp[0] = a * (h - y[0]);
for(int r = 1; r < n; r++) {
for(int l = 0; l < r; l++) {
if(l_ok[r][l] && r_ok[l][r]) {
if(dp[l] != INF) {
dp[r] = min(dp[r], dp[l] + 1LL * a * (h - y[r]) + 1LL * b * sqr(x[r] - x[l]));
}
}
}
}
if(dp[n-1] == INF) puts("impossible");
else printf("%lld\n", dp[n-1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3628kb
input:
5 60 18 2 0 0 20 20 30 10 50 30 70 20
output:
6460
result:
ok single line: '6460'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
4 10 1 1 0 0 1 9 9 9 10 0
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
2 1 1 1 0 0 2 0
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
2 1 1 1 0 0 3 0
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
4 5 100 1 0 0 1 3 9 3 10 0
output:
1100
result:
ok single line: '1100'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
4 5 1 100 0 0 1 3 9 3 10 0
output:
10010
result:
ok single line: '10010'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
2 100000 10000 10000 0 0 100000 0
output:
100002000000000
result:
ok single line: '100002000000000'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
13 43 1 5 3 26 4 25 10 23 11 0 23 2 49 20 64 2 68 0 83 24 84 17 91 33 92 6 97 33
output:
7348
result:
ok single line: '7348'
Test #9:
score: -100
Wrong Answer
time: 2ms
memory: 3660kb
input:
12 29 5 1 4 26 5 18 15 15 27 26 31 12 40 0 46 19 67 4 68 2 77 1 83 12 89 10
output:
2337
result:
wrong answer 1st lines differ - expected: '2134', found: '2337'