Submission #1364671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364671		kmath628	T-Covering (eJOI19_covering)	C++20	100 / 100	76 ms	13888 KiB

covering

#include <bits/stdc++.h>
using namespace std;
int dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};
int main(){
    int m,n,k,i,j,r=0;
    scanf("%d %d",&m,&n);
    vector<vector<int> > a(m),s(m),c(m);
    for(i=0;i<m;i++){
        a[i].resize(n);
        for(j=0;j<n;j++) scanf("%d",&a[i][j]);
        s[i].resize(n);
        c[i].resize(n);
    }
    scanf("%d",&k);
    while(k--){
        scanf("%d %d",&i,&j);
        s[i][j]=1;
    }
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            if(c[i][j]) continue;
            int ct=0,cs=0,sum=0,mn=1776;
            queue<pair<int,int> > q;
            q.push({i,j});
            c[i][j]=1;
            while(!q.empty()){
                auto [y,x]=q.front();
                ct++;
                sum+=a[y][x];
                if(s[y][x]) cs++;
                else mn=min(mn,a[y][x]);
                q.pop();
                for(k=0;k<4;k++){
                    int ty=y+dy[k],tx=x+dx[k];
                    if(ty>=0 && ty<=m-1 && tx>=0 && tx<=n-1 && !c[ty][tx] && (s[y][x]||s[ty][tx])){
                        q.push({ty,tx});
                        c[ty][tx]=1;
                    }
                }
            }
            if(ct<4*cs){
                printf("No\n");
                return 0;
            }
            r+=sum;
            if(ct>4*cs) r-=mn;
        }
    }
    printf("%d\n",r);
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     scanf("%d %d",&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~
covering.cpp:10:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         for(j=0;j<n;j++) scanf("%d",&a[i][j]);
      |                          ~~~~~^~~~~~~~~~~~~~~
covering.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d",&k);
      |     ~~~~~^~~~~~~~~
covering.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d %d",&i,&j);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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