답안 #225170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
225170	2020-04-19T10:48:48 Z	Vimmer	Mobitel (COCI19_mobitel)	C++14	컴파일 오류	0 ms	0 KB

mobitel

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(1e9 + 7)

using namespace std;

typedef long long ll;

typedef long double ld;



ll a[305][305], dp[305][305], f[305][305], n, m, s, ans;

int mk[305][305];

vector <pair <ll, ll> >  vr;

unordered_map <pair <pair <pair <int, int>, int>, int>, ll> mp;

void rec(int x, int y, ll sm, ll kol);

ll calc(int x, int y, int xr, int yr)
{
    if (mp.find({{{x, y}, xr}, yr}) != mp.end()) return mp[{{{x, y}, xr}, yr}];

    for (int i = xr; i <= x; i++)
        for (int j = yr; j < y; j++) f[i][j] = 0;

    f[xr][yr] = 1;

    for (int i = xr; i <= x; i++)
        for (int j = yr; j <= y; j++)
        {
            if (a[i][j] != 1) continue;

            if (i != 0 && a[i - 1][j] == 1) f[i][j] = (f[i - 1][j] + f[i][j]) % MOD;

            if (j != 0 && a[i][j - 1] == 1) f[i][j] = (f[i][j - 1] + f[i][j]) % MOD;

        }

    mp[{{{x, y}, xr}, yr}] = f[x][y];

    return f[x][y];
}

void dfs(int x, int y, int xr, int yr, int id)
{
    if (mk[x][y] == id) return;

    mk[x][y] = id;

    if (x + 1 != n)
    {
        if (a[x + 1][y] == 1) dfs(x + 1, y, xr, yr, id);
          else rec(x + 1, y, vr[id - 1].F * a[x + 1][y], (vr[id - 1].S * calc(x, y, xr, yr)) % MOD);
    }

    if (y + 1 != m)
    {
        if (a[x][y + 1] == 1) dfs(x, y + 1, xr, yr, id);
          else rec(x, y + 1, vr[id - 1].F * a[x][y + 1], (vr[id - 1].S * calc(x, y, xr, yr)) % MOD);
    }
}

void rec(int x, int y, ll sm, ll kol)
{
    if (sm >= s) {ans = (ans + (kol * dp[x][y]) % MOD) % MOD; return;}

    if (a[x][y] == 1) {vr.pb({sm, kol}); dfs(x, y, x, y, sz(vr)); return;}

    if (x + 1 != n) rec(x + 1, y, sm * a[x + 1][y], kol);

    if (y + 1 != m) rec(x, y + 1, sm * a[x][y + 1], kol);
}


int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> a[i][j];

    dp[n - 1][m - 1] = 1;

    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
        {
            if (i + 1 != n) dp[i][j] = (dp[i][j] + dp[i + 1][j]) % MOD;

            if (j + 1 != m) dp[i][j] = (dp[i][j] + dp[i][j + 1]) % MOD;
        }

    rec(0, 0, a[0][0], 1);

    cout << ans << endl;
}

Compilation message

In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from mobitel.cpp:1:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>'
mobitel.cpp:30:61:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to '(const std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> >) (const std::pair<std::pair<std::pair<int, int>, int>, int>&)'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from mobitel.cpp:1:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >':
/usr/include/c++/7/bits/unordered_map.h:103:66:   required from 'class std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>'
mobitel.cpp:30:61:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_map:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from mobitel.cpp:1:
/usr/include/c++/7/bits/unordered_map.h: In instantiation of 'class std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>':
mobitel.cpp:30:61:   required from here
/usr/include/c++/7/bits/unordered_map.h:103:66: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
                                                                  ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:110:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:111:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:112:48: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::mapped_type mapped_type;
                                                ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:113:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:114:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:115:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:120:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:121:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:124:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:125:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:126:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:127:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:128:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:129:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:288:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:386:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_map.h:578:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:584:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:591:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
  insert(_Pair&& __x)
  ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:657:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_map.h:953:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_map.h:957:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > >, std::__detail::__is_noexcept_hash<std::pair<std::pair<std::pair<int, int>, int>, int>, std::hash<std::pair<std::pair<std::pair<int, int>, int>, int> > > > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
mobitel.cpp: In function 'll calc(int, int, int, int)':
mobitel.cpp:36:12: error: 'class std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>' has no member named 'find'
     if (mp.find({{{x, y}, xr}, yr}) != mp.end()) return mp[{{{x, y}, xr}, yr}];
            ^~~~
mobitel.cpp:36:43: error: 'class std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>' has no member named 'end'
     if (mp.find({{{x, y}, xr}, yr}) != mp.end()) return mp[{{{x, y}, xr}, yr}];
                                           ^~~
mobitel.cpp:36:59: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>' and '<brace-enclosed initializer list>')
     if (mp.find({{{x, y}, xr}, yr}) != mp.end()) return mp[{{{x, y}, xr}, yr}];
                                                           ^
mobitel.cpp:54:7: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::pair<std::pair<std::pair<int, int>, int>, int>, long long int>' and '<brace-enclosed initializer list>')
     mp[{{{x, y}, xr}, yr}] = f[x][y];
       ^