Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits\stdc++.h>
- using namespace std;
- #define pb push_back
- #define mp make_pair
- typedef long double ld;
- typedef long long ll;
- typedef unsigned long long ull;
- const ld eps = 1e-9;
- const int inf = 1e9;
- inline ld dist(int l, int r, const vector<ld> &x, const vector<ld> &y)
- {
- return sqrt((x[l] - x[r]) * (x[l] - x[r]) + (y[l] - y[r]) * (y[l] - y[r]));
- }
- void solve(int n)
- {
- int tail, hand, foot, body;
- int ktail, khand, kfoot;
- hand = n;
- cin >> body >> foot >> tail;
- cin >> khand >> kfoot >> ktail;
- cin >> n;
- vector<ld> x(n), y(n);
- double temp;
- for (int i = 0; i < n; i++)
- {
- scanf(" %lf", &temp); x[i] = temp;
- scanf(" %lf", &temp); y[i] = temp;
- }
- int dp[khand + 1][kfoot + 1][ktail + 1][n][3];
- for (int i = 0; i <= khand; i++)
- for (int j = 0; j <= kfoot; j++)
- for (int k = 0; k <= ktail; k++)
- for (int pos = 0; pos < n; pos++)
- for (int wtf = 0; wtf < 3; wtf++)
- dp[i][j][k][pos][wtf] = inf;
- if (khand >= 1)
- dp[1][0][0][0][0] = 0;
- if (kfoot >= 1)
- dp[0][1][0][0][1] = 0;
- if (ktail >= 1)
- dp[0][0][1][0][2] = 0;
- for (int len = 1; len <= n; len++)
- for (int i = 0; i <= khand; i++)
- for (int j = 0; j <= kfoot; j++)
- for (int k = 0; k <= ktail; k++)
- for (int start = 0; start < n; start++)
- for (int where = 0; where < 3; where++)
- for (int to = 0; to < 3; to++)
- for (int dest = 0; dest < n; dest++)
- if (dp[i][j][k][start][where] < inf)
- {
- if (where == 2 && to == 2)
- continue;
- ld reallen = dist(start, dest, x, y);
- ll pathlen = body;
- if (where == 0)
- pathlen += hand;
- else if (where == 1)
- pathlen += foot;
- else if (where == 2)
- pathlen += tail;
- if (to == 0)
- pathlen += hand;
- else if (to == 1)
- pathlen += foot;
- else if (to == 2)
- pathlen += tail;
- if (pathlen + eps >= reallen)
- {
- bool ok = false;
- ok |= (i < khand && to == 0);
- ok |= (j < kfoot && to == 1);
- ok |= (k < ktail && to == 2);
- if (!ok)
- continue;
- int ni = i;
- int nj = j;
- int nk = k;
- if (to == 0)
- ni++;
- if (to == 1)
- nj++;
- if (to == 2)
- nk++;
- int &reef = dp[ni][nj][nk][dest][to];
- if (reef > dp[i][j][k][start][where] + 1)
- reef = dp[i][j][k][start][where] + 1;
- }
- }
- int ans = inf;
- for (int i = 0; i <= khand; i++)
- for (int j = 0; j <= kfoot; j++)
- for (int k = 0; k <= ktail; k++)
- for (int where = 0; where < 3; where++)
- ans = min(ans, dp[i][j][k][n - 1][where]);
- if (ans == inf)
- printf("-1\n");
- else
- printf("%d\n", ans + 1);
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- // freopen("input.txt", "rt", stdin);
- // freopen("output.txt", "w", stdout);
- #endif // ONLINE_JUDGE
- freopen("tote.in", "rt", stdin);
- freopen("tote.out", "w", stdout);
- int n;
- while (cin >> n)
- solve(n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement