• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Aug 21st, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define F first
3. #define S second
4. using namespace std;
5. using ll = long long int;
6. using ii = pair<int, int>;
7. using vi = vector<int>;
8. using vii = vector<ii>;
9. using graph = vector<vi>;
10. const int MAXN = 2e3 + 5;
11. const int INF = 0x3f3f3f3f;
12. const int mod =998244853;
13.
14. int ord[] = {1, 2, 3};
15. int x, y, xt, yt;
16. bool work(int t, int a, int b, int at, int bt) {
17.     return abs(a-at)+ abs(b-bt) <= 2*t;
18. }
19.
20. int bbin(int a, int b, int at, int bt, int w) {
21.     int ini = 1, fim = 3e5, mid, ans = INF;
22.     while (ini <= fim) {
23.         mid = ini + fim >> 1;
24.         if (work(mid,a ,b, at+mid*xt[w], bt+mid*yt[w])) {
25.             ans = mid;
26.             fim = mid-1;
27.         } else {
28.             ini = mid+1;
29.         }
30.     }
31.     return ans;
32. }
33.
34. int main() {
35.     int n, m;
36.     int a, b;
37.     int ans, t;
38.     char c;
39.     while (scanf("%d %d", &n, &m) != EOF && n) {
40.         for (int i = 1; i<=3; ++i) {
41.             scanf("%d %d %c", &a, &b, &c);
42.             yt[i] = c == 'C';
43.             xt[i] = c == 'D';
44.             x[i] = a, y[i] = b;
45.         }
46.
47.         ans = INF;
48.         do {
49.             ii last = {n, m};
50.             t = 0;
51.             for (int i = 0, w; i<3; ++i) {
52.                 w = ord[i];
53.                 t += bbin(last.F, last.S, x[w]+t*xt[w], y[w]+t*yt[w], w);
54.                 last = {x[w]+t*xt[w], y[w]+t*yt[w]};
55.             }
56.             ans = min(ans, t);
57.         } while (next_permutation(ord, ord+3));
58.         printf("%d\n", ans);
59.     }
60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top