제출 #658836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658836		aebov	T-Covering (eJOI19_covering)	C++17	25 / 100	78 ms	29832 KiB

covering

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("O3")
    #pragma GCC optimize("fast-math")
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<set>
    #include<queue>
    #define ll long long
    #define pb push_back
    #define pll pair<ll ,ll>
    #define F first
    #define S second
    #define pii pair<int ,int>
    using namespace std;
     
    const int N = (int)1e6 + 6;
    int n, m, k, x, y, g[N], v, u,  okt;
    vector<int> vc, adj[N];
    int hx[] = {0, 0, -1, 1};
    int hy[] = {-1, 1, 0, 0};
    ll ans = 0LL;
    bool vis[N], ok[N];
     
    bool valid(int i,int j){return (i >= 0 && i < n && j >= 0 && j < m);}
    void dfs(int v){
    	vis[v] = 1;
    	if(!ok[v])vc.pb(g[v]);
    	else okt ++;
    	for(auto u : adj[v])if(!vis[u])dfs(u);
    }
    int main(){
    	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    	cin >> n >> m;
    	for(int i = 0; i < n; i ++)for(int j = 0; j < m;j ++)cin >> g[i*m + j];
    	cin >> k;
    	for(int i = 0; i < k; i ++){
    		cin >> x >> y;
    		int v = x*m + y;
    	//	cout << "V : " << v << endl;
    		ok[v] = 1, ans += g[v];
    		for(int r = 0; r < 4; r ++){
    			int xx = x + hx[r], yy = y + hy[r];
    			if(!valid(xx, yy))continue;
    			int u = xx * m + yy;
    			adj[v].pb(u), adj[u].pb(v);
    	//		cout << " adj : " <<u << " " << v << endl;
    		}
    	}
    	for(int i = 0; i < n; i ++){
    		for(int j = 0; j < m; j ++){
    			v = i*m + j;
    			if(!vis[v] && ok[v]){
    				okt = 0;
    				vc.clear();
    				dfs(v);
    				if(vc.size() < 3 * okt)return cout << "NO\n", 0;
    				sort(vc.begin(), vc.end());
    	//			cout << i << " " << j << " : " ;
        //          for(auto x : vc)cout << x << " ";
       //           cout << endl;
    				for(int f = 1; f <= 3*okt; f ++)ans += vc[vc.size() - f];
    			}
    		}
    	}return cout << ans << "\n" , 0;
    }

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'int main()':
covering.cpp:60:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if(vc.size() < 3 * okt)return cout << "NO\n", 0;
      |            ~~~~~~~~~~^~~~~~~~~

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