oj.uz

Submission #44193

# Submission time Handle Problem Language Result Execution time Memory
44193 2018-03-30T11:06:55 Z wasyl OBELISK (NOI14_obelisk) C++11
25 / 25
 50 ms 2436 KB 
#include <bits/stdc++.h>
#ifndef dbg
#define dbg(...)
#endif
#define all(x) begin(x), end(x)
#define rsz(...) resize(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define prt(...) print(cout, __VA_ARGS__)
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define dprt(...) dbg(print(cerr,__VA_ARGS__))
#define ddmp(...) dbg(dmp(__VA_ARGS__))
using namespace std;using ll=long long;
template<typename t>using V=vector<t>;
template<typename t>void print(ostream& os, const t& a){os<<a<<'\n';}
template<typename t, typename... A>void print
(ostream& os, const t& a, A&&... b){os<<a<<' ';print(os, b...);}

constexpr ll INF = 1e15 + 1;

struct Point
{
    int x, y;
    Point(int x, int y):
    x(x), y(y){}        
};

struct State
{
    Point v;
    ll val;
    State(Point v, ll val = 0):
    v(v), val(val){}
    State(int x, int y, ll val = 0):
    v(x, y), val(val){}
};

int k, m, v;
V< V< State > > dp;

inline Point turn_to_vector(const Point& a, const Point& b)
{
    return Point(abs(a.x - b.x), abs(a.y - b.y));
}

inline ll cost (int a, bool p, bool q)
{
    if (a == 0)
        return (p? 2 : 0);
    
    if (not p)
        return a;
    
    if (not q and a % v == 0)
        return a / v * 2;
    
    if (not q and a % v != 0)
        return INF;
    
    return min(
        max(2LL, (ll)(a / v) * 2) + a - ((a / v) * v),
        (ll)(a / v) * 2 + 2 + (((a / v) * v + v) - a)); 
}

inline ll cost(const Point& a)
{
    if (a.x == 0 and a.y == 0)
        return 0;
        
    if (m == 1)
        return a.x + a.y;
        
    return min({
    cost(a.x, 0, 1) + cost(a.y, 1 ,0),
    cost(a.x, 1, 0) + cost(a.y, 0, 1),
    cost(a.x, 1, 1) + cost(a.y, 1, 1)});
}

inline void proceed()
{
    for (auto& q : dp[1])
    {
        ll cos = LLONG_MAX;
        ddmp(q.v.x, q.v.y, q.val);
        for (auto& p : dp[0])
        {
            cos = min(cos, p.val + cost(turn_to_vector(p.v, q.v))); 
            ddmp(p.v.x, p.v.y, p.val);
        }
        q.val += cos;
        ddmp(q.val);
    }
    
    swap(dp[0], dp[1]);
    dp[1].clear();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> k >> m;
    v = m + 1;
    
    int stx, sty, enx, eny;
    
    cin >> stx >> sty >> enx >> eny;
    
    dp.rsz(2);
    dp[0].emp(stx, sty);
    
    for (int i = 0; i < k - 1; ++i)
    {
        int h; cin >> h;

        for (int i = 0; i < h; ++i)
        {
            int x, y;
            cin >> x >> y;
            dp[1].emp(x, y);
        }

        proceed();
    }
           
    dp[1].emp(enx, eny);
    
    proceed();

    prt(dp[0][0].val);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 480 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 480 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 532 KB Output is correct
5 Correct 2 ms 664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 664 KB Output is correct
2 Correct 38 ms 820 KB Output is correct
3 Correct 36 ms 1076 KB Output is correct
4 Correct 39 ms 1316 KB Output is correct
5 Correct 39 ms 1580 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1580 KB Output is correct
2 Correct 45 ms 1580 KB Output is correct
3 Correct 41 ms 1656 KB Output is correct
4 Correct 44 ms 2040 KB Output is correct
5 Correct 42 ms 2436 KB Output is correct