QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104623#2338. Beautiful Bridges_skb_WA 2ms3720kbC++172.7kb2023-05-11 13:28:322023-05-11 13:28:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 13:28:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3720kb
  • [2023-05-11 13:28:32]
  • 提交

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'