Submission #1671742


Source Code Expand

/**
 * 
 */

// #include {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <forward_list>
#include <functional>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifdef DEBUG
#include <fmt/format.h>
#include <fmt/ostream.h>
#endif

using namespace std;
// }}}

// type {{{
using  s8 =   int8_t;
using  u8 =  uint8_t;
using s16 =  int16_t;
using u16 = uint16_t;
using s32 =  int32_t;
using u32 = uint32_t;
using s64 =  int64_t;
using u64 = uint64_t;

template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
// }}}

// 適宜調整
//#define int s64

constexpr bool STDIO_ENABLE = false;

constexpr int IOS_PREC = 10;

constexpr int INF_S32 = 1.01e+9;
constexpr s64 INF_S64 = 1.01e+18;

constexpr auto   INF = INF_S64;
constexpr double EPS = 1e-9;

// util {{{
template<typename T>
constexpr bool is_odd(T x)
{
    return x % 2 == 1;
}

template<typename T>
constexpr bool is_even(T x)
{
    return x % 2 == 0;
}

template<typename T>
constexpr int cmp(T x, T y)
{
    return (x > y) - (x < y);
}

template<typename T>
constexpr int sgn(T x)
{
    return cmp(x, T(0));
}

template<typename T>
constexpr typename enable_if<is_signed<T>::value,T>::type modulo(T a, T b)
{
    assert(b > 0);
    T r = a % b;
    return r >= 0 ? r : r+b;
}

template<typename T>
constexpr T clamp(T x, T lo, T hi)
{
    assert(lo <= hi);
    if(x < lo)
        return lo;
    else if(x > hi)
        return hi;
    else
        return x;
}

int sqrti(int x)
{
    assert(x >= 0);
    return static_cast<int>(sqrt(x));
}

s64 sqrtl(s64 x)
{
    assert(x >= 0);
    return static_cast<s64>(sqrtl(x));
}

template<typename T>
bool chmax(T& xmax, const T& x)
{
    if(x > xmax) {
        xmax = x;
        return true;
    }
    else {
        return false;
    }
}

template<typename T>
bool chmin(T& xmin, const T& x)
{
    if(x < xmin) {
        xmin = x;
        return true;
    }
    else {
        return false;
    }
}

template<typename T>
constexpr int SIZE(const T& c)
{
    return static_cast<int>(c.size());
}

template<typename T, size_t N>
constexpr int SIZE(const T (&)[N])
{
    return static_cast<int>(N);
}

ostream& FPRINT(ostream& out) { return out; }

template<typename T, typename... TS>
ostream& FPRINT(ostream& out, const T& x, const TS& ...args)
{
    out << x;
    if(sizeof...(args))
        out << ' ';
    return FPRINT(out, args...);
}

template<typename... TS>
ostream& FPRINTLN(ostream& out, const TS& ...args)
{
    FPRINT(out, args...);
    return out << '\n';
}

template<typename InputIt>
ostream& FPRINTSEQ(ostream& out, InputIt first, InputIt last)
{
    for(InputIt it = first; it != last; ++it) {
        if(it != first) out << ' ';
        out << *it;
    }
    return out;
}

template<typename T, size_t N>
ostream& FPRINTARRAY1(ostream& out, const T (&c)[N])
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T, size_t N1, size_t N2>
ostream& FPRINTARRAY2(ostream& out, const T (&c)[N1][N2])
{
    out << '\n';
    for(const auto& e : c) {
        FPRINTARRAY1(out, e) << '\n';
    }
    return out;
}

template<typename... TS>
ostream& PRINT(const TS& ...args)
{
    return FPRINT(cout, args...);
}

template<typename... TS>
ostream& PRINTLN(const TS& ...args)
{
    return FPRINTLN(cout, args...);
}

template<typename InputIt>
ostream& PRINTSEQ(InputIt first, InputIt last)
{
    return FPRINTSEQ(cout, first, last);
}

template<typename T, size_t N>
ostream& PRINTARRAY1(const T (&c)[N])
{
    return FPRINTARRAY1(cout, c);
}

template<typename T, size_t N1, size_t N2>
ostream& PRINTARRAY2(const T (&c)[N1][N2])
{
    return FPRINTARRAY2(cout, c);
}

template<typename... TS>
ostream& DPRINT(const TS& ...args)
{
    return FPRINT(cerr, args...);
}

template<typename... TS>
ostream& DPRINTLN(const TS& ...args)
{
    return FPRINTLN(cerr, args...);
}

template<typename InputIt>
ostream& DPRINTSEQ(InputIt first, InputIt last)
{
    return FPRINTSEQ(cerr, first, last);
}

