Cod sursa(job #1258858)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 noiembrie 2014 15:12:45
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <map>

int a[550][550];
long long sum[550][550];
int n;
int l1, c1, l2, c2;
long long v[9];

inline long long get_sum(int i1, int i2, int j1, int j2) {
  return sum[i2][j2] - sum[i1 - 1][j2] - sum[i2][j1 - 1] + sum[i1 - 1][j1 - 1];
}

bool all_zeros(const std::map<long long, int>& m) {
  for (typename std::map<long long, int>::const_iterator it = m.begin();
       it != m.end(); ++it) {
    if (it->second != 0) {
      return false;
    }
  }
  return true;
}

void solve() {
  // Count vectors.
  std::map<long long, int> cts;
  for (int i = 0; i < 9; ++i) {
    cts[v[i]]++;
  }

  // The backtracking.
  for (l1 = 1; l1 <= n - 2; ++l1) {
    for (c1 = 1; c1 <= n - 2; ++c1) {
      int s1 = sum[l1][c1];
      if (cts[s1]) {
        cts[s1]--;
        for (l2 = l1 + 1; l2 <= n - 1; ++l2) {
          long long s2 = sum[l2][c1] - sum[l1][c1];
          long long s3 = sum[n][c1] - sum[l2][c1];
          if (cts[s2]) {
            cts[s2]--;
            if (cts[s3]) {
              cts[s3]--;
              for (c2 = c1 + 1; c2 <= n - 1; ++c2) {
                cts[get_sum(1, l1, c1 + 1, c2)]--;
                cts[get_sum(l1 + 1, l2, c1 + 1, c2)]--;
                cts[get_sum(l2 + 1, n, c1 + 1, c2)]--;
                cts[get_sum(1, l1, c2 + 1, n)]--;
                cts[get_sum(l1 + 1, l2, c2 + 1, n)]--;
                cts[get_sum(l2 + 1, n, c2 + 1, n)]--;
                if (all_zeros(cts)) {
                  return;
                }
                cts[get_sum(1, l1, c1 + 1, c2)]++;
                cts[get_sum(l1 + 1, l2, c1 + 1, c2)]++;
                cts[get_sum(l2 + 1, n, c1 + 1, c2)]++;
                cts[get_sum(1, l1, c2 + 1, n)]++;
                cts[get_sum(l1 + 1, l2, c2 + 1, n)]++;
                cts[get_sum(l2 + 1, n, c2 + 1, n)]++;
              }
              cts[s3]++;
            }
            cts[s2]++;
          }
        }
        cts[s1]++;
      }
    }
  }
}

int main()
{
  std::ifstream in("zone.in");
  std::ofstream out("zone.out");

  in >> n;
  for (int i = 0; i < 9; ++i) {
    in >> v[i];
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      in >> a[i][j];
      sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
  }

  solve();

  out << l1 << " " << l2 << " " << c1 << " " << c2 << std::endl;

  in.close();
  out.close();

  return 0;
}