Submission #1220965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220965		vicvic	OBELISK (NOI14_obelisk)	C++20	25 / 25	61 ms	1352 KiB

obelisk

#include <bits/stdc++.h>
#define int long long
using namespace std;
int k, m;
int dp[505][105];
vector <pair <int, int>> layer[505];
int dist (pair <int, int> a, pair <int, int> b)
{
    int ret=1ll << 60;
    pair <int, int> d={abs (b.first-a.first), abs (b.second-a.second)};
    if (m==1)
        return d.first+d.second;
    int v_x=d.first/(m+1)*(m+1);
    int v_y=d.second/(m+1)*(m+1);
    for (auto p : vector <pair <int, int>>{{v_x, v_y}, {v_x, v_y+m+1}, {v_x+m+1, v_y}, {v_x+m+1, v_y+m+1}})
    {
        int res=p.first/(m+1)*2+p.second/(m+1)*2;
        res+=abs (p.first-d.first)!=0 && p.second==0?2+abs (p.first-d.first):abs (p.first-d.first);
        res+=abs (p.second-d.second)!=0 && p.first==0?2+abs (p.second-d.second):abs (p.second-d.second);
        ret=min (ret, res);
    }
    return ret;
}
int32_t main ()
{
    memset (dp, 0x3f, sizeof(dp));
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> k >> m;
    int s_x, s_y, e_x, e_y;
    cin >> s_x >> s_y >> e_x >> e_y;
    pair <int, int> s={s_x, s_y}, e={e_x, e_y};
    layer[0].push_back (s);
    for (int i=1;i<k;i++)
    {
        int cnt;
        cin >> cnt;
        for (int j=1;j<=cnt;j++)
        {
            int x, y;
            cin >> x >> y;
            layer[i].push_back ({x, y});
        }
    }
    layer[k].push_back (e);
    dp[0][0]=0;
    for (int i=0;i<k;i++)
    {
        for (int j=0;j<layer[i].size();j++)
        {
            for (int k=0;k<layer[i+1].size();k++)
            {
                dp[i+1][k]=min (dp[i+1][k], dp[i][j]+dist (layer[i][j], layer[i+1][k]));
            }
        }
    }
    cout << dp[k][0];
    return 0;
}

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