oj.uz

Submission #51548

# Submission time Handle Problem Language Result Execution time Memory
51548 2018-06-18T12:45:09 Z Kubalionzzale OBELISK (NOI14_obelisk) C++11
5 / 25
 110 ms 1968 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)
{
    ++m;
    int length = abss(from.first - to.first);
    int overfirst = ((length / m) + 1) * m;
    int underfirst = (length / m) * m;
    int firstDiff = 1e15;

    if (underfirst == length)
    {
        if (length == 0)
            firstDiff = 0;
        else
            firstDiff = (length / m) * 2;
    }
    else
    {
        firstDiff = std::min(abss(overfirst - length) + ((length / m) + 1) * 2, abss(length - underfirst) + (length / m) * 2) + 2;
    }

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

    length = abss(from.second - to.second);
    overfirst = ((length / m) + 1) * m;
    underfirst = (length / m) * m;
    int secondDiff = 1e15;

    if (underfirst == length)
    {
        if (length == 0)
            secondDiff = 0;
        else
            secondDiff = (length / m) * 2;
    }
    else
    {
        secondDiff = std::min(abss(overfirst - length) + ((length / m) + 1) * 2, abss(length - underfirst) + (length / m) * 2) + 2;
    }

//    std::cout << secondDiff << "\n";

    return firstDiff + secondDiff;
}

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:57:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1380 KB Output is correct
3 Correct 3 ms 1464 KB Output is correct
4 Correct 2 ms 1464 KB Output is correct
5 Correct 3 ms 1464 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 1960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 1968 KB Output isn't correct
2 Halted 0 ms 0 KB -