답안 #641312

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641312 2022-09-16T11:29:55 Z RaulAndrei01 Climbers (RMI18_climbers) C++17
45 / 100
32 ms 17740 KB
#include <bits/stdc++.h>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

ll h[5005];
int n;

bool check(int i)
{
    if (h[i-2] <= h[i-1] && h[i-1] <= h[i]) return 1;
    if (h[i-2] >= h[i-1] && h[i-1] >= h[i]) return 1;
    return 0;
}

struct seg {
    ll hmax, hmin;
    bool dir;
};

int hashState (int x, int y)
{
    return (n + 1) * x + y;
}
struct edge {
    int to; ll cost;
};

seg s[5005];
vector<edge> adj[250050];
ll dist[250050];

bool unhash (int x)
{
    int f = x % (n + 1);
    int s = x / (n + 1);
    if (f == s) return 1;
    if (s == f + 1) return 1;
    return 0;
}

ll dijsktra ()
{
    for (int i = 0; i <= n * (n + 1) + 10; i++)
    {
        dist[i] = 1e18;
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.push({0, hashState(1, n-1)});
    dist[hashState(1, n - 1)] = 0;
    ll ans = -1;
    while (!q.empty())
    {

        pair<ll, int> crt = q.top();
        q.pop();
    //    cout << crt.first << '\n';
    //    cout << crt.second / (n + 1) << ' ' << crt.second % (n + 1) << '\n';
        if (unhash(crt.second))
        {
            ans = crt.first;
            break;
        }
        
        if (crt.first > dist[crt.second]) continue;
        for (auto to : adj[crt.second])
        {
         //   cout << dist[to.to] << ' ';
            if (dist[to.to] > dist[crt.second] + to.cost)
            {
                q.push({dist[crt.second] + to.cost, to.to});
                dist[to.to] = dist[crt.second] + to.cost;
            }
        }
    }
    return ans;
}

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
        if (i > 2 && check(i))
        {
            n--;
            i--;
            h[i] = h[i+1];
            h[i+1] = 0;
        }
    }
    for (int i = 1; i < n; i++)
    {
        s[i] = {max(h[i], h[i+1]), min(h[i], h[i+1])};
        if (h[i] < h[i+1]) s[i].dir = 1;

    //    cout << s[i].hmin << ' ' << s[i].hmax << '\n';
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (s[j].hmin > h[i] || s[j].hmax < h[i]) continue;
          //  cout << i << ' ' << j  << ":\n";
            if (h[i+1] >= s[j].hmin && h[i+1] <= s[j].hmax)
            {
            //    cout << h[i+1] << ' ' << s[j].hmin << ' ' << s[j].hmax << '\n';
           //    cout << hashState(i, j) << ' ' << hashState(i + 1, j) << '\n';
                adj[hashState(i, j)].push_back({hashState(i + 1, j), abs(h[i] - h[i+1])});
                adj[hashState(i + 1, j)].push_back({hashState(i, j), abs(h[i] - h[i+1])});
            }
            if (i > 1 && h[i-1] >= s[j].hmin && h[i-1] <= s[j].hmax)
            {
            //    cout << h[i-1] << ' ' << s[j].hmin << ' ' << s[j].hmax << '\n';
            //    cout << hashState(i, j) << ' ' << hashState(i - 1, j) << '\n';
                adj[hashState(i, j)].push_back({hashState(i - 1, j), abs(h[i] - h[i-1])});
                adj[hashState(i - 1, j)].push_back({hashState(i, j), abs(h[i] - h[i-1])});
            }
            if (h[j] >= s[i].hmin && h[j] <= s[i].hmax)
            {
            //    cout << h[j] << ' ' << s[i].hmin << ' ' << s[i].hmax << '\n';
            //    cout << hashState(i, j) << ' ' << hashState(j, i) << '\n';
                adj[hashState(i, j)].push_back({hashState(j, i), abs(h[j] - h[i])});
                adj[hashState(j, i)].push_back({hashState(i, j), abs(h[j] - h[i])});
            }
            if (i > 1 && h[j] >= s[i-1].hmin && h[j] <= s[i-1].hmax)
            {
            //    cout << h[j] << ' ' << s[i-1].hmin << ' ' << s[i-1].hmax << '\n';
            //    cout << hashState(i, j) << ' ' << hashState(j, i-1) << '\n';
                adj[hashState(i, j)].push_back({hashState(j, i-1), abs(h[j] - h[i])});
                adj[hashState(j, i-1)].push_back({hashState(i, j), abs(h[j] - h[i])});
            }
            if (h[j+1] >= s[i].hmin && h[j+1] <= s[i].hmax)
            {
            //    cout << h[j+1] << ' ' << s[i].hmin << ' ' << s[i].hmax << '\n';
            //    cout << hashState(i, j) << ' ' << hashState(j+1, i) << '\n';
                adj[hashState(i, j)].push_back({hashState(j+1, i), abs(h[j+1] - h[i])});
                adj[hashState(j+1, i)].push_back({hashState(i, j), abs(h[j+1] - h[i])});
            }
            if (i > 1 && h[j+1] >= s[i-1].hmin && h[j+1] <= s[i-1].hmax)
            {
            //    cout << h[j+1] << ' ' << s[i-1].hmin << ' ' << s[i-1].hmax << '\n';
            //    cout << hashState(i, j) << ' ' << hashState(j+1, i-1) << '\n';
                adj[hashState(i, j)].push_back({hashState(j+1, i-1), abs(h[j+1] - h[i])});
                adj[hashState(j+1, i-1)].push_back({hashState(i, j), abs(h[j+1] - h[i])});
            }
        }
    }

  /*  for (int i = 1; i <= (n + 1) * n; i++)
    {
        cout << i / (n + 1) << ' ' << i % (n + 1) << ":\n";
        for (auto to : adj[i]) 
        cout << " " << to.to / (n + 1) << ' ' <<
         to.to % (n + 1) << ' ' << to.cost << '\n';
    }*/

    cout << dijsktra() << '\n';

}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 13 ms 9920 KB Output is correct
3 Runtime error 8 ms 12372 KB Execution killed with signal 11
4 Runtime error 10 ms 12464 KB Execution killed with signal 11
5 Runtime error 10 ms 12628 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6184 KB Output is correct
2 Correct 4 ms 6356 KB Output is correct
3 Correct 6 ms 7636 KB Output is correct
4 Correct 5 ms 6868 KB Output is correct
5 Correct 20 ms 12884 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7764 KB Output is correct
2 Correct 32 ms 17740 KB Output is correct
3 Runtime error 10 ms 12344 KB Execution killed with signal 11
4 Runtime error 12 ms 12492 KB Execution killed with signal 11
5 Runtime error 11 ms 12624 KB Execution killed with signal 11
6 Runtime error 11 ms 12504 KB Execution killed with signal 11
7 Runtime error 10 ms 12596 KB Execution killed with signal 11
8 Runtime error 10 ms 12628 KB Execution killed with signal 11
9 Runtime error 11 ms 12736 KB Execution killed with signal 11
10 Runtime error 11 ms 12628 KB Execution killed with signal 11