답안 #330455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330455 2020-11-25T10:15:42 Z Ruxandra985 Climbers (RMI18_climbers) C++14
100 / 100
295 ms 195948 KB
#include <bits/stdc++.h>

using namespace std;
int n;
long long vinit[5010];
long long dp[25000000];
priority_queue <pair <long long , 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 , long long cost){

    int nod , vecin;

    nod = encode(x1 , y1);
    vecin = encode(x2 , y2);

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

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , ers , nod , j;
    long long cost;
    pair <int , int> actual;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i <= n ; i++)
        fscanf (fin,"%lld",&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 = 0 ; i < n * n ; i++)
        dp[i] = 2000000000000000000;

    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);

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

        i = actual.first;
        j = actual.second;

        if (i == j || i == j + 1){
            fprintf (fout,"%lld",cost);
            return 0;
        }

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

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


        if (j != n && vinit[i] == vinit[j + 1])
            muchie (i , j , i , j + 1 , 0);

        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

            /// vreau 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]);
            }

        }
        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]);
            }

        }


    }

    fprintf (fout,"NO");

    return 0;
}

Compilation message

climbers.cpp: In function 'int main()':
climbers.cpp:42:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
climbers.cpp:44:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |         fscanf (fin,"%lld",&vinit[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 45 ms 70636 KB Output is correct
5 Correct 132 ms 195948 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1516 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 75 ms 7532 KB Output is correct
4 Correct 153 ms 64492 KB Output is correct
5 Correct 191 ms 64108 KB Output is correct
6 Correct 219 ms 121964 KB Output is correct
7 Correct 222 ms 115052 KB Output is correct
8 Correct 217 ms 176108 KB Output is correct
9 Correct 295 ms 179692 KB Output is correct
10 Correct 263 ms 175468 KB Output is correct