3213:PM3

keyword

行列　C

概要

行列A,B,Cが与えられる。(N<1000)が与えられる。
A*B = Cであるかどうか判定する問題。間違っている場合はどの要素が間違えているか出力する。
メモリの局所性に気をつけてO(N^3)で計算する。普通ならこのオーダーはアウトだけど計算は単純だしメモリも連続しているので何とかなった。

int a[1000][1000], b[1000][1000], c[1000][1000], d[1000][1000];

void main(){
    int n, p, m, i, j, k;
    n = readint();
    p = readint();
    m = readint();
    for(i=0;i<n;++i)
        for(j=0;j<p;++j)
            a[i][j] = readint();
    for(i=0;i<p;++i)
        for(j=0;j<m;++j)
            b[i][j] = readint();
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            c[i][j] = readint();
    for(i=0;i<n;++i)
        for(k=0;k<p;++k)
            for(j=0;j<m;++j)
                d[i][j] += a[i][k]*b[k][j];
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            if(d[i][j] != c[i][j]){
                puts("No");
                printf("%d %d\n",i+1,j+1);
                printf("%d\n",d[i][j]);
                return ;
            }
    puts("Yes");
}