oj.uz

답안 #1096071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096071 2024-10-03T17:07:07 Z alexdd Climbers (RMI18_climbers) C++17
50 / 100
 800 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_STARI = 6300000;
const long long INF = 1e18;

vector<pair<int,int>> con[MAX_STARI];
long long dist[MAX_STARI];
int nrm[5005][5005],cate;
int n,p[5005];
void add_edge(int v1, int m1, int v2, int m2)
{
    con[nrm[v1][m1]].push_back({nrm[v2][m2],abs(p[v1]-p[v2])});
    con[nrm[v2][m2]].push_back({nrm[v1][m1],abs(p[v1]-p[v2])});
}
priority_queue<pair<long long,int>> pq;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    assert(p[1]==0);
    assert(p[n]==0);
    for(int v=1;v<=n;v++)
    {
        for(int m=1;m<n;m++)
        {
            if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
                continue;
            nrm[v][m] = ++cate;
        }
    }
    for(int v=1;v<=n;v++)
    {
        for(int m=1;m<n;m++)
        {
            if(p[v] < min(p[m],p[m+1]) || p[v] > max(p[m],p[m+1]))
                continue;
            for(int newv:{v-1,v+1})
            {
                if(newv>=1 && newv<=n && min(p[m],p[m+1]) <= p[newv] && p[newv] <= max(p[m],p[m+1]))
                {
                    add_edge(v,m,newv,m);
                }
            }

            if(p[v] == p[m] && m-1>0)
            {
                add_edge(v,m,v,m-1);
            }
            if(p[v] == p[m+1] && m+1<n)
            {
                add_edge(v,m,v,m+1);
            }

            if(p[v] == p[m])
            {
                if(v<n) add_edge(v,m,m,v);
                if(v>1) add_edge(v,m,m,v-1);
            }
            if(p[v] == p[m+1])
            {
                if(v<n) add_edge(v,m,m+1,v);
                if(v>1) add_edge(v,m,m+1,v-1);
            }
            if(v+1<n && min(p[v],p[v+1]) <= p[m] && p[m] <= max(p[v],p[v+1]))
            {
                add_edge(v,m,m,v);
            }
            if(v-1>0 && min(p[v],p[v-1]) <= p[m] && p[m] <= max(p[v],p[v-1]))
            {
                add_edge(v,m,m,v-1);
            }
            if(v+1<n && min(p[v],p[v+1]) <= p[m+1] && p[m+1] <= max(p[v],p[v+1]))
            {
                add_edge(v,m,m+1,v);
            }
            if(v-1>0 && min(p[v],p[v-1]) <= p[m+1] && p[m+1] <= max(p[v],p[v-1]))
            {
                add_edge(v,m,m+1,v-1);
            }
        }
    }
    for(int i=1;i<=cate;i++)
        dist[i]=INF;
    dist[nrm[n][1]]=0;
    dist[nrm[1][n-1]]=0;
    pq.push({0,nrm[n][1]});
    pq.push({0,nrm[1][n-1]});
    while(!pq.empty())
    {
        long long cdist = -pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        if(dist[nod]!=cdist)
            continue;
        //cerr<<nod<<" new dist "<<dist[nod]<<"\n";
        for(auto [adj,c]:con[nod])
        {
            if(cdist + c < dist[adj])
            {
                dist[adj] = cdist + c;
                pq.push({-dist[adj],adj});
            }
        }
    }
    long long rez=INF;
    for(int m=1;m<n;m++)
    {
        rez = min(rez, dist[nrm[m][m]]);
        rez = min(rez, dist[nrm[m+1][m]]);
    }
    assert(rez<INF);
    cout<<rez;
    return 0;
}
/*
7
0 10 1 20 5 10 0
*/

Subtask #1
15.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 149076 KB Output is correct
2 Correct 68 ms 151892 KB Output is correct
3 Correct 160 ms 180132 KB Output is correct
4 Execution timed out 1039 ms 409940 KB Time limit exceeded
5 Runtime error 332 ms 498760 KB Execution killed with signal 11

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 148552 KB Output is correct
2 Correct 63 ms 148788 KB Output is correct
3 Correct 71 ms 150100 KB Output is correct
4 Correct 65 ms 149328 KB Output is correct
5 Correct 76 ms 155220 KB Output is correct

Subtask #3
10.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 150356 KB Output is correct
2 Correct 84 ms 161616 KB Output is correct
3 Execution timed out 915 ms 375496 KB Time limit exceeded
4 Runtime error 791 ms 524288 KB Execution killed with signal 9
5 Runtime error 259 ms 395860 KB Execution killed with signal 11
6 Runtime error 300 ms 458832 KB Execution killed with signal 11
7 Runtime error 287 ms 458660 KB Execution killed with signal 11
8 Runtime error 329 ms 498776 KB Execution killed with signal 11
9 Runtime error 323 ms 498784 KB Execution killed with signal 11
10 Runtime error 320 ms 498768 KB Execution killed with signal 11