Submission #441829

#	Time	Username	Problem	Language	Result	Execution time	Memory
441829		Theo830	T-Covering (eJOI19_covering)	C++17	100 / 100	710 ms	79740 KiB

covering

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll dx[4] = {0,0,1,-1};
ll dy[4] = {1,-1,0,0};
vector<vector<bool> >v;
bool in(ll n,ll m,ll x,ll y){
    return min(x,y) >= 0 && x < n && y < m;
}
vector<vector<vector<ii> > >adj;
vector<ll>exo;
set<ii>ar;
vector<vector<ll> >arr;
ll posa = 0;
void dfs(ll x,ll y){
    v[x][y] = true;
    if(!ar.count(ii(x,y))){
        exo.pb(arr[x][y]);
    }
    else{
        posa++;
    }
    for(auto z:adj[x][y]){
        if(!v[z.F][z.S]){
            dfs(z.F,z.S);
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    f(i,0,n){
        arr.pb(vector<ll>());
        v.pb(vector<bool>());
        f(j,0,m){
            ll a;
            cin>>a;
            arr.back().pb(a);
            v.back().pb(0);
        }
    }
    vector<vector<ii> > w(m);
    adj.assign(n,w);
    ll ans = 0;
    bool ok = true;
    ll k;
    cin>>k;
    f(i,0,k){
        ll x,y;
        cin>>x>>y;
        ar.insert(ii(x,y));
        ans += arr[x][y];
        f(e,0,4){
            if(in(n,m,x + dx[e],y + dy[e])){
                adj[x][y].pb(ii(x + dx[e],y + dy[e]));
                adj[x + dx[e]][y + dy[e]].pb(ii(x,y));
            }
        }
    }
    f(i,0,n){
        f(j,0,m){
            if(!v[i][j]){
                posa = 0;
                exo.clear();
                dfs(i,j);
                sort(all(exo));
                posa *= 3;
                if(posa > exo.size()){
                    ok = false;
                }
                else{
                    while(posa--){
                        ans += exo.back();
                        exo.pop_back();
                    }
                }
            }
        }
    }
    if(!ok){
        cout<<"No\n";
        return 0;
    }
    cout<<ans<<"\n";
}
/*
5 6
7 3 8 1 0 9
4 6 2 5 8 3
1 9 7 3 9 5
2 6 8 4 5 7
3 8 2 7 3 6
3
1 1
2 2
3 4
*/

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:91:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 if(posa > exo.size()){
      |                    ~~~~~^~~~~~~~~~~~

• 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