Submission #2943598


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
ll ugauss(ll a, ll b) { if (!a) return 0; if (a>0^b>0) return a/b; else return (a+(a>0?-1:1))/b+1; }
ll lgauss(ll a, ll b) { if (!a) return 0; if (a>0^b>0) return (a+(a>0?-1:1))/b-1; else return a/b; }
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T> ostream &operator<<(ostream &o, const deque<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const unordered_set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U, typename V>  ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
template <typename T, typename S, typename U> ostream &operator<<(ostream &o, const priority_queue<T, S, U> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const queue<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.front(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const stack<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
size_t random_seed; struct init_{init_(){ ios::sync_with_stdio(false); cin.tie(0); gettimeofday(&start, NULL); struct timeval myTime; struct tm *time_st; gettimeofday(&myTime, NULL); time_st = localtime(&myTime.tv_sec); srand(myTime.tv_usec); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;
#define ldout fixed << setprecision(40) 

#define EPS (double)1e-14
#define INF (ll)1e18
#define mo  (ll)(1e9+7)

int main(void) {
    ll n, m; cin >> n >> m;
    vector<string> b(n);
    rep(i, n) {
        cin >> b[i];
    }

    vvll xl(n, vll(m));
    vvll xr(n, vll(m));
    vvll xu(n, vll(m));
    vvll xd(n, vll(m));

    auto x = xl;
    rep(i, n) {
        if (b[i][0] == '#') 
            x[i][0] = -1;
        else
            x[i][0] = 0;
        repi(j, 1, m) {
            if (b[i][j] == '#') {
                x[i][j] = -1;
            } else {
                x[i][j] = x[i][j-1] + 1;
            }
        }
    }
    xl = x;
//    cout << xl << endl;

    x = xr;
    rep(i, n) {
        if (b[i][m-1] == '#') 
            x[i][m-1] = -1;
        else
            x[i][m-1] = 0;
        for (ll j = m-2; j >= 0; j--) {
//            cout << mt(i, j) << endl;
            if (b[i][j] == '#') {
                x[i][j] = -1;
            } else {
                x[i][j] = x[i][j+1] + 1;
            }
        }
    }
    xr = x;
//    cout << xr << endl;

    x = xu;
    rep(j, m) {
        if (b[0][j] == '#') 
            x[0][j] = -1;
        else
            x[0][j] = 0;
        for (ll i = 1; i < n; i++) {
            if (b[i][j] == '#') {
                x[i][j] = -1;
            } else {
                x[i][j] = x[i-1][j] + 1;
            }
        }
    }
    xu=x;
//    cout << xu << endl;

    x = xd;
    rep(j, m) {
        if (b[n-1][j] == '#') 
            x[n-1][j] = -1;
        else
            x[n-1][j] = 0;
        for (ll i = n-2; i >= 0; i--) {
            if (b[i][j] == '#') {
                x[i][j] = -1;
            } else {
//                cout << mt(i, j, x.size(), x[0].size()) << endl;
                x[i][j] = x[i+1][j] + 1;
            }
        }
    }
    xd = x;

//    cout << xd << endl;


    ll ret = 0;
    rep(i, n) rep(j, m) if (b[i][j] != '#') {
        ret += xu[i][j] * xl[i][j];
        ret += xu[i][j] * xr[i][j];
        ret += xd[i][j] * xl[i][j];
        ret += xd[i][j] * xr[i][j];
    }
    cout << ret << endl;

    return 0;
}

Submission Info

Submission Time
Task C - 右折
User hamko
Language C++14 (GCC 5.4.1)
Score 400
Code Size 6977 Byte
Status
Exec Time 430 ms
Memory 161148 KB

Compile Error

./Main.cpp: In function ‘void vizGraph(vvll&, int, std::string)’:
./Main.cpp:38:478: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
 void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
                                                                                                                                                                                                                                                                                                                                              ...

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 430 ms 161020 KB
02.txt 429 ms 160892 KB
03.txt 430 ms 160892 KB
04.txt 429 ms 160636 KB
05.txt 370 ms 161020 KB
06.txt 373 ms 161148 KB
07.txt 372 ms 160892 KB
08.txt 371 ms 160764 KB
09.txt 357 ms 160892 KB
10.txt 357 ms 161020 KB
11.txt 356 ms 160892 KB
12.txt 359 ms 161020 KB
13.txt 363 ms 160764 KB
14.txt 363 ms 160636 KB
15.txt 359 ms 161148 KB
16.txt 357 ms 160892 KB
17.txt 338 ms 160764 KB
18.txt 338 ms 160892 KB
19.txt 357 ms 160636 KB
20.txt 356 ms 161020 KB
21.txt 372 ms 161148 KB
22.txt 371 ms 160892 KB
23.txt 369 ms 160764 KB
24.txt 372 ms 160892 KB
25.txt 361 ms 161020 KB
26.txt 360 ms 160892 KB
27.txt 365 ms 161020 KB
28.txt 361 ms 160764 KB
29.txt 1 ms 256 KB
30.txt 1 ms 256 KB
31.txt 1 ms 256 KB
32.txt 1 ms 256 KB
33.txt 1 ms 256 KB
34.txt 1 ms 256 KB
35.txt 1 ms 256 KB
36.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB