제출 #18050

#제출 시각아이디문제언어결과실행 시간메모리
18050tncks0121오벨리스크 (NOI14_obelisk)C++14
25 / 25
90 ms1900 KiB
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <time.h> #include <functional> #include <numeric> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; const int K_ = 505; int K, M; int sx, sy, ex, ey; vector< tuple<int, int> > holes[K_]; ll tb[K_][105]; ll dist (ll dx, ll dy) { if(dx < 0) dx = -dx; if(dy < 0) dy = -dy; // 세로로 세운 (0,0)에서 세로로 세운 (dx, dy)까지 몇 번을 굴려야 하는가? // 한칸짜리 : 자명 if(M == 1) return dx + dy; // 그외: 어쩌지? ll ret = (ll)1e14; ll big_x = dx / (M + 1), big_y = dy / (M + 1); for(int px = 0; px <= 1; px++) { for(int py = 0; py <= 1; py++) { big_x += px; big_y += py; ll tmp = (2 * big_x) + (2 * big_y); ll small_x = dx - big_x * (M + 1); if(small_x < 0) small_x = -small_x; if(small_x > 0) tmp += small_x + (big_y > 0 ? 0 : 2); ll small_y = dy - big_y * (M + 1); if(small_y < 0) small_y = -small_y; if(small_y > 0) tmp += small_y + (big_x > 0 ? 0 : 2); if(tmp < ret) ret = tmp; big_x -= px; big_y -= py; } } return ret; } int main() { scanf("%d%d", &K, &M); { scanf("%d%d%d%d", &sx, &sy, &ex, &ey); holes[K-1].push_back( tie(ex, ey) ); } for(int i = 0; i+1 < K; i++) { int h; scanf("%d", &h); while(h--) { int x, y; scanf("%d%d", &x, &y); holes[i].push_back( tie(x, y) ); } } { // init for(int i = 0; i < holes[0].size(); i++) { int xi, yi; tie(xi, yi) = holes[0][i]; tb[0][i] = dist(xi - sx, yi - sy); } for(int f = 1; f < K; f++) { for(int i = 0; i < holes[f].size(); i++) tb[f][i] = (ll)1e13; } } for(int f = 0; f+1 < K; f++) { for(int i = 0; i < holes[f].size(); i++) { int xi, yi; tie(xi, yi) = holes[f][i]; for(int j = 0; j < holes[f+1].size(); j++) { int xj, yj; tie(xj, yj) = holes[f+1][j]; tb[f+1][j] = min(tb[f+1][j], tb[f][i] + dist(xi - xj, yi - yj)); } } } printf("%lld\n", tb[K-1][0]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...