Cod sursa(job #1259426)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 noiembrie 2014 23:31:37
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 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) {
      long long s1 = sum[l1][c1];
      if (cts.count(s1) && 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.count(s2) && cts[s2]) {
            cts[s2]--;
            if (cts.count(s3) && cts[s3]) {
              cts[s3]--;
              for (c2 = c1 + 1; c2 <= n - 1; ++c2) {
                long long s4 = sum[l1][c2] - sum[l1][c1];
                long long s5 = get_sum(l1 + 1, l2, c1 + 1, c2);
                long long s6 = get_sum(l2 + 1, n, c1 + 1, c2);
                long long s7 = sum[l1][n] - sum[l1][c2];
                long long s8 = get_sum(l1 + 1, l2, c2 + 1, n);
                long long s9 = get_sum(l2 + 1, n, c2 + 1, n);
                cts[s4]--;
                cts[s5]--;
                cts[s6]--;
                cts[s7]--;
                cts[s8]--;
                cts[s9]--;
                if (all_zeros(cts)) {
                  return;
                }
                cts[s4]++;
                cts[s5]++;
                cts[s6]++;
                cts[s7]++;
                cts[s8]++;
                cts[s9]++;
              }
              cts[s3]++;
            }
            cts[s2]++;
          }
        }
        cts[s1]++;
      }
    }
  }
}

int main()
{
  FILE* in = fopen("zone.in", "r");
  std::ofstream out("zone.out");

  fscanf(in, "%d", &n);
  for (int i = 0; i < 9; ++i) {
    fscanf(in, "%lld", &v[i]);
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      fscanf(in, "%d", &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;

  fclose(in);
  out.close();

  return 0;
}