1073C : Vasya and Robot

풀이

널 향한 내 사랑은 여기까진가 봐.
그 사람 곁에서 행복하길 바라.

코드

#include <cstdio>

int n, ex, ey, x[200002], y[200002];
char s[200002];

int abs(int x) { return x < 0 ? -x : x; }

void f(char c, int &x, int &y) {
    if (c == 'U') y++; if (c == 'D') y--;
    if (c == 'L') x--; if (c == 'R') x++;
}

int main() {
    scanf("%d %s %d %d", &n, s+1, &ex, &ey);
    for (int i = 1; i <= n; i++) {
        f(s[i], x[i], y[i]);
        x[i] += x[i-1];
        y[i] += y[i-1];
    }

    int lft = 0, rgt = n, res = -1;
    while (lft <= rgt) {
        int mid = (lft + rgt) / 2;
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            if (i < mid) continue;
            int dst = abs(ex-(x[n]-x[i]+x[i-mid])) + abs(ey-(y[n]-y[i]+y[i-mid]));
            if (dst <= mid && (mid-dst)%2 == 0) {
                flag = 1;
                break;
            }
        }
        if (flag) {
            rgt = mid - 1;
            res = mid;
        }
        else {
            lft = mid + 1;
        }
    }

    printf("%d\n", res);

    return 0;
}
wookje.kwon's profile image

wookje.kwon

2018-11-06 22:58

Read more posts by this author