QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576073 | #2338. Beautiful Bridges | neonaht | WA | 0ms | 3744kb | C++17 | 2.7kb | 2024-09-19 18:15:33 | 2024-09-19 18:15:33 |
Judging History
answer
#include <bits/stdc++.h>
#define DEBUG 0
#define CASES 0
using namespace std;
const int SZ = 1e4 + 7;
const int MX = 1e9 + 7;
const long long MOD = 1e9 + 7;
const long long MXX = 1LL << 62LL;
long long X[SZ], Y[SZ], L[SZ], R[SZ], dp[SZ];
long long n, h, a, b;
bool check(int l, int r) {
return L[l] >= r && R[r] <= l;
}
bool inRange(int i, int lx, int rx, int mode) {
if(!mode) return lx <= X[i] && 2*X[i] <= rx + lx && 2*h - rx + lx <= 2*Y[i] && Y[i] <= h;
return rx + lx <= 2*X[i] && X[i] <= rx && 2*h - rx + lx <= 2*Y[i] && Y[i] <= h;
}
bool inCir(int i, int lx, int rx) {
long long x=X[i], y=Y[i];
return 4*x*x + 4*y*y - 4*x*(rx-lx) - 4*y*(2*h-rx+lx) + rx*rx + 2*rx*lx + lx*lx + 4*h*h -
4*h*(rx-lx) + rx*rx + 2*rx*lx + lx*lx <= rx*rx - 2*rx*lx + lx*lx;
// return (2*X[i]-lx-rx)*(2*X[i]-lx-rx) + (2*Y[i]-2*h+rx-lx)*(2*Y[i]-2*h+rx-lx) >= (rx-lx)*(rx-lx);
}
bool good(int l, int r, int mode) {
if(l >= r) return true;
long long lx = X[l], rx = X[r];
for(int i=l; i<=r; i++) {
if(inRange(i, lx, rx, mode) && !inCir(i, lx, rx)) {
return false;
}
}
return true;
}
void process(void) {
cin >> n >> h >> a >> b;
for(int i=1; i<=n; i++) cin >> X[i] >> Y[i];
for(int i=1; i<=n; i++) {
int l=i, r=n+1;
while(l < r) {
int mid = (l + r) >> 1;
if(good(i, mid, 0)) {
L[i] = mid;
l = mid + 1;
}
else r = mid;
}
}
for(int i=1; i<=n; i++) {
int l=1, r=i+1;
while(l < r) {
int mid = (l + r) >> 1;
if(good(i, mid, 1)) {
R[i] = mid;
r = mid;
}
else l = mid+1;
}
}
if(DEBUG) {
for(int i=1; i<=n; i++) cout << "L : (" << i << ", " << L[i] << ")" << '\n';
for(int i=1; i<=n; i++) cout << "R : (" << i << ", " << R[i] << ")" << '\n';
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
cout << good(i, j, 0) << ' ';
}
cout << '\n';
}
}
dp[1] = a*(h-Y[1]);
for(int r=2; r<=n; r++) {
dp[r] = MXX;
for(int l=r-1; l>=1; l--) {
if(check(l, r)) {
dp[r] = min(dp[r], dp[l] + a*(h-Y[r]) + b*(X[r]-X[l])*(X[r]-X[l]));
}
}
}
if(dp[n] == MXX) cout << "impossible";
else cout << dp[n];
return ;
}
int main() {
#ifndef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
cin.tie(nullptr)->ios::sync_with_stdio(false);
int t(1);
if(CASES) cin >> t;
while(t--) process();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
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: 0ms
memory: 3708kb
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: 3744kb
input:
2 1 1 1 0 0 2 0
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
2 1 1 1 0 0 3 0
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
4 5 100 1 0 0 1 3 9 3 10 0
output:
1100
result:
ok single line: '1100'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3736kb
input:
4 5 1 100 0 0 1 3 9 3 10 0
output:
8212
result:
wrong answer 1st lines differ - expected: '10010', found: '8212'