Submission #95564

#	Time	Username	Problem	Language	Result	Execution time	Memory
95564		oolimry	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	38 ms	5548 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

class Grid{
public:
    int rows, columns;
    vector< vector<int> > grid;
    vector<int> IntMapping;
    vector<char> CharMapping;
    void create(){
        for(int r = 0;r < rows;r++){
            vector<int> v;
            for(int c = 0;c < columns;c++){
                v.push_back(9);
            }
            grid.push_back(v);
        }
    }
    void readChar(){
        for(int r = 0;r < rows;r++){
            char ch;
            scanf("%c",&ch);
            for(int c = 0;c < columns;c++){
                scanf("%c",&ch);
                for(int i = 0;i < CharMapping.size();i++){
                    if(CharMapping[i] == ch){
                        grid[r][c] = i;
                    }
                }
            }
        }
    }
    bool isOut(int r, int c){
        return (r < 0 || c < 0 || r >= rows || c >= columns);

    }
    int get(int r,int c){
        if(isOut(r,c))
            return 1;
        return grid[r][c];


    }
    void showGrid(){
        for(int r = 0;r < rows;r++){
            for(int c = 0;c < columns;c++){
                printf("%d ",grid[r][c]);
            }
            printf("\n");
        }
    }
};

int main()
{
    //freopen("i4.txt","r",stdin);
    int r, c, d, k;
    scanf("%d %d %d %d",&r,&c,&d,&k);
    Grid g;
    g.rows  = r;
    g.columns = c;
    g.create();
    g.CharMapping.push_back('.');
    g.CharMapping.push_back('S');
    g.CharMapping.push_back('M');
    g.readChar();

    int prefix[r][c];

    for(int rr = 0;rr < r;rr++){
        for(int cc = 0;cc < c;cc++){
            if(g.grid[rr][cc] == 2){
                prefix[rr][cc] = 0;
            }
            else{
                prefix[rr][cc] = g.grid[rr][cc];
            }
        }
    }
    //g.showGrid();
    for(int rr = 0;rr < r;rr++){
        for(int cc = 1;cc < c;cc++){
            prefix[rr][cc] += prefix[rr][cc-1];
        }
    }

    for(int rr = 1;rr < r;rr++){
        for(int cc = 0;cc < c;cc++){
            prefix[rr][cc] += prefix[rr-1][cc];
        }
    }

    int canMush = 0;
    for(int rr = 0;rr < r;rr++){
        for(int cc = 0;cc < c;cc++){
            if(g.grid[rr][cc] != 2){
                continue;
            }
            else{
                int top = max(0, rr - d);
                int bottom = min(r - 1,rr + d);
                int left = max(0, cc - d);
                int right = min(c - 1,cc + d);


                int n = 0;
                n += prefix[bottom][right];
                if(top > 0){
                    n -= prefix[top-1][right];
                }
                if(left > 0){
                    n -= prefix[bottom][left-1];
                }
                if(top > 0 && left > 0){
                    n += prefix[top-1][left-1];
                }

                if(n >= k){
                    canMush++;
                }
                //printf("%d %d %d %d %d\n",left,right,top,bottom,n);
            }
        }
    }

    printf("%d",canMush);

    for(int rr = 0;rr < r;rr++){
        for(int cc = 0;cc < c;cc++){
            //printf("%d ",prefix[rr][cc]);
        }
        //printf("\n");
    }
    return 0;
}

Compilation message (stderr)

mushrooms.cpp: In member function 'void Grid::readChar()':
mushrooms.cpp:26:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i = 0;i < CharMapping.size();i++){
                               ~~^~~~~~~~~~~~~~~~~~~~
mushrooms.cpp: In function 'int main()':
mushrooms.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d",&r,&c,&d,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp: In member function 'void Grid::readChar()':
mushrooms.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c",&ch);
             ~~~~~^~~~~~~~~~
mushrooms.cpp:25:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%c",&ch);
                 ~~~~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21