Game
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1563 Accepted Submission(s): 664
the following:
● At the beginning, the score is 0;
● If you take a number which equals to x, the score increase x;
● If there appears two neighboring empty grids after you taken the number, then the score should be decreased by 2(x&y). Here x and y are the values used to existed on these two grids. Please pay attention that "neighboring grids" means there exits and only exits one common border between these two grids.
Since onmylove thinks this problem is too easy, he adds one more rule:
● Before you start the game, you are given some positions and the numbers on these positions must be taken away.
Can you help onmylove to calculate: what's the highest score onmylove can get in the game?
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.
2 2
2 2
1 1
2 2 1
2 7
4 1
1 1
9
As to the second case in Sample Input, onmylove gan get the highest score when calulating like this:
2 + 7 + 4 - 2 × (2&4) - 2 × (2&7) = 13 - 2 × 0 - 2 × 2 = 9.
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 1e5 + , INF = 0x7fffffff;
int dir[][] = {{, }, {, -}, {, }, {-, }};
int n, m, k, s, t;
int way[][], vv[][];
int head[maxn], cur[maxn], vis[maxn], d[maxn], cnt, nex[maxn << ]; struct node
{
int u, v, c;
}Node[maxn << ]; void add_(int u, int v, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
nex[cnt] = head[u];
head[u] = cnt++;
} void add(int u, int v, int c)
{
add_(u, v, c);
add_(v, u, );
} bool bfs()
{
queue<int> Q;
mem(d, );
Q.push(s);
d[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(!d[v] && Node[i].c > )
{
d[v] = d[u] + ;
Q.push(v);
if(v == t) return ;
}
}
}
return d[t] != ;
} int dfs(int u, int cap)
{
int ret = ;
if(u == t || cap == )
return cap;
for(int &i = cur[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(d[v] == d[u] + && Node[i].c > )
{
int V = dfs(v, min(cap, Node[i].c));
Node[i].c -= V;
Node[i ^ ].c += V;
ret += V;
cap -= V;
if(cap == ) break;
}
}
if(cap > ) d[u] = -;
return ret;
} int Dinic()
{
int ans = ;
while(bfs())
{
memcpy(cur, head, sizeof head);
ans += dfs(s, INF);
}
return ans;
} int main()
{
while(scanf("%d%d%d", &n, &m, &k) != EOF)
{
int sum = ;
s = , t = n * m + ;
mem(head, -), cnt = , mem(vv, );
int w, x, y;
rap(i, , n)
rap(j, , m)
rd(way[i][j]), sum += way[i][j];
rap(i, , k)
{
rd(x), rd(y);
if((x + y) & )
add(s, (x - ) * m + y, INF);
else add((x - ) * m + y, t, INF);
vv[x][y] = ;
}
rap(i, , n)
rap(j, , m)
{
rep(k, , )
{
int nx = i + dir[k][];
int ny = j + dir[k][];
if(nx < || ny < || nx > n || ny > m) continue;
if((i + j) & )
add((i - ) * m + j, (nx - ) * m + ny, * (way[i][j] & way[nx][ny]));
}
if(vv[i][j]) continue;
if((i + j) & ) add(s, (i - ) * m + j, way[i][j]);
else add((i - ) * m + j, t, way[i][j]);
}
cout << sum - Dinic() << endl; } return ;
}
Game
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1563 Accepted Submission(s): 664
the following:
● At the beginning, the score is 0;
● If you take a number which equals to x, the score increase x;
● If there appears two neighboring empty grids after you taken the number, then the score should be decreased by 2(x&y). Here x and y are the values used to existed on these two grids. Please pay attention that "neighboring grids" means there exits and only exits one common border between these two grids.
Since onmylove thinks this problem is too easy, he adds one more rule:
● Before you start the game, you are given some positions and the numbers on these positions must be taken away.
Can you help onmylove to calculate: what's the highest score onmylove can get in the game?
n and m describing the size of the grids is n ×m. k means there are k positions of which you must take their numbers. Then following n lines, each contains m numbers, representing the numbers on the n×m grids.Then k lines follow. Each line contains two integers, representing the row and column of one position
and you must take the number on this position. Also, the rows and columns are counted start from 1.
Limits: 1 ≤ n, m ≤ 50, 0 ≤ k ≤ n × m, the integer in every gird is not more than 1000.
2 2
2 2
1 1
2 2 1
2 7
4 1
1 1
9
As to the second case in Sample Input, onmylove gan get the highest score when calulating like this:
2 + 7 + 4 - 2 × (2&4) - 2 × (2&7) = 13 - 2 × 0 - 2 × 2 = 9.