Submission #641326

# Submission time Handle Problem Language Result Execution time Memory
641326 2022-09-16T12:07:47 Z RaulAndrei01 Climbers (RMI18_climbers) C++17
5 / 100
93 ms 196296 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;
};
struct state {
    bool friend operator<(const state& s1, const state& s2)
    {
        return s1.dist > s2.dist;
    }
    int p, s;
    ll dist;
};

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

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

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; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dist[i][j] = 1e18;
        }
    }
    priority_queue<state> q;
    q.push({1, n-1, 0});
    dist[1][n-1] = 0;
    ll ans = -1;
    while (!q.empty())
    {

        state crt = q.top();
     //   cout << crt.p << ' ' << crt.s << '\n';
       // cout << crt.dist << '\n';
      //  int a; cin >> a;
        q.pop();
        if (crt.s >= n) continue;
        if (crt.p == crt.s || crt.p == crt.s + 1)
        {
            ans = crt.dist;
            break;
        }
        
        if (crt.dist > dist[crt.p][crt.s]) continue;
    
        int i = crt.p, j = crt.s;
        if (s[j].hmin > h[i] || s[j].hmax < h[i]) continue;
          //  cout << i << ' ' << j  << ":\n";
            if (i < n && 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 (dist[i+1][j] > dist[i][j] + abs(h[i] - h[i+1]))
                {
                    dist[i+1][j] = dist[i][j] + abs(h[i] - h[i+1]);
                    q.push({i + 1, j, dist[i+1][j]});
                }
            }
            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 (dist[i-1][j] > dist[i][j] + abs(h[i] - h[i-1]))
                {
                    dist[i-1][j] = dist[i][j] + abs(h[i] - h[i-1]);
                    q.push({i - 1, j, dist[i-1][j]});
                }
            }
            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 (dist[j][i] > dist[i][j] + abs(h[j] - h[i]))
                {
                    dist[j][i] = dist[i][j] + abs(h[j] - h[i]);
                    q.push({j, i, dist[j][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 (dist[j][i-1] > dist[i][j] + abs(h[j] - h[i]))
                {
                    dist[j][i-1] = dist[i][j] + abs(h[j] - h[i]);
                    q.push({j, i-1, dist[j][i-1]});
                }
            }
            if (j < n && 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 (dist[j+1][i] > dist[i][j] + abs(h[j+1] - h[i]))
                {
                    dist[j+1][i] = dist[i][j] + abs(h[j+1] - h[i]);
                    q.push({j+1, i, dist[j+1][i]});
                }
            }
            if (j < n && 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])});
                if (dist[j+1][i-1] > dist[i][j] + abs(h[j+1] - h[i]))
                {
                    dist[j+1][i-1] = dist[i][j] + abs(h[j+1] - h[i]);
                    q.push({j+1, i-1, dist[j+1][i]});
                }
            }

    }
    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 << dijsktra() << '\n';

}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Incorrect 1 ms 2132 KB Output isn't correct
3 Incorrect 6 ms 12116 KB Output isn't correct
4 Incorrect 41 ms 82812 KB Output isn't correct
5 Incorrect 90 ms 196296 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Incorrect 1 ms 980 KB Output isn't correct
4 Incorrect 1 ms 724 KB Output isn't correct
5 Incorrect 2 ms 3028 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 2004 KB Output isn't correct
3 Incorrect 6 ms 11320 KB Output isn't correct
4 Incorrect 41 ms 76092 KB Output isn't correct
5 Incorrect 42 ms 75524 KB Output isn't correct
6 Incorrect 69 ms 137804 KB Output isn't correct
7 Incorrect 70 ms 130288 KB Output isn't correct
8 Incorrect 86 ms 186148 KB Output isn't correct
9 Incorrect 91 ms 187844 KB Output isn't correct
10 Incorrect 93 ms 185696 KB Output isn't correct