Submission #284135

#	Time	Username	Problem	Language	Result	Execution time	Memory
284135		inbarin	T-Covering (eJOI19_covering)	C++14	5 / 100	81 ms	12152 KiB

covering

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30