Submission #1281060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281060		silence25	T-Covering (eJOI19_covering)	C++20	100 / 100	255 ms	60612 KiB

covering

#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
const long long maxn = 2e6+5;
const long long px[4]={0,0,-1,1};
const long long py[4]={1,-1,0,0};
long long n,m;
long long cnt;
long long a[maxn];
bool b[maxn];
bool vis[maxn];
vector<long long>g[maxn];
vector<long long>v;
void merge(long long i1,long long j1,long long i2,long long j2){
	if(i2 > n || j2 > m || !i2 || !j2)
		return;
	long long pos1 = i1*m + j1;
	long long pos2 = i2*m + j2;
	g[pos1].pb(pos2);
	g[pos2].pb(pos1);
	return;
}
void dfs(long long pos){
	vis[pos] = true;
	if(b[pos])
		++ cnt;
	else
		v.pb(a[pos]);
	for(auto it:g[pos]){
		if(vis[it])
			continue;
		else
			dfs(it);
	}
	return;
}
void solve(){
	cin>>n>>m;
	for(long long i = 1;i<=n;++i)
		for(long long j = 1;j<=m;++j)
			cin>>a[i*m+j];
	long long q;
	long long ans = 0;
	cin>>q;
	while(q--){
		long long i,j;
		cin>>i>>j;
		++i;
		++j;
		b[i*m+j] = true;
		ans += a[i*m+j];
		for(long long k = 0;k<4;++k)
			merge(i,j,i+px[k],j+py[k]);
	}
	for(long long i = 1;i<=n;++i){
		for(long long j = 1;j<=m;++j){
			long long pos = i * m + j;
			if(vis[pos])
				continue;
			dfs(pos);
			if(cnt * 3 > v.size()){
				cout<<"No";
				return;
			}
			sort(all(v));
			reverse(all(v));
			for(long long k = 0;k<cnt*3;++k)
				ans += v[k];
			v.clear();
			cnt = 0;
		}
	}
	cout<<ans;
}
int main(){
	// freopen("file.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

• 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