QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178293 | #2338. Beautiful Bridges | PetroTarnavskyi# | WA | 0ms | 3712kb | C++17 | 1.7kb | 2023-09-13 20:45:00 | 2023-09-13 20:45:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, b, a) for (int i = (b) - 1; i >= (a); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef unsigned long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
#define beta fkldjgkldfjg
const int N = 10'047;
const db EPS = 1e-9;
const LL LINF = 1.1e18;
int n, h;
LL alpha, beta;
int x[N], y[N];
db mxR[2][N];
LL dp[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
cin >> n >> h >> alpha >> beta;
FOR(i, 0, n)
cin >> x[i] >> y[i];
FOR(it, 0, 2)
{
FOR(i, 0, n)
{
mxR[it][i] = min((db)h - y[i], (x[n - 1] - x[i]) / 2.0);
FOR(j, i + 1, n)
{
#warning
// EPS
if (x[j] - x[i] > 2 * mxR[it][i] + EPS)
break;
if (y[j] <= y[i])
continue;
db b = 2 * (x[i] - x[j] - h + y[j]), c = (db)(x[i] - x[j]) * (x[i] - x[j]) + (db)(h - y[j]) * (h - y[j]);
db D = b * b - 4 * c;
assert(D > -EPS);
D = max(D, (db)0.0);
//if (D < EPS)
// break;
db res = (-b + sqrt(D)) / 2;
mxR[it][i] = min(mxR[it][i], res);
}
}
reverse(x, x + n);
FOR(i, 0, n)
x[i] *= -1;
}
reverse(mxR[1], mxR[1] + n);
dp[0] = alpha * (h - y[0]);
FOR(i, 1, n)
{
dp[i] = LINF;
FOR(j, 0, i)
{
if (x[i] - x[j] < 2 * min(mxR[0][j], mxR[1][i]) + EPS)
dp[i] = min(dp[i], dp[j] + alpha * (h - y[i]) + beta * (x[i] - x[j]) * (x[i] - x[j]));
}
}
if (dp[n - 1] == LINF)
cout << "impossible\n";
else
cout << dp[n - 1] << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
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: 3700kb
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: 3688kb
input:
2 1 1 1 0 0 2 0
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
2 1 1 1 0 0 3 0
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
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: 0ms
memory: 3712kb
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: 0ms
memory: 3624kb
input:
2 100000 10000 10000 0 0 100000 0
output:
100002000000000
result:
ok single line: '100002000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3704kb
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: 0ms
memory: 3696kb
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:
2053
result:
wrong answer 1st lines differ - expected: '2134', found: '2053'