Submission #480441

# Submission time Handle Problem Language Result Execution time Memory
480441 2021-10-16T11:08:27 Z nicolaalexandra Climbers (RMI18_climbers) C++14
5 / 100
61 ms 98292 KB
#include <bits/stdc++.h>
#define DIM 5010
#define INF 2000000000
using namespace std;

priority_queue <pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > h;
int dp[DIM][DIM],v[DIM];
int n,i,j;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i];

    int k = 1;
    for (i=2;i<n;i++){
        if ( (v[i] > v[i-1] && v[i] > v[i+1]) || (v[i] < v[i-1] && v[i] < v[i+1]))
            v[++k] = v[i];
    }

    v[++k] = 0;
    n = k;

    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            dp[i][j] = INF;

    /// dp[capat][segment] - A/B se afla intr un capat de segm si celalalt e pe un segm

    dp[1][n-1] = 0;
    h.push(make_pair(0,make_pair(1,n-1)));

    while (!h.empty()){
        int cost = h.top().first;
        int capat = h.top().second.first;
        int segm = h.top().second.second;
        h.pop();

        if (capat == segm || capat == segm+1){ /// au ajuns in acelasi punct
            cout<<cost;
            return 0;
        }

        if (capat < segm){ /// A e in capat

            if (v[capat] < v[capat+1]){ /// trebuie sa urc

                if (v[segm] > v[segm+1]){ /// poate si B sa urce

                    if (v[capat+1] <= v[segm]){
                        int val = v[capat+1] - v[capat];
                        if (dp[capat][segm] + val < dp[capat+1][segm]){
                            dp[capat+1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
                        }

                    } else {

                        int val = v[segm] - v[capat];
                        if (dp[capat][segm] + val < dp[segm][capat]){
                            dp[segm][capat] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm][capat],make_pair(segm,capat)));
                        }

                    }


                } else { /// B trebuie sa se intoarca inapoi

                    if (v[capat+1] <= v[segm+1]){
                        int val = v[capat+1] - v[capat];
                        if (dp[capat][segm] + val < dp[capat+1][segm]){
                            dp[capat+1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
                        }
                    } else {

                        int val = v[segm+1] - v[capat];
                        if (dp[capat][segm] + val < dp[segm+1][capat]){
                            dp[segm+1][capat] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm+1][capat],make_pair(segm+1,capat)));
                        }

                    }

                }


            } else { /// A coboara

                if (v[segm] > v[segm+1]){ /// trb sa coboare si B, dar se duce inapoi

                    if (v[capat+1] >= v[segm+1]){

                        int val = v[capat] - v[capat+1];
                        if (dp[capat][segm] + val < dp[capat+1][segm]){
                            dp[capat+1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
                        }

                    } else {
                        int val = v[capat] - v[segm+1];
                        if (dp[capat][segm] + val < dp[segm+1][capat]){
                            dp[segm+1][capat] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm+1][capat],make_pair(segm+1,capat)));
                        }

                    }


                } else { /// coboara B, merge inainte

                    if (v[capat+1] >= v[segm]){
                        int val = v[capat] - v[capat+1];
                        if (dp[capat][segm] + val < dp[capat+1][segm]){
                            dp[capat+1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
                        }
                    } else {
                        int val = v[capat] - v[segm];
                        if (dp[capat][segm] + val < dp[segm][capat]){
                            dp[segm][capat] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm][capat],make_pair(segm,capat)));
                        }
                    }
                }
            }

        } else { /// B e in capat

            if (v[capat] < v[capat-1]){ /// B urca

                if (v[segm+1] > v[segm]){ /// poate si A sa urce

                    if (v[segm+1] >= v[capat-1]){
                        int val = v[capat-1] - v[capat];
                        if (dp[capat][segm] + val < dp[capat-1][segm]){
                            dp[capat-1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
                        }
                    } else {
                        int val = v[segm+1] - v[capat];
                        if (dp[capat][segm] + val < dp[segm+1][capat-1]){
                            dp[segm+1][capat-1] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm+1][capat-1],make_pair(segm+1,capat-1)));
                        }
                    }


                } else { /// A urca, dar se intoarce inapoi

                    if (v[segm-1] >= v[capat-1]){
                        int val = v[capat-1] - v[capat];
                        if (dp[capat][segm] + val < dp[capat-1][segm]){
                            dp[capat-1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
                        }
                    } else {
                        int val = v[segm] - v[capat];
                        if (dp[capat][segm] + val < dp[segm][capat-1]){
                            dp[segm][capat-1] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm][capat-1],make_pair(segm,capat-1)));
                        }
                    }

                }


            } else { /// B coboara

                if (v[segm] < v[segm+1]){ /// A cobora, dar se intoarce inapoi

                    if (v[segm] <= v[capat-1]){
                        int val = v[capat] - v[capat-1];
                        if (dp[capat][segm] + val < dp[capat-1][segm]){
                            dp[capat-1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
                        }
                    } else {
                        int val = v[capat] - v[segm];
                        if (dp[capat][segm] + val < dp[segm][capat-1]){
                            dp[segm][capat-1] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm][capat-1],make_pair(segm,capat-1)));
                        }
                    }


                } else { /// A coboara, merge inainte

                    if (v[segm+1] <= v[capat-1]){
                        int val = v[capat] - v[capat-1];
                        if (dp[capat][segm] + val < dp[capat-1][segm]){
                            dp[capat-1][segm] = dp[capat][segm] + val;
                            h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
                        }
                    } else {
                        int val = v[capat] - v[segm+1];
                        if (dp[capat][segm] + val < dp[segm+1][capat-1]){
                            dp[segm+1][capat-1] = dp[capat][segm] + val;
                            h.push(make_pair(dp[segm+1][capat-1],make_pair(segm+1,capat-1)));
                        }
                    }

                }

            }

        }

    }

    cout<<"NO";

    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 676 KB Output isn't correct
2 Incorrect 1 ms 1740 KB Output isn't correct
3 Incorrect 5 ms 8140 KB Output isn't correct
4 Incorrect 30 ms 47436 KB Output isn't correct
5 Incorrect 61 ms 98292 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Incorrect 1 ms 972 KB Output isn't correct
4 Incorrect 1 ms 716 KB Output isn't correct
5 Incorrect 1 ms 2476 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Incorrect 1 ms 1740 KB Output isn't correct
3 Incorrect 5 ms 7628 KB Output isn't correct
4 Incorrect 24 ms 43764 KB Output isn't correct
5 Incorrect 28 ms 43480 KB Output isn't correct
6 Incorrect 42 ms 76824 KB Output isn't correct
7 Incorrect 50 ms 72828 KB Output isn't correct
8 Incorrect 60 ms 93248 KB Output isn't correct
9 Incorrect 55 ms 94064 KB Output isn't correct
10 Incorrect 54 ms 93124 KB Output isn't correct