#include #include #include #include #include #include using namespace std; typedef vector> matrix; chrono::steady_clock::time_point end_time = chrono::steady_clock::now() + chrono::milliseconds(4800); bool can_continue() { return chrono::steady_clock::now() < end_time; } struct shift { int i, j, d; }; struct sol { matrix A, B; int M, N, P; vector R, C; // per row and column costs vector RS, CS; // per row and column sums vector M1, M2; // move operations row then col void read(ifstream& fin) { fin >> M >> N >> P; R.resize(M); RS.resize(M); C.resize(N); CS.resize(N); for (int i = 0; i < M; i++) fin >> R[i]; for (int j = 0; j < N; j++) fin >> C[j]; A.resize(M); B.resize(M); for (int i = 0; i < M; i++) { A[i].resize(N); for (int j = 0; j < N; j++) fin >> A[i][j]; } for (int i = 0; i < M; i++) { B[i].resize(N); for (int j = 0; j < N; j++) fin >> B[i][j]; } } int calcRowSum(const matrix& a, const matrix& b, int r, int k) { int total = 0; for (int j = 0; j < N; j++) { int s = a[r][(j + k) % N] * b[r][j]; total += s; } return total; } int calcColSum(const matrix& a, const matrix& b, int k, int c) { int total = 0; for (int i = 0; i < M; i++) { int s = a[(i + k) % M][c] * b[i][c]; total += s; } return total; } void calcBestRowMoves(const matrix& a, const matrix& b, vector& sh) { for (int i = 0; i < M && can_continue(); i++) { int zero = calcRowSum(a, b, i, 0), minj = 0, min = zero; for (int j = 1; j < N; j++) { int rij = calcRowSum(a, b, i, j); if (min > rij) { minj = j; min = rij; } } if (minj > 0 && zero - min > R[i]) sh.push_back({ i, -minj, zero - min - R[i] }); } } void calcBestColMoves(const matrix& a, const matrix& b, vector& sh) { for (int j = 0; j < N && can_continue(); j++) { int zero = calcColSum(a, b, 0, j), mini = 0, min = zero; for (int i = 1; i < M; i++) { int cij = calcColSum(a, b, i, j); if (min > cij) { mini = i; min = cij; } } if (mini > 0 && zero - min > C[j]) sh.push_back({ -mini, j, zero - min - C[j] }); } } void applyMoves(matrix& a, vector& sh) { for (shift& s : sh) { if (s.j < 0) { int k = -s.j; vector b; b.resize(k); for (int j = 0; j < k; j++) b[j] = a[s.i][j]; for (int j = 0, o = k; j < N - k; j++, o++) a[s.i][j] = a[s.i][o]; for (int j = 0, o = N - k; j < k; j++, o++) a[s.i][o] = b[j]; } else { int k = -s.i; vector b; b.resize(k); for (int i = 0; i < k; i++) b[i] = a[i][s.j]; for (int i = 0, o = k; i < M - k; i++, o++) a[i][s.j] = a[o][s.j]; for (int i = 0, o = M - k; i < k; i++, o++) a[o][s.j] = b[i]; } } } bool iter(matrix& a, bool rows, vector& TM) { if (can_continue()) { vector IM; if (rows) calcBestRowMoves(a, B, IM); else calcBestColMoves(a, B, IM); if (!IM.empty()) { applyMoves(a, IM); sort(IM.begin(), IM.end(), [](shift& l, shift& r)-> bool { return l.d > r.d; }); auto tms = TM.size(); TM.resize(tms + IM.size()); copy(IM.begin(), IM.end(), TM.begin() + tms); return true; } } return false; } void solve() { matrix A1(A), A2(A); bool c1r = true, c1c = true, c2r = true, c2c = true, d1 = false, d2 = true; while (c1r || c1c || c2r || c2c) { (d1 ? c1r : c1c) = iter(A1, d1, M1); d1 = !d1; (d2 ? c2r : c2c) = iter(A2, d2, M2); d2 = !d2; } } void write(ofstream& fout) { int t1 = 0, t2 = 0; for (int i = 0, c = min(P, (int)M1.size()); i < c; i++) t1 += M1[i].d; for (int i = 0, c = min(P, (int)M2.size()); i < c; i++) t2 += M2[i].d; auto& sh = t1 > t2 ? M1 : M2; int cnt = 0; fout << min(P, (int)sh.size()) << endl; for (auto& s : sh) { if (cnt++ >= P) break; if (s.i < 0) fout << "C " << s.j + 1 << " " << -s.i << endl; else fout << "R " << s.i + 1 << " " << -s.j << endl; } } }; int main() { sol s; ifstream fin("movethematrix.in"); s.read(fin); s.solve(); ofstream fout("movethematrix.out"); s.write(fout); }