Submission #93386

#	Time	Username	Problem	Language	Result	Execution time	Memory
93386		wolf	OBELISK (NOI14_obelisk)	C++14	5 / 25	44 ms	1528 KiB

obelisk

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define x first
#define y second

const int N = 505 , M = 105;
int n , h , Sx , Sy , Ex , Ey;
vector<pair<int , int> > f[N];


int ones (int a , int b) {
    return abs(b - a) + (b != a ? 2 : 0);
}

int best (int a , int b) {
    if (a > b)
        swap(a , b);
    if (h == 1)
        return b - a;
    int c = (b - a) / h;
    int first = a + c * h;
    return min(ones(first , b) , ones(first + h , b) + 2) + c * 2;
}

int dist (const pair<int , int> &a ,const pair<int , int> &b) {
    return best(a.x , b.x) + best(a.y , b.y);
}

ll memo[N][M];
ll solve (int i , int j) {
    if (!i)
        return 0;

    ll &ret = memo[i][j];
    if (~ret)
        return ret;

    ret = LLONG_MAX / 2;
    for (int k = 0 ;k < f[i].size() ;k++)
        ret = min(ret , solve(i - 1 , k) +  dist(f[i + 1][j] , f[i][k]));

    return ret;
}

int main() {
    ios::sync_with_stdio(0) ; cin.tie(0) , cout.tie(0);
    cin >> n >> h >> Sx >> Sy >> Ex >> Ey;

    f[n + 1].emplace_back(Sx , Sy);
    f[1].emplace_back(Ex , Ey);

    int cnt , x , y;
    for (int i = n ;i > 1 ;i--) {
        cin >> cnt;
        while (cnt--) {
            cin >> x >> y;
            f[i].emplace_back(x , y);
        }
    }


    memset(memo , -1 , sizeof memo);
    cout << solve(n , 0);

    return 0;
}

Compilation message (stderr)

obelisk.cpp: In function 'll solve(int, int)':
obelisk.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0 ;k < f[i].size() ;k++)
                     ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7