Submission #441646

#	Time	Username	Problem	Language	Result	Execution time	Memory
441646		nots0fast	T-Covering (eJOI19_covering)	C++17	100 / 100	142 ms	15232 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define mt make_tuple
#define MAX (int)(2*pow(10,6) + 5)
// #define cout out
// #define cin in
ll inf = pow(10, 18) + 100;
ll INF = pow(10, 9);
ll modulo = pow(10, 9) + 7;
double eps = 1e-10;

// start time 18 : 23

ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0 , 1, 0, -1};

void deal(){
	ll n, m;
	cin>>n>>m;
	vector<vector<bool> > chosen(n, vector<bool>(m, 0));
	vector<vector<bool> > seen(n, vector<bool>(m, 0));
	vector<vector<ll> > arr(n, vector<ll>(m));
	fori(n){
		forj(m){
			cin>>arr[i][j];
		}
	}
	ll q;
	cin>>q;
	fori(q){
		ll ri, ci;
		cin>>ri>>ci;
		chosen[ri][ci] = 1;
	}
	ll s = 0;
	fori(n){
		forj(m){
			if(chosen[i][j] && !seen[i][j]){
				vector<pair<ll,ll> > bfs(1, mp(i,j));
				seen[i][j] = 1;
				vector<ll> tot(2, 0);
				fork((ll)bfs.size()){
					ll x = bfs[k].ff, y = bfs[k].ss;
					tot[chosen[x][y]]++;
					forl(4){
						ll x1 = x+dx[l] , y1 = y + dy[l];
						if(x1 > -1 && y1 > -1 && x1 < n && y1 < m && !seen[x1][y1]){
							if(!chosen[x][y] && !chosen[x1][y1]){
								continue;
							}
							seen[x1][y1] = 1;
							bfs.pb(mp(x1,y1));
						}
					}
				}
				if(tot[0] < tot[1] * 3){
					cout<<"No";
					return;
				}
				ll mn = inf;
				for(auto& [x,y] : bfs){
					s+=arr[x][y];
					if(!chosen[x][y]){
						mn = min(mn, arr[x][y]);
					}
				}
				if(tot[0] > tot[1] * 3){
					s-=mn;
				}
			}
		}
	}
	cout<<s;
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();  
}

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