#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>
using namespace std;
typedef long long int63;
typedef unsigned long long int64;
#define forl(name,start,end,jump) for(int63 name = start; name < end; name+=jump)
#define forlb(name,start,end,jump) for(int63 name = end - 1; name >= start; name+=jump)
#define forn(name,start,end) forl(name,start,end,1)
#define fornb(name,start,end) forlb(name,start,end,-1)
#define fort(start,end) forn(i,start,end)
#define fortb(start,end) fornb(i,start,end)
#define forto(start,end) forn(j,start,end)
#define fortob(start,end) fornb(j,start,end)
#define fortoo(start,end) forn(l,start,end)
#define all(vec) vec.begin(),vec.end()
#define makeitem(itemname,itemtype) itemtype itemname; cin >> itemname
#define point pair<int63,int63>
#define spoint pair<short,short>
#define ipoint pair<int,int>
#define matrix(type) vector<vector<type>>
#define make(name) int63 name; cin >> name
#define tosort(name) name.begin(),name.end()
int63 powmod(int63 base, int63 exponent, int63 mod) {
int63 result = 1;
while (exponent > 0) {
if (exponent % 2 == 0) {
exponent /= 2;
base = (base * base) % mod;
}
else {
result = (result * base) % mod;
exponent /= 2;
base = (base * base) % mod;
}
}
return result;
}
bool decresing(int63 x, int63 y) {
return x > y;
}
int63 modInverse(int63 a, int63 b) {//finds inverse of a mod b ...?
int63 m = b;
int63 y = 0, x = 1;
while (a > 1) {
int63 q = a / m;
int63 t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) {
x += b;
}
return x;
}
int63 trin(int63 start, int63 stop) {
return (stop - start + 1) * (stop + start) / 2;
}
int63 trin2(int63 start, int63 stop, int63 mod) {
return ((stop - start + 1) * (stop + start) / 2) % mod;
}
int63 trig(int63 start, int63 stop, int63 jump, int63 mod) {
return ((trin2(start / jump, (stop - (start % jump)) / jump, mod)*jump + ((stop - (start % jump)) / jump - (start / jump) + 1) * (start % jump)) % mod);
}
int63 cntot(int63 start, int63 stop, int63 jump, int63 mod) {
return (stop / jump - (start + jump - 1) / jump + 1) % mod;
}
bool sortvectorf(point a, point b) {
return((a.first > b.first) || (a.first == b.first && a.second > b.second));
}
bool sortvectordiv(point a, point b) {
return a.first * b.second > b.first * a.second;
}
bool sortvectorfv(point a, point b) {
return((a.first > b.first) || (a.first == b.first && a.second < b.second));
}
bool sortvectors(point a, point b) {
return((a.second > b.second) || (a.second == b.second && a.first > b.first));
}
bool negasortvectorf(point a, point b) {
return((a.first < b.first) || (a.first == b.first && a.second < b.second));
}
bool negasortvectors(point a, point b) {
return((a.second < b.second) || (a.second == b.second && a.first < b.first));
}
vector<vector<int63>> findPermutationsI(vector<int63> &a) {
// Sort the given array
sort(a.begin(), a.end());
vector<vector<int63> > sol;
// Find all possible permutations
do {
sol.push_back(a);
} while (next_permutation(a.begin(), a.end()));
return sol;
}
vector<vector<string>> findPermutationsS(vector<string> &a) {
// Sort the given array
sort(a.begin(), a.end());
vector<vector<string> > sol;
// Find all possible permutations
do {
sol.push_back(a);
} while (next_permutation(a.begin(), a.end()));
return sol;
}
int63 gcd(int63 a, int63 b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
return gcd(b % a, a);
}
bool isprime(int63 n) {
fort(2, n) {
if (i * i > n) {
break;
}
if ((n / i) * i == n) {
return false;
}
}
return true;
}
int63 fdivisor(int63 n, int63 fro) {
fort(1, n + 1) {
if ((n / i) * i == n && i >= fro) {
return i;
}
}
return -1;
}
vector<int63> divlist(int63 n) {
vector<int63> curr;
fort(1, n + 1) {
if ((int63)i * i > n) {
break;
}
if ((n / i) * i == n) {
curr.push_back(i);
curr.push_back(n / i);
}
if ((int63)i * i == n) {
curr.pop_back();
}
}
sort(all(curr));
return curr;
}
int63 divcnt(int63 n) {
int63 ans = 1;
fort(2, n + 1) {
if (i*i > n) {
ans *= 2;
break;
}
int63 cur = 1;
while (n % i == 0) {
n /= i;
cur++;
}
ans *= cur;
}
return ans;
}
vector<int63> pdivlist(int63 n) {
vector<int63> curr;
fort(2, n + 1) {
if ((int63)i * i > n) {
break;
}
if ((n / i) * i == n) {
if (isprime(i)) { curr.push_back(i); }
if (isprime(n / i)) { curr.push_back(n / i); }
}
if ((int63)i * i == n && isprime(i)) {
curr.pop_back();
}
}
sort(all(curr));
return curr;
}
int63 countdivisors(int63 n, int63 divd, int63 rem) {
vector<int63> divs = divlist(n);
int63 tot = 0;
fort(0, (int63)divs.size()) {
if (divs[(int)i] % divd == rem) {
tot++;
}
}
if (n % divd == rem) {
tot++;
}
return tot;
}
int63 digsum(int63 num) {
int63 cr = 0;
while (num) {
cr += num % 10;
num /= 10;
}
return cr;
}
int63 azeret(int63 num, int63 mod) {
int63 sil = 1;
while (num > 1) {
sil *= num;
sil %= mod;
num--;
}
return sil;
}
int63 moddiv(int63 to, int63 by, int63 mod) {
to %= mod;
by %= mod;
to *= modInverse(by, mod);
return to % mod;
}
class node {
public:
int data1;
int data2;
node* nxt;
node* bef;
node(int dat1, int dat2, node*bif) {
this->nxt = NULL;
this->bef = bif;
this->bef->nxt = this;
this->data1 = dat1;
this->data2 = dat2;
}
node(int dat1, int dat2) {
this->nxt = NULL;
this->bef = NULL;
this->data1 = dat1;
this->data2 = dat2;
}
node() {
this->nxt = NULL;
this->bef = NULL;
this->data1 = 0;
this->data2 = 0;
}
void remove() {
this->bef->nxt = this->nxt;
if (this->nxt != NULL) {
this->nxt->bef = this->bef;
}
}
void push(int dat1, int dat2) {
node* next = this->nxt;
node* curr = new node(dat1, dat2, this);
curr->nxt = next;
next->bef = curr;
}
};
bool by_first(pair<point, point> a, pair<point, point> b) {
return a.first.first < b.first.first;
}
bool ff_fs(pair<pair<int63, bool>, int63> a, pair<pair<int63, bool>, int63> b) {
return a.first.first < b.first.first || (a.first.first == b.first.first && a.first.second && !b.first.second);
}
bool f_s_b(pair<int63, int63> a, pair<int63, int63> b) {
return a.first > b.first || (a.first == b.first && a.second > b.second);
}
bool palindrome(string s) {
fort(0, (int63)s.size() / 2) {
if (s[(int)i] != s[s.size() - 1 - (int)i]) {
return 0;
}
}
return 1;
}
struct union_find {
vector<int>rot;
vector<int> posrat;
vector<vector<int>> rat;
int63 cnt;
void init(int n) {
fort(0, n) {
rot.push_back((int)i);
rat.push_back({ (int)i });
posrat.push_back((int)i);
}
cnt = n;
}
bool isunion(int f, int s) {
if (rot[f] == rot[s]) {
return true;
}
return false;
}
bool unio(int f, int s) {
if (rot[f] == rot[s]) {
return false;
}
cnt--;
//rot[f] <-> rot[s]
if (rat[(int)posrat[rot[f]]].size() > rat[(int)posrat[rot[s]]].size()) {
//s to f
int siz = rat[posrat[rot[s]]].size();
int rs = rot[s];
fort(0, siz) {
rat[posrat[rot[f]]].push_back(rat[posrat[rs]][(int)i]);
rot[rat[posrat[rs]][(int)i]] = rot[f];
}
rat[rs].clear();
return true;
}
int siz = rat[posrat[rot[f]]].size();
int rf = rot[f];
fort(0, siz) {
rat[posrat[rot[s]]].push_back(rat[posrat[rf]][(int)i]);
rot[rat[posrat[rf]][(int)i]] = rot[s];
}
rat[rf].clear();
return true;
}
};
vector<int63> subsum(vector<int> items, int limit) {
vector<vector<int> > table(items.size() + 1, vector<int>(limit + 1));
forto(1, (int63)items.size() + 1) {
int wt = items[(int)j - 1];
int val = wt;
for (int w = 1; w < limit + 1; w++) {
if (wt > w) {
table[(int)j][w] = table[(int)j - 1][w];
}
else {
table[(int)j][w] = max(table[(int)j - 1][w], (int)(table[(int)j - 1][w - wt] + val));
}
}
}
vector<int63> result;
int w = limit;
for (int63 j = (int63)items.size(); j > 0; j--) {
bool was_added = table[(int)j][w] != table[(int)j - 1][w];
if (was_added) {
int wt = items[(int)j - 1];
result.push_back((int)j - 1);
w -= wt;
}
}
sort(all(result));
return result;
}
bool func(pair<point, int63>a, pair<point, int63>b) {
return a.first.second < b.first.second || (a.first.second == b.first.second && a.first.first < b.first.first);
}
int63 palpref(string &s) {
int63 ha1 = 0, ha2 = 0, hr1 = 0, hr2 = 0;
int63 m1 = 1, m2 = 1;
int63 mix = 0;
forto(0, (int63)s.size()) {
ha1 = (ha1 + m1 * s[(int)j]) % 1000000007;
ha2 = (ha2 + m2 * s[(int)j]) % 998244353;
hr1 = (s[(int)j] + 359 * hr1) % 1000000007;
hr2 = (s[(int)j] + 401 * hr2) % 998244353;
m1 *= 359, m1 %= 1000000007;
m2 *= 401, m2 %= 998244353;
if (ha1 == hr1 && ha2 == hr2) {
mix = j + 1;
}
}
return mix;
}
struct fenwick {
int n;
vector<int63> data;
vector<int63> real;
void init(int n) {
this->n = n;
data.resize(n);
real.resize(n);
}
void update(int pos, int63 val) {
int rpos = pos;
pos++;
int63 cur = 0;
while (pos << cur <= this->n) {
if (pos % 2 == 1) {
this->data[(pos << cur) - 1] += val - this->real[rpos];
}
cur++;
pos = (pos + 1) / 2;
}
this->real[rpos] = val;
}
void add(int pos, int63 val) {
int rpos = pos;
pos++;
int63 cur = 0;
while (pos << cur <= this->n) {
if (pos % 2 == 1) {
this->data[(pos << cur) - 1] += val;
}
cur++;
pos = (pos + 1) / 2;
}
this->real[rpos] += val;
}
int63 query0(int a) {
int63 sol = 0;
int63 cur = 0;
a++;
while (a) {
if (a % 2 == 1) {
sol += this->data[(a << cur) - 1];
}
cur++;
a = a / 2;
}
return sol;
}
int63 query(int a, int b) {
return query0(b) - query0(a - 1);
}
};
struct fenwick2 {
int63 n, m;
vector<vector<int63>> data;
vector<vector<int63>> real;
void init(int n, int m) {
this->n = n;
this->m = m;
data = vector<vector<int63>>(n, vector<int63>(m));
real = vector<vector<int63>>(n, vector<int63>(m));
}
void update(int posx, int posy, int63 val) {
int rposx = posx;
int rposy = posy;
posx++;
posy++;
int63 cur2 = 0;
while (posy << cur2 <= this->m) {
if (posy % 2 == 1) {
int63 cur1 = 0;
while (posx << cur1 <= this->n) {
if (posx % 2 == 1) {
this->data[(posx << cur1) - 1][(posy << cur2) - 1] += val - this->real[rposx][rposy];
}
cur1++;
posx = (posx + 1) / 2;
}
posx = rposx + 1;
}
cur2++;
posy = (posy + 1) / 2;
}
this->real[rposx][rposy] = val;
}
int63 query0(int x, int y) {
int63 sol = 0;
int63 cur2 = 0;
y++;
int cx = x + 1;
while (y) {
if (y % 2 == 1) {
int63 cur1 = 0;
x = cx;
while (x) {
if (x % 2 == 1) {
sol += this->data[(x << cur1) - 1][(y << cur2) - 1];
}
cur1++;
x = x / 2;
}
}
cur2++;
y = y / 2;
}
return sol;
}
int63 query(int fx, int fy, int sx, int sy) {
return this->query0(sx, sy) - this->query0(sx, fy - 1) - this->query0(fx - 1, sy) + this->query0(fx - 1, fy - 1);
}
};
double diffclock(clock_t clock1, clock_t clock2) {
double diffticks = clock1 - clock2;
double diffms = (diffticks) / (CLOCKS_PER_SEC / 1000);
return diffms;
}
int63 detrig(int63 num) {
int63 minus = 0;
while (true) {
num -= minus;
if (num < 0) {
return minus;
}
if (num - trin(minus + 1, minus + 1000) >= 0) {
num -= trin(minus + 1, minus + 1000);
minus += 1000;
}
minus++;
}
}
int63 detrig2(int63 num, int63 minus) {
while (true) {
num -= minus;
if (num < 0) {
return minus;
}
if (num - trig(minus + 2, minus + 1000, 2, 4999999999999999999) >= 0) {
num -= trig(minus + 2, minus + 1000, 2, 4999999999999999999);
minus += 1000;
}
minus += 2;
}
}
# define PI 3.14159265358979323846
struct ifenwick {
int63 n;
vector<int> data;
vector<int> real;
void init(int n) {
this->n = n;
data.resize(n);
real.resize(n);
}
void add(int pos, int val) {
int rpos = pos;
pos++;
int cur = 0;
while (pos << cur <= this->n) {
if (pos % 2 == 1) {
this->data[(pos << cur) - 1] += val;
}
cur++;
pos = (pos + 1) / 2;
}
this->real[rpos] += val;
}
int query0(int a) {
int sol = 0;
int cur = 0;
a++;
while (a) {
if (a % 2 == 1) {
sol += this->data[(a << cur) - 1];
}
cur++;
a /= 2;
}
return sol;
}
};
#define MOD % 1000000007
#define mod 1000000007
struct treestruct {
int63 n;
int63 root;
vector<int63>layer;
vector<vector<int63>>jumps;
void initialize(int63 N) {
n = N;
jumps = vector<vector<int63>>(n, vector<int63>(18));
layer = vector<int63>(n, -1);
}
void setroot(int63 a) {
root = a;
layer[root] = 0;
jumps[root][0] = root;
}
bool addedge(int63 a, int63 b) {
if (layer[a] == -1) {
return false;
}
layer[b] = layer[a] + 1;
jumps[b][0] = a;
return true;
}
void lift() {
forto(1, 18) {
fort(0, n) {
jumps[i][j] = jumps[jumps[i][j - 1]][j - 1];
}
}
}
int63 dist(int63 a, int63 b) {
if (a == b) {
return 0;
}
if (layer[a] <= layer[b]) {
return -1;
}
int63 dif = layer[a] - layer[b];
int63 ans = dif;
fortb(0, 18) {
if (dif >= (1 << i)) {
dif -= (1 << i);
a = jumps[a][i];
}
}
if (a == b) {
return ans;
}
return -1;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
make(n);
make(m);
vector<vector<int63>>v(n, vector<int63>(m));
fort(0, n) {
forto(0, m) {
cin >> v[i][j];
}
}
make(k);
vector<point>p(k);
int63 sm = 0;
fort(0, k) {
cin >> p[i].first >> p[i].second;
if ((p[i].first == 0 || p[i].first == n - 1) && (p[i].second == 0 || p[i].second == m - 1)) {
cout << "No" << endl;
return 0;
}
if (p[i].first == 0) {
sm += v[p[i].first][p[i].second];
sm += v[p[i].first + 1][p[i].second];
sm += v[p[i].first][p[i].second - 1];
sm += v[p[i].first][p[i].second + 1];
} else if (p[i].first == n - 1) {
sm += v[p[i].first][p[i].second];
sm += v[p[i].first - 1][p[i].second];
sm += v[p[i].first][p[i].second - 1];
sm += v[p[i].first][p[i].second + 1];
} else if (p[i].second == 0) {
sm += v[p[i].first][p[i].second];
sm += v[p[i].first + 1][p[i].second];
sm += v[p[i].first - 1][p[i].second];
sm += v[p[i].first][p[i].second + 1];
} else if (p[i].second == m - 1) {
sm += v[p[i].first][p[i].second];
sm += v[p[i].first + 1][p[i].second];
sm += v[p[i].first - 1][p[i].second];
sm += v[p[i].first][p[i].second - 1];
} else {
sm += v[p[i].first][p[i].second];
sm += v[p[i].first + 1][p[i].second];
sm += v[p[i].first - 1][p[i].second];
sm += v[p[i].first][p[i].second - 1];
sm += v[p[i].first][p[i].second + 1];
sm -= min({ v[p[i].first + 1][p[i].second],v[p[i].first - 1][p[i].second],v[p[i].first][p[i].second - 1],v[p[i].first][p[i].second + 1] });
}
}
cout << sm << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
640 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1572 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
81 ms |
12152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
640 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1572 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
81 ms |
12152 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
640 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1572 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
81 ms |
12152 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
