| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053787 | Nickpapadak | T-Covering (eJOI19_covering) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define XX first
#define YY second
const unsigned int MAXK = 1e+6 + 10;
const unsigned int INF = 1e+7 + 10;
vector<vector<int> > grid;
vector<vector<bool> > sgrid;
vector<pair<int,int> > special;
int N,M, K;
int firsSub(){
int ans = 0;
// totalinc = 0/;
for(int i = 0; i<K; ++i){
int c = 0;
int x = special[i].XX, y = special[i].YY;
int u = 0,r=0,l=0,d=0;
r += grid[x+1][y];
r += grid[x][y+1];
r += grid[x][y-1];
l += grid[x-1][y];
l += grid[x][y+1];
l += grid[x][y-1];
d += grid[x-1][y];
d += grid[x+1][y];
d += grid[x][y+1];
u += grid[x-1][y];
u += grid[x+1][y];
u += grid[x][y-1];
// int x = special[i].X, y = special[i].Y;
ans += grid[x][y];
if(x == 1 ||sgrid[x-1][y]){
ans += r;
c++;
}
if(x == M || sgrid[x+1][y]){
ans += l;
c++;
}
if(y == 1 || sgrid[x][y-1]){
ans += d;
c++;
}
if(y == N || sgrid[x][y+1]){
ans += u;
c++;
}
if(c>=2) return -1;
// printf("c: %d \n", c);
if(sgrid[x+1][y+1] || sgrid[x-1][y+1]){
return c == 0 ?u: -1;}
if(sgrid[x+1][y-1] || sgrid[x-1][y+1]){
return c == 0?d: -1;}
if(c==1) continue;
int best = max(l, r);
best = max(best, u);
ans += max(best, d);
// printf("%d s\n", ans);
}
return ans;
}
int solve410(int i, vector<vector<bool> > sgrids, int ans);
int Rleft(int i, vector<vector<bool> > sgrids, int ans){
int x = special[i].XX, y = special[i].YY;
int u = y+1, d = y-1, r = x+1, l = x-1;
if(sgrids[x][u] || sgrids[x][d] || sgrids[l][y]) return -1;
ans += grid[x][y];
ans += grid[x][u];
sgrids[x][u] = 1;
ans += grid[x][d];
sgrids[x][d] = 1;
ans += grid[l][y];
sgrids[l][y] = 1;
return solve410(i+1, sgrids, ans);
}
int Rright(int i, vector<vector<bool> > sgrids, int ans){
int x = special[i].XX, y = special[i].YY;
int u = y+1, d = y-1, r = x+1, l = x-1;
if(sgrids[x][u] || sgrids[x][d] || sgrids[r][y]) return -1;
ans += grid[x][y];
ans += grid[x][u];
sgrids[x][u] = 1;
ans += grid[x][d];
sgrids[x][d] = 1;
ans += grid[r][y];
sgrids[r][y] = 1;
return solve410(i+1, sgrids, ans);
}
int Rup(int i, vector<vector<bool> > sgrids, int ans){
int x = special[i].XX, y = special[i].YY;
int u = y+1, d = y-1, r = x+1, l = x-1;
if(sgrids[x][u] || sgrids[r][y] || sgrids[l][y]) return -1;
ans += grid[x][y];
ans += grid[x][u];
sgrids[x][u] = 1;
ans += grid[r][y];
sgrids[r][y] = 1;
ans += grid[l][y];
sgrids[l][y] = 1;
return solve410(i+1, sgrids, ans);
}
int Rdown(int i, vector<vector<bool> > sgrids, int ans){
int x = special[i].XX, y = special[i].YY;
int u = y+1, d = y-1, r = x+1, l = x-1;
if(sgrids[r][y] || sgrids[x][d] || sgrids[l][y]) return -1;
ans += grid[x][y];
ans += grid[r][y];
sgrids[r][y] = 1;
ans += grid[x][d];
sgrids[x][d] = 1;
ans += grid[l][y];
sgrids[l][y] = 1;
return solve410(i+1, sgrids, ans);
}
int solve410(int i, vector<vector<bool> > sgrids, int ans){
if(i>=K){
// for(int y = 1;y<= N; ++y){
// for(int x = 1;x <= M; ++x)
// cout << sgrids[x][y] << ' ';
// printf("\n");
// }
return ans;
}
// int x = special[i].XX, y = special[i].YY;
// int u = y+1, d = y-1, r = x+1, l = x-1;
// printf("%d ", ans);
return max(max(Rleft(i, sgrids, ans), Rright(i, sgrids, ans)),
max(Rup(i, sgrids, ans), Rdown(i, sgrids, ans)));
}
int sameRow(){
vector<vector<int> > dp(K+1, vector<int>(2, 0));
vector<int> spec;
for(int i = 0; i<K;++i){
spec.push_back(grid[special[i].XX][special[i].YY]);
grid[special[i].XX][special[i].YY] = -INF;
}
grid[0][special[0].YY] = -INF;
grid[M+1][special[0].YY] = -INF;
if(special[0].YY == 1 || special[0].YY == M){
int px = 0, ans = 0;
for(int i =0; i<K;++i){
int x = special[i].XX, y = special.YY;
if(x-px >= 2 || M==x) return -10;
ans += spec[i];
ans += grid[x-1][y] + grid[x+1][y];
ans += special[0].YY == 1? grid[x][y+1]: grid[x][y-1];
}
return ans;
}
for(int i = 1; i<=K;++i){
int x = special[i-1].XX, y = special[i-1].YY;
int px = i> 0? special[i-2].XX: 0;
if(x-px <= 2) dp[i][0] = dp[i-1][0] +spec[i-1]+grid[x-1][y]+grid[x][y+1]+grid[x][y-1];
else dp[i][0] = max(dp[i-1][0], dp[i-1][1]) +spec[i-1]+grid[x-1][y]+grid[x][y+1]+grid[x][y-1];
dp[i][1] = max(dp[i-1][1], dp[i-1][0]) +spec[i-1]+grid[x+1][y]+grid[x][y+1]+grid[x][y-1];
// printf("%d %d\n", dp[i][0], dp[i][1]);
}
return max(dp[K][0],dp[K][1]);
}
int main(){
scanf("%d%d", &N,&M);// N = y M = x
grid.resize(M+10, vector<int>(N+10, 0));
sgrid.resize(M+10, vector<bool>(N+10,0));
for(int y = 1; y <=N;++y){
for(int x = 1; x <=M; ++x){
scanf("%d", &grid[x][y]);
// printf("done\n");
}
}
for(int i = 1; i<= M; ++i){
sgrid[i][0] = 1;
sgrid[i][N+1] = 1;
}
for(int i = 1; i<=N;++i){
sgrid[0][i] = 1;
sgrid[M+1][i] = 1;
}
scanf("%d", &K);
bool allOneLine = 1;
for(int i = 1; i<=K; ++i){
int a,b;
scanf("%d%d", &a,&b);
special.push_back({b+1,a+1});
if(a+1 != special[0].YY) allOneLine = false;
sgrid[b+1][a+1] = 1;
// printf("%d\n", grid[a+1][b+1]);
}
if(allOneLine){
sort(special.begin(), special.end());
int x =sameRow();
if(x < 0) printf("No");
else printf("%d", x);
}
else if(K < 10){
int sol =solve410(0, sgrid, 0);
if(sol == -1) printf("No");
else printf("%d", sol);
}
else {
int sol = firsSub();
if(sol == -1) printf("No");
else printf("%d\n", sol);
}
return 0;
}