Submission #638557

#TimeUsernameProblemLanguageResultExecution timeMemory
638557ShirleyMT-Covering (eJOI19_covering)C++14
15 / 100
1094 ms724 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<bool> vb; typedef vector<vb> vvb; #define x first #define y second #define pb push_back #define loop(i,s,e) for(int i=s;i<e;i++) #define loopr(i,s,e) for(int i=e-1;i>=s;i--) #define chkmax(a,b) a=max(a,b) #define chkmin(a,b) a=min(a,b) #define all(a) a.begin(),a.end() #define fast {ios_base::sync_with_stdio(false); cin.tie(0);} const int inf = 1e11; const int INF = 1e9; const int mod = 1e9+7; int n,m,k; vvi g; vii sp; vvi st; vvb s; int ans=-1; bool in_limits(int i, int j){ return (i>=0 && i<n && j>=0 && j<m); } int best(int i, int j){ int ans = g[i][j]; vi a; vii d = {{-1,0}, {0,-1}, {0,1}, {1,0}}; for(auto it : d){ int di = it.x, dj = it.y; int ni = i+di, nj = j+dj; if(!in_limits(ni,nj)) continue; a.pb(g[ni][nj]); } if(a.size() <=2) return -1; sort(all(a), greater<int>()); loop(ind,0,3) ans += a[ind]; return ans; } int get_from_st(int i, int j, int st){ if(st == -1) return best(i,j); int ans = g[i][j]; int u = in_limits(i-1,j) ? g[i-1][j] : -inf; int d = in_limits(i+1,j) ? g[i+1][j] : -inf; int l = in_limits(i,j-1) ? g[i][j-1] : -inf; int ri = in_limits(i,j+1) ? g[i][j+1] : -inf; if(st==0) ans += u+d+l; if(st == 1) ans += u+d+ri; else if(st==2) ans += u+l+ri; else if(st==3) ans += d+l+ri; return ans; } void put(int i, int j, int state){ if(st[i][j] != -1 && st[i][j] != state){ cout << "No"; exit(0); } st[i][j] = state; } bool ins(const ii& cur, set<ii>& taken){ if(cur == ii{-1,-1}) return false; if(taken.find(cur) != taken.end()) return false; taken.insert(cur); return true; } bool legal(){ set<ii> taken; loop(i,0,k){ int r = sp[i].x, c = sp[i].y; ii u = in_limits(r-1,c) ? ii{r-1,c} : ii{-1,-1}; ii d = in_limits(r+1,c) ? ii{r+1,c} : ii{-1,-1}; ii l = in_limits(r,c-1) ? ii{r,c-1} : ii{-1,-1}; ii ri = in_limits(r,c+1) ? ii{r,c+1} : ii{-1,-1}; if(st[r][c] == 0){ if(!ins(u,taken) || !ins(d, taken) || !ins(l, taken)) return false; } if(st[r][c] == 1){ if(!ins(u,taken) || !ins(d, taken) || !ins(ri, taken)) return false; } if(st[r][c] == 2){ if(!ins(u,taken) || !ins(l, taken) || !ins(ri, taken)) return false; } if(st[r][c] == 3){ if(!ins(d,taken) || !ins(l, taken) || !ins(ri, taken)) return false; } } return true; } void calc(int ind, int tot){ if(ind==k){ if(!legal()) return; chkmax(ans, tot); return; } int r = sp[ind].x, c = sp[ind].y; loop(state,0,4){ st[r][c] = state; int cur_add = get_from_st(r,c,state); if(cur_add < 0) continue; calc(ind+1, tot+cur_add); st[r][c] = -1; } } int32_t main() { fast; cin >> n >> m; g.resize(n, vi(m)); st.resize(n, vi(m, -1)); s.resize(n, vb(m, -1)); loop(i,0,n) loop(j,0,m) cin >> g[i][j]; cin >> k; sp.resize(k); loop(i,0,k){ cin >> sp[i].x >> sp[i].y; s[sp[i].x][sp[i].y]=true; } calc(0,0); if(ans<0) cout << "No"; else cout << ans; 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...