template<typename T, size_t N>
ostream& DPRINTARRAY1(const T (&c)[N])
{
    return FPRINTARRAY1(cerr, c);
}

template<typename T, size_t N1, size_t N2>
ostream& DPRINTARRAY2(const T (&c)[N1][N2])
{
    return FPRINTARRAY2(cerr, c);
}

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1,T2>& p)
{
    return out << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T>>& c)
{
    out << '\n';
    for(const auto& e : c) {
        out << e << '\n';
    }
    return out;
}

ostream& operator<<(ostream& out, const vector<string>& c)
{
    out << '\n';
    for(const string& e : c) {
        out << e << '\n';
    }
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const deque<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const list<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const forward_list<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const unordered_set<T>& c)
{
    return out << set<T>(cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename T>
ostream& operator<<(ostream& out, const unordered_multiset<T>& c)
{
    return out << multiset<T>(cbegin(c), cend(c));
}

template<typename T, size_t N>
ostream& operator<<(ostream& out, const array<T,N>& c)
{
    return FPRINTSEQ(out, cbegin(c), cend(c));
}

template<typename InputIt>
ostream& FPRINTMAP(ostream& out, InputIt first, InputIt last)
{
    out << "{\n";
    for(auto it = first; it != last; ++it) {
        out << "  " << it->first << " : " << it->second << '\n';
    }
    out << "}\n";
    return out;
}

template<typename InputIt>
ostream& PRINTMAP(InputIt first, InputIt last)
{
    return FPRINTMAP(cout, first, last);
}

template<typename InputIt>
ostream& DPRINTMAP(InputIt first, InputIt last)
{
    return FPRINTMAP(cerr, first, last);
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const map<K,V>& c)
{
    return FPRINTMAP(out, cbegin(c), cend(c));
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_map<K,V>& c)
{
    return out << map<K,V>(cbegin(c), cend(c));
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const multimap<K,V>& c)
{
    return FPRINTMAP(out, cbegin(c), cend(c));
}

template<typename K, typename V>
ostream& operator<<(ostream& out, const unordered_multimap<K,V>& c)
{
    return out << multimap<K,V>(cbegin(c), cend(c));
}

template<typename T, typename C>
ostream& operator<<(ostream& out, stack<T,C> c)
{
    while(!c.empty()) {
        out << c.top();
        c.pop();
        if(!c.empty()) out << ' ';
    }
    return out;
}

template<typename T, typename C>
ostream& operator<<(ostream& out, queue<T,C> c)
{
    while(!c.empty()) {
        out << c.front();
        c.pop();
        if(!c.empty()) out << ' ';
    }
    return out;
}

template<typename T, typename Cont, typename Cmp>
ostream& operator<<(ostream& out, priority_queue<T,Cont,Cmp> c)
{
    while(!c.empty()) {
        out << c.top();
        c.pop();
        if(!c.empty()) out << ' ';
    }
    return out;
}

template<typename InputIt>
bool alltrue(InputIt first, InputIt last)
{
    return all_of(first, last, [](bool b) { return b; });
}

template<typename InputIt>
bool anytrue(InputIt first, InputIt last)
{
    return any_of(first, last, [](bool b) { return b; });
}

template<typename InputIt>
bool allfalse(InputIt first, InputIt last)
{
    return !anytrue(first, last);
}

template<typename InputIt>
bool anyfalse(InputIt first, InputIt last)
{
    return !alltrue(first, last);
}

struct pairhash {
    template<typename T1, typename T2>
    size_t operator()(const pair<T1,T2>& p) const
    {
        size_t ans = 17;
        ans = 31*ans + hash<T1>()(p.first);
        ans = 31*ans + hash<T2>()(p.second);
        return ans;
    }
};

template<typename T>
void UNIQ(T& c)
{
    c.erase(unique(begin(c), end(c)), end(c));
}

template<typename T>
void RD(T& x)
{
    cin >> x;
#ifdef DEBUG
    if(!cin) assert(false);
#endif
}

[[noreturn]] void EXIT()
{
#ifdef DEBUG
    fflush(stdout);
    fflush(stderr);
    cout.flush();
    cerr.flush();
#else
    if(STDIO_ENABLE)
        fflush(stdout);
    else
        cout.flush();
#endif
    quick_exit(0);
}

struct IosIni {
    IosIni()
    {
#ifndef DEBUG
        cin.tie(nullptr);
        if(!STDIO_ENABLE)
            ios::sync_with_stdio(false);
#endif
        cout << fixed << setprecision(IOS_PREC);
    }
} IOSINI;

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f,c,...) (([&](decltype((c)) cc) { return (f)(begin(cc), end(cc), ## __VA_ARGS__); })(c))

#define MEMSET(a,v) memset((a), (v), sizeof(a))

#define DBG(x) DPRINTLN('L', __LINE__, ':', #x, ':', (x))
// }}}

struct Point {
    int x;
    int y;
    Point(int xx, int yy) : x(xx), y(yy) {}
};

int dist(const Point& a, const Point& b)
{
    return abs(a.x-b.x) + abs(a.y-b.y);
}

int H, W;
int K;

vector<string> M;

// 各行にいもす法を適用
void solve()
{
    vector<vector<int>> v(H, vector<int>(W+1, 0));
    REP(y, H) REP(x, W) {
        char c = M[y][x];
        if(c == 'x') {
            v[y][max(0, x-K)]   += 1;
            v[y][min(W, x+K+1)] -= 1;
            FOR(i, 1, K+1) {
                if(y+1 < H) {
                    v[y+1][max(0, x-K+i)]   += 1;
                    v[y+1][min(W, x+K-i+1)] -= 1;
                }
                if(y-1 >= 0) {
                    v[y-1][max(0, x-K+i)]   += 1;
                    v[y-1][min(W, x+K-i+1)] -= 1;
                }
            }
        }
    }
#ifdef DEBUG
    DBG(v);
#endif
    REP(y, H) {
        auto& row = v[y];
        ALL(partial_sum, row, begin(row));
        row.pop_back();
    }
#ifdef DEBUG
    DBG(v);
#endif

    int ans = 0;
    FOR(y, K, H-K) FOR(x, K, W-K) {
        if(v[y][x] == 0)
            ++ans;
    }

    PRINTLN(ans);
}

signed main(signed /*argc*/, char** /*argv*/)
{
    RD(H); RD(W);
    M.resize(H);
    RD(K); --K; // 0-based

    REP(y, H) {
        RD(M[y]);
    }

    solve();

    EXIT();
}

Submission Info

Submission Time
Task C - 菱型カウント
User yumsiim
Language C++14 (GCC 5.4.1)
Score 0
Code Size 11193 Byte
Status WA
Exec Time 4 ms
Memory 1536 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 12
WA × 11
AC × 20
WA × 23
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 1 ms 256 KB
subtask0-sample02.txt AC 1 ms 256 KB
subtask0-sample03.txt AC 1 ms 256 KB
subtask1-01.txt AC 1 ms 256 KB
subtask1-02.txt AC 1 ms 256 KB
subtask1-03.txt AC 1 ms 256 KB
subtask1-04.txt AC 1 ms 256 KB
subtask1-05.txt WA 1 ms 256 KB
subtask1-06.txt WA 1 ms 256 KB
subtask1-07.txt WA 1 ms 256 KB
subtask1-08.txt WA 1 ms 256 KB
subtask1-09.txt WA 1 ms 256 KB
subtask1-10.txt AC 1 ms 256 KB
subtask1-11.txt WA 1 ms 256 KB
subtask1-12.txt WA 1 ms 256 KB
subtask1-13.txt WA 1 ms 256 KB
subtask1-14.txt AC 1 ms 256 KB
subtask1-15.txt AC 1 ms 256 KB
subtask1-16.txt WA 1 ms 256 KB
subtask1-17.txt AC 1 ms 256 KB
subtask1-18.txt AC 1 ms 256 KB
subtask1-19.txt WA 1 ms 256 KB
subtask1-20.txt WA 1 ms 256 KB
subtask2-01.txt AC 2 ms 640 KB
subtask2-02.txt AC 2 ms 640 KB
subtask2-03.txt AC 1 ms 256 KB
subtask2-04.txt WA 2 ms 768 KB
subtask2-05.txt WA 3 ms 1536 KB
subtask2-06.txt AC 3 ms 1536 KB
subtask2-07.txt WA 4 ms 1536 KB
subtask2-08.txt AC 3 ms 1536 KB
subtask2-09.txt WA 3 ms 1536 KB
subtask2-10.txt WA 3 ms 1536 KB
subtask2-11.txt WA 3 ms 1536 KB
subtask2-12.txt WA 3 ms 1536 KB
subtask2-13.txt AC 3 ms 1536 KB
subtask2-14.txt AC 3 ms 1536 KB
subtask2-15.txt WA 3 ms 1536 KB
subtask2-16.txt WA 4 ms 1536 KB
subtask2-17.txt WA 3 ms 1536 KB
subtask2-18.txt WA 3 ms 1536 KB
subtask2-19.txt WA 3 ms 1536 KB
subtask2-20.txt AC 3 ms 1536 KB