oj.uz

Submission #93387

# Submission time Handle Problem Language Result Execution time Memory
93387 2019-01-08T01:28:25 Z wolf OBELISK (NOI14_obelisk) C++14
5 / 25
 44 ms 1016 KB 
#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 (h == 1)
        return abs(b - a);

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

    int c = (a - b) / h;
    int first = a - c * h;
    int ans = ones(first , b) + c * 2;
    if (first - h > 0)
        ans = min(ans , ones(first - h , b) + (c + 1) * 2);

    return ans;
}

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 760 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 7.0

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