Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <set>
- #include <map>
- #include <sstream>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <fstream>
- #include <unordered_map>
- #include <cassert>
- #include <ctime>
- #define lol long long
- using namespace std;
- const int INF = 1e9;
- int dp[505][343 * 8];
- int precalc[343 * 8];
- vector<pair<int, int> > masks[8];
- int diff(int a1, int b1)
- {
- return a1 > b1 ? a1 - b1 : 0;
- }
- int diff(int mask1, int mask2, int a1, int a2, int a3, int a4, int a5, int a6)
- {
- int x = mask1 % 7;
- int y = mask1 / 7 % 7;
- int z = mask1 / 49 % 7;
- int b1, b2, b3, b4, b5, b6;
- b1 = b2 = b3 = b4 = b5 = b6 = 0;
- (mask2 & 1 ? b1 : b6) = x;
- (mask2 & 2 ? b2 : b5) = y;
- (mask2 & 4 ? b3 : b4) = z;
- return diff(a1, b1) + diff(a2, b2) + diff(a3, b3) + diff(a4, b4) + diff(a5,
- b5) + diff(a6, b6);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- int n;
- cin >> n;
- vector<string> v(n + 1, "");
- vector<char> mx(n + 1, '0');
- for (int i = 1; i <= n; ++i)
- {
- cin >> v[i];
- for (int j = 0; j < 7; ++j)
- mx[i] = max(mx[i], v[i][j]);
- }
- for (int i = 0; i < 343; ++i)
- {
- int a1, a2, a3, a4, a5, a6;
- a1 = a2 = a3 = a4 = a5 = a6 = 0;
- int f = i % 7;
- int s = i / 7 % 7;
- int t = i / 7 / 7 % 7;
- for (int j = 0; j < 8; ++j)
- {
- int p = i * 8 + j;
- (j & 1 ? a1 : a6) = f;
- (j & 2 ? a2 : a5) = s;
- (j & 4 ? a3 : a4) = t;
- int k = 0;
- k += a1 * 1 + a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5 + a6 * 6;
- k %= 7;
- precalc[p] = k;
- masks[k].push_back({p, a1 + a2 + a3 + a4 + a5 + a6});
- }
- }
- for (int i = 1; i <= n; ++i)
- {
- for (int j = 0; j < 343 * 8; ++j)
- dp[i][j] = 1e9;
- }
- for (int j = 0; j < 7; ++j)
- {
- if (v[1][j] == mx[1])
- {
- for (auto mask : masks[j])
- dp[1][mask.first] = mask.second;
- }
- }
- for (int i = 1; i < n; ++i)
- {
- for (int j = 0; j < 343; ++j)
- {
- for (int j_ = 0; j_ < 8; ++j_)
- {
- if (dp[i][j * 8 + j_] != 1e9)
- {
- for (int nx_mask = 0; nx_mask < 49; ++nx_mask)
- {
- for (int k = 0; k < 4; ++k)
- {
- int a1, a2, a3, a4, a5, a6;
- a1 = a2 = a3 = a4 = a5 = a6 = 0;
- int f = j % 7;
- int s = j / 7 % 7;
- (k & 1 ? a2 : a5) = f;
- (k & 2 ? a3 : a4) = s;
- for (int jj = 0; jj < 7; ++jj)
- {
- if (v[i + 1][jj] == mx[i + 1])
- {
- int cur = (a2 * 2 + a3 * 3 + a4 * 4 + a5 * 5) % 7;
- // jj = cur + need % 7
- int need = (jj - cur + 7) % 7;
- {
- a1 = need;
- a6 = 0;
- int mask = (nx_mask * 7 + (a1 + a6)) * 8 + (k << 1) + 1;
- int d = diff(j, j_, a1, a2, a3, a4, a5, a6);
- dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][j * 8 + j_] + d);
- }
- {
- a1 = 0;
- a6 = 7 - need;
- int mask = (nx_mask * 7 + (a1 + a6)) * 8 + (k << 1);
- int d = diff(j, j_, a1, a2, a3, a4, a5, a6);
- dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][j * 8 + j_] + d);
- }
- }
- }
- }
- }
- }
- }
- }
- }
- cout << dp[3][49 * 8 + 4] << endl;
- int mn = 1e9;
- for (int i = 0; i < 343 * 8; ++i)
- {
- mn = min(dp[n][i], mn);
- }
- cout << mn;
- }
- /*
- *
- *
- *
- 6
- 9689331
- 1758824
- 3546327
- 5682494
- 9128291
- 9443696
- 7
- 5941186
- 3871463
- 8156346
- 9925977
- 8836125
- 9999999
- 5987743
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement