#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cmath>
using std::swap;
using std::vector;
using std::max;
int n, m, r, c;
long long a[1000][1000];
long long b[1000][1000];
struct bigint {
static const long long B = 100000000ll;
static const int len = 20;
long long a[len];
int sign;
bigint(long long x = 0) {
for (int i=0; i<len; i++) a[i] = 0;
a[0] = abs(x);
sign = x>=0 ? 1 : -1;
for (int i=0; i<len-1; i++) {
a[i+1] += a[i] / B;
a[i] %= B;
}
}
bool zero()
{
for (int i=0; i<len; i++) if (a[i]) return false;
return true;
}
bigint bigabs() { bigint res(*this); res.sign = 1; return res; }
bigint operator + (bigint r)
{
if (sign == -1 && r.sign == -1) return -(-*this + -r);
if (sign == -1) return r - -*this;
if (r.sign == -1) return *this - r;
bigint res;
res.sign = 1;
for (int i=0; i<len; i++)
res.a[i] = a[i] + r.a[i];
for (int i=0; i<len-1; i++) {
res.a[i+1] += res.a[i] / B;
res.a[i] %= B;
}
return res;
}
bigint operator - (bigint r)
{
if (sign == -1 && r.sign == 1) return -(-*this + r);
if (sign == -1) return -(-*this - -r);
if (sign == 1 && r.sign == -1) return *this + -r;
if (bigabs() < r.bigabs()) return -(r - *this);
bigint res;
res.sign = 1;
for (int i=0; i<len; i++)
res.a[i] = a[i] - r.a[i];
for (int i=0; i<len-1; i++) {
while (res.a[i] < 0) {
res.a[i] += B;
res.a[i+1] -= 1;
}
}
for (int i=0; i<len-1; i++) {
res.a[i+1] += res.a[i] / B;
res.a[i] %= B;
}
return res;
}
bigint operator - () { bigint res(*this); res.sign *= -1; return res; }
bigint operator * (bigint r)
{
bigint res;
res.sign = sign * r.sign;
for (int i=0; i<len; i++) for (int j=0; j<len; j++) if (i+j<len)
res.a[i+j] += a[i] * r.a[j];
for (int i=0; i<len-1; i++) {
res.a[i+1] += res.a[i] / B;
res.a[i] %= B;
}
return res;
}
bool operator < (bigint r) { // assume both >= 0
for (int i=len-1; i>=0; i--)
if (a[i] != r.a[i])
return a[i] < r.a[i];
return false;
}
};
struct bigdouble {
bigint a, b;
bigdouble(bigint a=0, bigint b=1) : a(a), b(b) {}
bool zero() { return a.zero(); }
bigdouble operator * (const bigdouble& r)
{
return bigdouble(a * r.a, b * r.b);
}
bigdouble operator / (const bigdouble& r)
{
return bigdouble(a * r.b, b * r.a);
}
bigdouble operator - (const bigdouble& r)
{
return bigdouble(a * r.b - b * r.a, b * r.b);
}
};
double s;
bool zero(double v)
{
double eps = 1e-4;
return -eps <= v && v <= eps;
}
int rk(bigdouble m[][3])
{
int n = 3;
int r = 0;
for (int i=0; i<n; i++) {
bool f = false;
for (int j=r; j<n; j++) {
if (!m[j][r].zero()) {
f = true;
for (int k=0; k<n; k++)
swap(m[j][k], m[r][k]);
break;
}
}
if (f) {
for (int j=r+1; j<n; j++) {
bigdouble mul = m[j][i] / m[r][i];
for (int k=0; k<n; k++)
m[j][k] = m[j][k] - mul * m[r][k];
}
r++;
}
}
return r;
}
int rk(bigdouble m11, bigdouble m12, bigdouble m13, bigdouble m22, bigdouble m23, bigdouble m33)
{
bigdouble m21 = m12;
bigdouble m31 = m13;
bigdouble m32 = m23;
bigdouble m[3][3] = {m11, m12, m13, m21, m22, m23, m31, m32, m33};
return rk(m);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=0; i<n; i++) for (int j=0; j<m; j++) scanf("%lld", &a[i][j]);
scanf("%d%d", &r, &c);
for (int i=0; i<r; i++) for (int j=0; j<c; j++) scanf("%lld", &b[i][j]);
int ans = 0;
for (int i=0; i<=n-r; i++) {
for (int j=0; j<=m-c; j++) {
bigint ass, abs, bss, as, bs, os;
for (int k=0; k<r; k++) {
for (int l=0; l<c; l++) {
ass = ass + a[i+k][j+l] * a[i+k][j+l];
abs = abs + a[i+k][j+l] * b[k][l];
bss = bss + b[k][l] * b[k][l];
as = as + a[i+k][j+l];
bs = bs + b[k][l];
os = os + bigint(1);
}
}
if (rk(ass, as, abs, os, bs, bss) <= 2)
ans++;
}
}
printf("%d\n", ans);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
525 ms |
16736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
