| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1250130 | Petrix | T-Covering (eJOI19_covering) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
int n,m,cnt;
vector<int> v1,v[1000001];
int viz[1000001];
int a[1000001];
int b[1000001];
void dfs(int nod){
int i;
if(viz[nod]) return;
viz[nod]=1;
if(b[nod]==1) cnt++;
else v1.push_back(-a[nod]);
for(i=0;i<v[nod].size();i++) {
dfs(v[nod][i]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i,a1,b1,k,j,rasp=0;
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>a1;
a[(i-1)*m+j]=a1;
}
}
cin>>k;
for(i=1;i<=k;i++) {
cin>>a1>>b1;a1++;b1++;
rasp+=a[(a1-1)*m+b1];b[(a1-1)*m+b1]=1;
if(a1>1){
v[(a1-1)*m+b1].push_back((a1-2)*m+b1);
v[(a1-2)*m+b1].push_back((a1-1)*m+b1);
}
if(b1>1){
v[(a1-1)*m+b1].push_back((a1-1)*m+b1-1);
v[(a1-1)*m+b1-1].push_back((a1-1)*m+b1);
}
if(a1<n){
v[a1*m+b1].push_back((a1-1)*m+b1);
v[(a1-1)*m+b1].push_back(a1*m+b1);
}
if(b1<m){
v[(a1-1)*m+b1+1].push_back((a1-1)*m+b1+1);
v[(a1-1)*m+b1].push_back((a1-1)*m+b1+1);
}
}
for(i=1;i<=n*m;i++) {
if(viz[i]) continue;
v1.clear();cnt=0;
dfs(i);
if(3*cnt>v1.size()){
cout<<"No";return 0;
}
sort(v1.begin(),v1.end());
for(j=0;j<3*cnt;j++)
rasp-=v1[j];
}
cout<<rasp;
return 0;
}