QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178293#2338. Beautiful BridgesPetroTarnavskyi#WA 0ms3712kbC++171.7kb2023-09-13 20:45:002023-09-13 20:45:00

Judging History

你现在查看的是最新测评结果

  • [2023-09-13 20:45:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2023-09-13 20:45:00]
  • 提交

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'