Submission #639737

#	Time	Username	Problem	Language	Result	Execution time	Memory
639737		ShirleyM	T-Covering (eJOI19_covering)	C++14	100 / 100	331 ms	59060 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vvii> vvvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
#define fast {ios_base::sync_with_stdio(false); cin.tie(0);}
const int inf = 1e11;
const int INF = 1e9;
const int mod = 1e9+7;
const int sz = 1e6;

int n,m,k;
int g[sz];
bool s[sz];
bool vis[sz];
vi adj[sz];
int cnt_s=0;
vi vals;

inline bool in_limits(int i, int j){
    return (i>=0 && i<n && j>=0 && j<m);
}

void dfs(int v){
    vis[v]=1;
    if(!s[v]) vals.pb(g[v]);
    else cnt_s++;
    for(auto u:adj[v]){
        if(vis[u]) continue;
        dfs(u);
    }
}

int32_t main() {
    fast;
    cin >> n >> m;
    loop(i,0,n){
        loop(j,0,m){
            int v = i*m+j;
            cin >> g[v];
            s[v]=vis[v]=0;
        }
    }
    cin >> k;
    int ans=0;
    loop(i,0,k){
        int r,c; cin >> r >>c;
        int v= r*m+c;
        s[v]=true;
        ans+=g[v];
        vii d = {{-1,0}, {1,0}, {0,1}, {0,-1}};
        for(auto it:d) {
            int di = it.x, dj = it.y;
            int ni = r + di, nj = c + dj;
            int u = ni*m+nj;
            if (!in_limits(ni, nj)) continue;
            adj[v].pb(u);
            adj[u].pb(v);
        }
    }
    loop(r,0,n){
        loop(c,0,m){
            int v = r*m+c;
            if(!vis[v] && s[v]){
                cnt_s=0;
                vals.clear();
                dfs(v);
                if(vals.size() < 3*cnt_s){
                    cout << "No";
                    return 0;
                }
                sort(all(vals));
                loop(i,1,3*cnt_s+1) ans+=vals[vals.size()-i];
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int32_t main()':
covering.cpp:83:32: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   83 |                 if(vals.size() < 3*cnt_s){
      |                    ~~~~~~~~~~~~^~~~~~~~~

• 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