제출 #778419

#제출 시각아이디문제언어결과실행 시간메모리
778419andrei_iorgulescuT-Covering (eJOI19_covering)C++14
0 / 100
331 ms392 KiB
#include <bits/stdc++.h> using namespace std; int n,m,k; vector<vector<int>>a; vector<vector<bool>>b; vector<pair<int,int>>v; int ori[15]; pair<int,int>cell[10][10]; int ans = -1; void afis() { bool bb = true; int sm = 0; for (int i = 1; i <= k; i++) { bool boo = true; for (int j = 1; j <= 4; j++) { int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second; if (l == 0 or l == n + 1 or c == 0 or c == m + 1) boo = false,bb = false; } if (boo == true) { for (int j = 1; j <= 4; j++) { int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second; if (!b[l][c]) b[l][c] = true,sm += a[l][c]; else bb = false; } } } for (int i = 1; i <= k; i++) { bool boo = true; for (int j = 1; j <= 4; j++) { int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second; if (l == 0 or l == n + 1 or c == 0 or c == m + 1) boo = false; } if (boo == true) { for (int j = 1; j <= 4; j++) { int l = v[i].first + cell[ori[i]][j].first,c = v[i].second + cell[ori[i]][j].second; b[l][c] = false; } } } if (bb == true) ans = max(ans,sm); } void bkt(int pos) { if (pos == k + 1) afis(); else { for (int i = 1; i <= 4; i++) { ori[pos] = i; bkt(pos + 1); } } } void solve_small() { b.resize(n + 1); for (int i = 1; i <= n; i++) b[i].resize(m + 1); bkt(1); if (ans == -1) cout << "No"; else cout << ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; a.resize(n + 1); for (int i = 1; i <= n; i++) { a[i].resize(m + 1); for (int j = 1; j <= m; j++) cin >> a[i][j]; } cin >> k; v.resize(k + 1); for (int i = 1; i <= k; i++) cin >> v[i].first >> v[i].second,v[i].first++,v[i].second++; cell[1][1] = {0,0},cell[1][2] = {0,-1},cell[1][3] = {0,1},cell[1][4] = {1,0}; cell[2][1] = {0,0},cell[2][2] = {0,-1},cell[2][3] = {0,1},cell[1][4] = {-1,0}; cell[3][1] = {0,0},cell[3][2] = {-1,0},cell[3][3] = {0,1},cell[3][4] = {1,0}; cell[4][1] = {0,0},cell[4][2] = {-1,0},cell[4][3] = {0,-1},cell[4][4] = {1,0}; if (k <= 10) { solve_small(); return 0; } /*if (all_same_row() == true) { solve_all_same_row(); return 0; } else if (all_subtask2() == true) { solve_subtask2(); return 0; } else { solve_normal; return 0; }*/ return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...