Advertisement
Gosunov

Untitled

Oct 7th, 2022
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4. #define int long long
  5.  
  6. const int n = 100;
  7. int dp[n][n];
  8. int p[n][n][2];
  9. char c[n][n];
  10.  
  11. string s = ".-`|=+<(>)^*#@:'#";
  12.  
  13.  
  14. int k = 0;
  15. void print(int x, int y, int a, int b, int f=1) {
  16.     if (a == 0 || b == 0)
  17.         return;
  18.     if (dp[a][b] <= 1 && f) {
  19.         for (int i = x; i < x + a; ++i) {
  20.             for (int j = y; j < y + b; ++j) {
  21.                 c[i][j] = s[k];
  22.             }
  23.         }
  24.         k = (k + 1) % s.size();
  25.         return;
  26.     }
  27.     int cut_x = p[a][b][0];
  28.     int cut_y = p[a][b][1];
  29.     print(x, y, cut_x, cut_y);
  30.     print(x + cut_x, y, a - cut_x, cut_y);
  31.     print(x, y + cut_y, cut_x, b - cut_y);
  32.     print(x + cut_x, y + cut_y, a - cut_x, b - cut_y);
  33. }  
  34.  
  35. void solve() {
  36.     for (int i = 0; i < n; ++i) {
  37.         for (int j = 0; j < n; ++j) {
  38.             dp[i][j] = 1e9;
  39.         }
  40.     }
  41.     for (int i = 1; i < n; ++i) {
  42.         dp[0][i] = 0;
  43.         dp[i][0] = 0;
  44.         dp[1][i] = i;
  45.         p[1][i][0] = 0;
  46.         p[1][i][1] = i - 1;
  47.         dp[i][1] = i;
  48.         p[i][1][0] = i - 1;
  49.         p[i][1][1] = 0;
  50.     }
  51.     for (int a = 2; a < n; ++a) {
  52.         for (int b = 2; b < n; ++b) {
  53.             for (int y = 0; y < b; ++y) {
  54.                 for (int x = 0; x < a; ++x) {
  55.                     int v = dp[x][y] + dp[a - x][y] + dp[x][b - y] + dp[a - x][b - y];
  56.                     if (v <= dp[a][b]) {
  57.                         dp[a][b] = v;
  58.                         p[a][b][0] = x;
  59.                         p[a][b][1] = y;
  60.                     }
  61.                 }
  62.             }
  63.             if (a == b) {
  64.                 dp[a][a] = 1;
  65.             }
  66.         }
  67.     }
  68.     int b = 73;
  69.     print(0, 0, b, b, 0);
  70.     for (int i = 0; i < b; ++i) {
  71.         for (int j = 0; j < b; ++j) {
  72.             cout << c[i][j];
  73.         }
  74.         cout << '\n';
  75.     }
  76. }
  77.  
  78. signed main() {
  79.     ios::sync_with_stdio(0); cin.tie(0);
  80.     solve();
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement