Submission #330442

#	Time	Username	Problem	Language	Result	Execution time	Memory
330442		Ruxandra985	Climbers (RMI18_climbers)	C++14	0 / 100	296 ms	524296 KiB

climbers

#include <bits/stdc++.h>

using namespace std;
int n;

vector <pair <int , int> > v[25000000];
int dp[25000000] , vinit[5010];
priority_queue <pair <int , int> > h;

int encode (int x , int y){

    x--;
    y--;
    return x * n  + y;

}

pair <int , int> decode (int cod){
    return make_pair(cod / n + 1 , cod % n + 1);
}

void muchie (int x1 , int y1 , int x2 , int y2 , int cost){

    v[encode(x1 , y1)].push_back(make_pair(encode(x2 , y2) , cost));

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , ers , cost , nod , val , vecin , j;
    pair <int , int> actual;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i <= n ; i++)
        fscanf (fin,"%d",&vinit[i]);


    ers = 0;

    for (i = 2 ; i < n ; i++){
        if ((vinit[i - 1] <= vinit[i] && vinit[i] <= vinit[i + 1]) || (vinit[i - 1] >= vinit[i] && vinit[i] >= vinit[i + 1]))
            ers++; /// il stergi pe vinit[i]
        else vinit[i - ers] = vinit[i];
    }

    vinit[n - ers] = vinit[n];
    n -= ers;

    /// acum vinit ul e "condensat"

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j < n ; j++){

            //if (i == 3 && j == 4)
            //printf ("a");

            /// daca cu un om sunt pe nodul i si cu celalalt pe segmentul j , j + 1

            if ((vinit[j] <= vinit[i] && vinit[i] <= vinit[j + 1]) || (vinit[j] >= vinit[i] && vinit[i] >= vinit[j + 1])){
                /// e o stare vinitalida

                if (vinit[j] < vinit[j + 1]){ /// segm e crescator

                    if (i != n){ /// ma duc in nodul i + 1, deci nu parasesc segm

                        if (vinit[i + 1] > vinit[i] && vinit[i + 1] <= vinit[j + 1]){

                            muchie (i , j , i + 1 , j , vinit[i + 1] - vinit[i]); /// se pastreaza segmentul

                        }
                        else if (vinit[i + 1] < vinit[i] && vinit[i + 1] >=  vinit[j]){
                            muchie (i , j , i + 1 , j , vinit[i] - vinit[i + 1]);
                        }


                    }

                    if (i != 1){ /// ma duc in nodul i - 1, raman pe acelasi segm

                        if (vinit[i - 1] > vinit[i] && vinit[i - 1] <= vinit[j + 1]){

                            muchie (i , j , i - 1 , j , vinit[i - 1] - vinit[i]); /// se pastreaza segmentul

                        }
                        else if (vinit[i - 1] < vinit[i] && vinit[i - 1] >=  vinit[j]){
                            muchie (i , j , i - 1 , j , vinit[i] - vinit[i - 1]);
                        }

                    }

                    /// --------------------------------------------------

                    /// sunt intre j si j + 1

                    /// vinitreau sa ma mut in j, adc cobor
                    if (i != n && vinit[i] > vinit[i + 1] && vinit[i] - vinit[i + 1] >= vinit[i] - vinit[j]){
                        muchie (i , j , j , i , vinit[i] - vinit[j]);
                    }

                    if (i != 1 && vinit[i] > vinit[i - 1] && vinit[i] - vinit[i - 1] >= vinit[i] - vinit[j]){
                        muchie (i , j , j , i - 1 , vinit[i] - vinit[j]);
                    }

                    /// in j + 1 , adc urc

                    if (i != n && vinit[i] < vinit[i + 1] && vinit[i + 1] - vinit[i] >= vinit[j + 1] - vinit[i]){
                        muchie (i , j , j + 1 , i , vinit[j + 1] - vinit[i]);
                    }

                    if (i != 1 && vinit[i] < vinit[i - 1] && vinit[i - 1] - vinit[i] >= vinit[j + 1] - vinit[i]){
                        muchie (i , j , j + 1 , i - 1 , vinit[j + 1] - vinit[i]);
                    }


                    /// cazuri particulare de egalitate??



                }
                else { /// segm e descrescator


                    if (i != n){ /// ma duc in nodul i + 1, deci nu parasesc segm

                        if (vinit[i + 1] > vinit[i] && vinit[i + 1] <= vinit[j]){

                            muchie (i , j , i + 1 , j , vinit[i + 1] - vinit[i]); /// se pastreaza segmentul

                        }
                        else if (vinit[i + 1] < vinit[i] && vinit[i + 1] >= vinit[j + 1]){
                            muchie (i , j , i + 1 , j , vinit[i] - vinit[i + 1]);
                        }


                    }

                    if (i != 1){ /// ma duc in nodul i - 1, raman pe acelasi segm

                        if (vinit[i - 1] > vinit[i] && vinit[i - 1] <= vinit[j]){

                            muchie (i , j , i - 1 , j , vinit[i - 1] - vinit[i]); /// se pastreaza segmentul

                        }
                        else if (vinit[i - 1] < vinit[i] && vinit[i - 1] >= vinit[j + 1]){
                            muchie (i , j , i - 1 , j , vinit[i] - vinit[i - 1]);
                        }

                    }

                    /// --------------------------------------------------

                    /// sunt intre j si j + 1

                    /// vinitreau sa ma mut in j, adc URC


                    if (i != n && vinit[i] < vinit[i + 1] && vinit[i + 1] - vinit[i] >= vinit[j] - vinit[i]){
                        muchie (i , j , j , i , vinit[j] - vinit[i]);
                    }

                    if (i != 1 && vinit[i] < vinit[i - 1] && vinit[i - 1] - vinit[i] >= vinit[j] - vinit[i]){
                        muchie (i , j , j , i - 1 , vinit[j] - vinit[i]);
                    }

                    /// vinitreau sa ma duc in j + 1 adica cobor

                    if (i != n && vinit[i] > vinit[i + 1] && vinit[i] - vinit[i + 1] >= vinit[i] - vinit[j + 1]){
                        muchie (i , j , j + 1 , i , vinit[i] - vinit[j + 1]);
                    }

                    if (i != 1 && vinit[i] > vinit[i - 1] && vinit[i] - vinit[i - 1] >= vinit[i] - vinit[j + 1]){
                        muchie (i , j , j + 1 , i - 1 ,vinit[i] - vinit[j + 1]);
                    }

                }


            }


        }
    }

    /// am construit graful vietii

    for (i = 0 ; i < n * n ; i++)
        dp[i] = 2000000000;

    dp[encode(1 , n - 1)] = 0;

    h.push(make_pair(0 , encode(1 , n - 1)));

    while (!h.empty()){
        cost = -h.top().first;
        nod = h.top().second;
        h.pop();

        actual = decode(nod);

        //printf ("%d %d\n",actual.first , actual.second);

        if (actual.first == actual.second || actual.first == actual.second + 1){
            fprintf (fout,"%d",cost);
            return 0;
        }

        if (dp[nod] != cost)
            continue;

        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i].first;
            val = v[nod][i].second;

            if (dp[vecin] > dp[nod] + val){
                dp[vecin] = dp[nod] + val;
                h.push(make_pair(-dp[vecin] , vecin));
            }

        }
    }

    fprintf (fout,"NO");

    return 0;
}

Compilation message (stderr)

climbers.cpp: In function 'int main()':
climbers.cpp:210:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |         for (i = 0 ; i < v[nod].size() ; i++){
      |                      ~~^~~~~~~~~~~~~~~
climbers.cpp:33:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
climbers.cpp:35:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         fscanf (fin,"%d",&vinit[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50