#include #include #include #include #include #include #include using namespace std; typedef long long ll; int M, N, P, Q, E, timer, konrow, koncol; int A[501][501], B[501][501], R[501], C[501], temp[501]; ll sumrow[501], sumcol[501]; struct result{ int rc, mn, k; }res[50000001]; ll PartSumRow(int m, int k) { ll a = 0; for (int i = 1; i <= N - k; i++) { a += A[m][i + k] * B[m][i]; } for (int i = 1; i <= k; i++) { a += A[m][i] * B[m][N - k + i]; } return a; } ll PartSumCol(int n, int k) { ll a = 0; for (int i = 1; i <= M - k; i++) { a += A[i + k][n] * B[i][n]; } for (int i = 1; i <= k; i++) { a += A[i][n] * B[M - k + i][n]; } return a; } void SetSumRow() { for (int i = 1; i <= M; i++) { sumrow[i] = PartSumRow(i, 0); } } void SetSumCol() { for (int i = 1; i <= N; i++) { sumcol[i] = PartSumCol(i, 0); } } void SetNewRow(int m, int k) { for (int i = 1; i <= N; i++) temp[i] = A[m][i]; for (int i = 1; i <= N - k; i++) A[m][i] = temp[i + k]; for (int i = 1; i <= k; i++) A[m][N - k + i] = temp[i]; } void SetNewCol(int n, int k) { for (int i = 1; i <= M; i++) temp[i] = A[i][n]; for (int i = 1; i <= M - k; i++) A[i][n] = temp[i + k]; for (int i = 1; i <= k; i++) A[M - k + i][n] = temp[i]; } void ScanRow() { SetSumRow(); konrow = 0; int temp_m, temp_k, val; ll temp_sum, ts; for (int i = 1; i <= M; i++) { if (GetTickCount() - timer > 4750) { E++; return; } temp_sum = sumrow[i]; val = 0; for (int k = 0; k < N; k++) { ts = PartSumRow(i, k) + R[i]; if (ts < temp_sum) { temp_m = i; temp_k = k; temp_sum = ts; val++; } } if (val) { Q++; if (Q > P) { E++; Q--; return; } res[Q].rc = 1; res[Q].mn = temp_m; res[Q].k = temp_k; SetNewRow(i, temp_k); sumrow[i] = PartSumRow(i, 0); konrow++; } } } void ScanCol() { SetSumCol(); koncol = 0; int temp_n, temp_k, val; ll temp_sum, ts; for (int i = 1; i <= N; i++) { if (GetTickCount() - timer > 4750) { E++; return; } temp_sum = sumcol[i]; val = 0; for (int k = 0; k < M; k++) { ts = PartSumCol(i, k) + C[i]; if (ts < temp_sum) { temp_n = i; temp_k = k; temp_sum = ts; val++; } } if (val) { Q++; if (Q > P) { E++; Q--; return; } res[Q].rc = 2; res[Q].mn = temp_n; res[Q].k = temp_k; SetNewCol(i, temp_k); sumcol[i] = PartSumCol(i, 0); koncol++; } } } void solve() { while (E == 0) { if (GetTickCount() - timer > 4750)return; ScanRow(); if (GetTickCount() - timer > 4750)return; ScanCol(); if (konrow == 0 && koncol == 0)return; } } void Input() { FILE *in = fopen("movethematrix.in", "r"); fscanf(in, "%i %i %i\n", &M, &N, &P); for (int i = 1; i <= M; i++) { fscanf(in, "%i ", &R[i]); } for (int i = 1; i <= N; i++) { fscanf(in, "%i ", &C[i]); } for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { fscanf(in, "%i ", &A[i][j]); } } for (int i = 1; i <= M; i++) { for (int j = 1; j <= N; j++) { fscanf(in, "%i ", &B[i][j]); } } } void Output() { FILE *out = fopen("movethematrix.out", "w"); fprintf(out, "%i\n", Q); for (int i = 1; i <= Q; i++) { if (res[i].rc == 1) { fprintf(out, "%s %i %i\n", "R", res[i].mn, res[i].k); } else { fprintf(out, "%s %i %i\n", "C", res[i].mn, res[i].k); } } } int main() { timer = GetTickCount(); Input(); solve(); Output(); return 0; }