Submission #638517

#TimeUsernameProblemLanguageResultExecution timeMemory
638517ShirleyMT-Covering (eJOI19_covering)C++14
25 / 100
73 ms19744 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 = 1e17; const int INF = 1e9; const int mod = 1e9+7; int n,m,k; vvi g; vi r,c; vvi st; bool in_limits(int i, int j){ return (i>=0 && i<n && j>=0 && j<m); } int best(int i, int j){ /*int op1=g[i][j], op2=0, op3=0, op4=0; op2 = op3 = op4 = op1; 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; bool bad = 0; if(!in_limits(ni,nj)) bad=1; if(di==-1){ if(bad) op1 = op2= op4 = -inf; else { op1 += g[ni][nj]; op2 += g[ni][nj]; op4 += g[ni][nj]; } } if(di==1){ if(bad) op2 = op3= op4 = -inf; else { op2 += g[ni][nj]; op3 += g[ni][nj]; op4 += g[ni][nj]; } } if(dj==-1){ if(bad) op1 = op3= op4 = -inf; else { op1 += g[ni][nj]; op3 += g[ni][nj]; op4 += g[ni][nj]; } } if(dj==1) { if (bad) op1 = op2 = op3 = -inf; else { op1 += g[ni][nj]; op2 += g[ni][nj]; op3 += g[ni][nj]; } } } int ans = max({op1,op2,op3,op4}); return ans;*/ 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){ if(st[i][j] == -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[i][j] == 1) ans += u+l+ri; else if(st[i][j]==2) ans += u+d+ri; else if(st[i][j]==3) ans += d+l+ri; else ans += u+d+l; if(ans < 0) { cout << "No"; exit(0); } 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; } int32_t main() { fast; cin >> n >> m; g.resize(n, vi(m)); st.resize(n, vi(m, -1)); loop(i,0,n) loop(j,0,m) cin >> g[i][j]; cin >> k; r.resize(k); c.resize(k); loop(i,0,k) cin >> r[i] >> c[i]; int ans = 0; loop(i,0,k){ int r1 = r[i], c1 = c[i]; loop(j,i+1,k){ int r2 = r[j], c2 = c[j]; if(abs(r1-r2) <= 1 && abs(c1-c2) <= 1){ if(c1==c2) { if (r1 == r2 - 1) { put(r1, c1, 1); put(r2, c2, 3); } if (r2 == r1 - 1) { put(r1, c1, 3); put(r2, c2, 1); } } else if(r1==r2){ if(c1 == c2-1){ put(r1,c1,4); put(r2,c2,2); } if(c2 == c1-1){ put(r1,c1,2); put(r2,c2,4); } } else if(r1 < r2){ put(r1,c1,1); put(r2,c2,3); } else if(r2 < r1){ put(r1,c1,3); put(r2,c2,1); } } } } loop(i,0,k){ ans += get_from_st(r[i], c[i]); } 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...