oj.uz

답안 #51669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51669 2018-06-19T18:51:29 Z Kubalionzzale 오벨리스크 (NOI14_obelisk) C++14
25 / 25
 109 ms 2044 KB 
#include <iostream>

#define int long long int

int abss(int x)
{
    if (x < 0)
        return -x;
    else
        return x;
}

int calc(std::pair<int, int> from, std::pair<int, int> to, int m)
{
    if (from.first == to.first && to.second == from.second)
        return 0;
    ++m;
    int length = abss(from.first - to.first);
    int overfirst = ((length / m) + 1LL) * m;
    int underfirst = (length / m) * m;
    int val = length / m;
    int oneover = abss(overfirst - length);
    int oneunder = abss(underfirst - length);

//    std::cout << firstDiff << " ";

    int length2 = abss(from.second - to.second);
    int overfirst2 = ((length2 / m) + 1LL) * m;
    int underfirst2 = (length2 / m) * m;
    int val2 = length2 / m;
    int oneover2 = abss(overfirst2 - length2);
    int oneunder2 = abss(underfirst2 - length2);

    int min = 1e15;
    //OVER OVER

    min = std::min(min, abss(overfirst - length) + abss(overfirst2 - length2) + ((length / m) + 1LL) * 2LL + ((length2 / m) + 1LL) * 2LL);
   // std::cout << "OVEROVER: " << abss(overfirst - length) + abss(overfirst2 - length2) + ((length / m) + 1LL) * 2LL + ((length2 / m) + 1LL) * 2LL << "\n";

    //UNDER OVER
    if (val > 0 || oneunder2 == 0)
    {
      //  std::cout << "UNDEROVER: " << oneunder + oneover2 + val * 2LL + ((length2 / m) + 1LL) * 2LL << "\n";
        min = std::min(min, oneunder + oneover2 + val * 2LL + ((length2 / m) + 1LL) * 2LL);
    }
    else
    {
    //    std::cout << "UNDEROVER: " << oneunder + oneover2 + val * 2LL + ((length2 / m) + 1LL) * 2LL + 2LL << "\n";
        min = std::min(min, oneunder + oneover2 + val * 2LL + ((length2 / m) + 1LL) * 2LL + 2LL);
    }

    //OVER UNDER
    if (val2 > 0 || oneunder == 0)
    {
  //      std::cout << "OVERUNDER: " << oneover + oneunder2 + ((length / m) + 1LL) * 2LL + val2 * 2LL << "\n";
        min = std::min(min, oneover + oneunder2 + ((length / m) + 1LL) * 2LL + val2 * 2LL);
    }
    else
    {
//        std::cout << "OVERUNDER: " << oneover + oneunder2 + ((length / m) + 1LL) * 2LL + val2 * 2LL + 2LL << "\n";
        min = std::min(min, oneover + oneunder2 + ((length / m) + 1LL) * 2LL + val2 * 2LL + 2LL);
    }

    //UNDER UNDER
    int add = 4LL;
    if (val > 0 || oneunder2 == 0)
        add -= 2;
    if (val2 > 0 || oneunder == 0)
        add -= 2;

    min = std::min(min, oneunder + oneunder2 + val * 2LL + val2 * 2LL + add);
//    std::cout << "UNDERUNDER: " << oneunder + oneunder2 + val * 2LL + val2 * 2LL + add << "\n";

    return min;
}

main()
{
    int k, m;
    std::cin >> k >> m;

    std::pair<int, int> hole[510][110];
    int mini[510][110];
    int holeNumber[510];

    std::pair<int, int> start, ende;
    std::cin >> start.first >> start.second >> ende.first >> ende.second;
    holeNumber[0] = 1;
    holeNumber[k] = 1;
    hole[0][0].first = start.first;
    hole[0][0].second = start.second;
    hole[k][0].first = ende.first;
    hole[k][0].second = ende.second;
    mini[0][0] = 0;
    mini[k][0] = 1e15;

    for (int i = 1; i <= k - 1; ++i)
    {
        std::cin >> holeNumber[i];
        for (int j = 0; j < holeNumber[i]; ++j)
        {
            mini[i][j] = 1e15;
            std::cin >> hole[i][j].first >> hole[i][j].second;
        }
    }

    if (m == 1)
    {
        for (int i = 1; i <= k; ++i)
        {
            for (int j = 0; j < holeNumber[i]; ++j)
            {
                for (int q = 0; q < holeNumber[i - 1]; ++q)
                {
                    int val = abss(hole[i][j].first - hole[i - 1][q].first) + abss(hole[i][j].second - hole[i - 1][q].second);
                    mini[i][j] = std::min(mini[i][j], val + mini[i - 1][q]);
                }
            }
        }

        std::cout << mini[k][0];
        return 0;
    }

    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < holeNumber[i]; ++j)
        {
            for (int q = 0; q < holeNumber[i - 1]; ++q)
            {
                int val = calc(hole[i][j], hole[i - 1][q], m);
         //       std::cout << val << " " << j << " " << q << "\n";
                mini[i][j] = std::min(mini[i][j], val + mini[i - 1][q]);
            }
        }
    }

    std::cout << mini[k][0];
}

Compilation message

obelisk.cpp:77:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 2 ms 1252 KB Output is correct
3 Correct 4 ms 1456 KB Output is correct
4 Correct 4 ms 1456 KB Output is correct
5 Correct 2 ms 1456 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1456 KB Output is correct
2 Correct 4 ms 1456 KB Output is correct
3 Correct 5 ms 1456 KB Output is correct
4 Correct 5 ms 1468 KB Output is correct
5 Correct 4 ms 1468 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 1872 KB Output is correct
2 Correct 85 ms 1896 KB Output is correct
3 Correct 67 ms 1896 KB Output is correct
4 Correct 76 ms 1976 KB Output is correct
5 Correct 77 ms 1976 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 1976 KB Output is correct
2 Correct 84 ms 1976 KB Output is correct
3 Correct 92 ms 2044 KB Output is correct
4 Correct 96 ms 2044 KB Output is correct
5 Correct 79 ms 2044 KB Output is correct