Submission #380608

#	Time	Username	Problem	Language	Result	Execution time	Memory
380608		smjleo	Skyscraper (JOI16_skyscraper)	C++14	Compilation error	0 ms	0 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 105;
const int L = 1005;

int n, l, arr[N], dp[N][N][L][3];

signed main() {
    io;
    cin >> n >> l;
    for (int i=1; i<=n; i++) cin >> arr[i];

    if (n == 1) {
        cout << 1 < nl;
        return 0;
    }

    sort(arr, arr+n+1);
    arr[n+1] = 1e9;

    dp[0][0][0][0] = 1;
    
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=i; j++) {
            for (int k=0; k<=l; k++) {
                for (int m=0; m<3; m++) {
                    // i: index, j: components, k: sum, m: ends
                    int dc = (2*j-m) * (arr[i+1] - arr[i]);
                    // difference in cost. each component contributes 2*j except for the m ones which contribute 1

                    if (dc > k) continue;   // cost too much lol

                    // we can create a new component that isn't the end
                    dp[i][j][k][m] += dp[i-1][j-1][k-dc][m];

                    // we can create a new component that is the end
                    if (m) dp[i][j][k][m] += (3-m) * dp[i-1][j-1][k-dc][m-1];

                    // we can join an existing component but not combine
                    dp[i][j][k][m] += (2*j-m) * dp[i-1][j][k-dc][m];

                    // we can join two existing components [[...]X[...]]
                    if (m == 0) {
                        dp[i][j][k][m] += j*(j+1)*dp[i-1][j+1][k-dc][m];
                        // for each of the j+1 i can match with j
                    } else if (m == 1) {
                        dp[i][j][k][m] += j*j*dp[i-1][j+1][k-dc][m];
                        // for each of the j (because end cannot) i can match with j
                    } else {
                        if (i == n) dp[i][j][k][m] += dp[i-1][j+1][k-dc][m];
                        else dp[i][j][k][m] += j*(j-1)*dp[i-1][j+1][k-dc][m];
                        // for each of the j-1 (because ends cannot) i can match with j
                    }

                    // we can bring an existing component to the end
                    if (m == 1) {
                        dp[i][j][k][m] += (2*j) * dp[i-1][j][k-dc][m-1];    // 2j components to select from (two ends of each)
                    } else if (m == 2) {
                        if (i == n) dp[i][j][k][m] += dp[i-1][j][k-dc][m-1];    // only one thing to select from
                        else if (j) dp[i][j][k][m] += (j-1) * dp[i-1][j][k-dc][m-1];   // j-1 components to select from (one end of each except other end)
                    }

                    dp[i][j][k][m] %= mod;
                }       
            }
        }
    }
    int ans = 0;
    for (int i=0; i<=l; i++) {
        ans += dp[n][1][i][2];
        ans %= mod;
    }

    cout << ans << nl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:19: error: no match for 'operator<' (operand types are 'std::basic_ostream<char>' and 'char')
   23 |         cout << 1 < nl;
      |         ~~~~~~~~~ ^
      |              |
      |              std::basic_ostream<char>
skyscraper.cpp:23:19: note: candidate: 'operator<(int, int)' <built-in>
   23 |         cout << 1 < nl;
      |                   ^
skyscraper.cpp:23:19: note:   no known conversion for argument 1 from 'std::basic_ostream<char>' to 'int'
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1048:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1048 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1048:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1124:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1124 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1124:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1198:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1198 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1198:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1272:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1272 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1272:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'char'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1346:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1346 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1346:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1421:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1421 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1421:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'char'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/regex.h:1499:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1499 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1499:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_pair.h:454:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  454 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:454:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::pair<_T1, _T2>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:331:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  331 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:331:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::reverse_iterator<_Iterator>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:369:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  369 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:369:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::reverse_iterator<_Iterator>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:1163:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1163 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1163:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::move_iterator<_IteratorL>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
                 from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_iterator.h:1169:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1169 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1169:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::move_iterator<_IteratorL>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/basic_string.h:6226:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6226 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6226:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/basic_string.h:6239:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)'
 6239 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6239:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/string:55,
                 from /usr/include/c++/9/bits/locale_classes.h:40,
                 from /usr/include/c++/9/bits/ios_base.h:41,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/basic_string.h:6251:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6251 |     operator<(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6251:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   mismatched types 'const _CharT*' and 'std::basic_ostream<char>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/bits/ios_base.h:46,
                 from /usr/include/c++/9/ios:42,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/9/system_error:208:3: note: candidate: 'bool std::operator<(const std::error_code&, const std::error_code&)'
  208 |   operator<(const error_code& __lhs, const error_code& __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/9/system_error:208:31: note:   no known conversion for argument 1 from 'std::basic_ostream<char>' to 'const std::error_code&'
  208 |   operator<(const error_code& __lhs, const error_code& __rhs) noexcept
      |             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/9/system_error:282:3: note: candidate: 'bool std::operator<(const std::error_condition&, const std::error_condition&)'
  282 |   operator<(const error_condition& __lhs,
      |   ^~~~~~~~
/usr/include/c++/9/system_error:282:36: note:   no known conversion for argument 1 from 'std::basic_ostream<char>' to 'const std::error_condition&'
  282 |   operator<(const error_condition& __lhs,
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:68,
                 from skyscraper.cpp:1:
/usr/include/c++/9/bits/stl_deque.h:312:5: note: candidate: 'template<class _Tp, class _Ref, class _Ptr> bool std::operator<(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)'
  312 |     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
      |     ^~~~~~~~
/usr/include/c++/9/bits/stl_deque.h:312:5: note:   template argument deduction/substitution failed:
skyscraper.cpp:6:12: note:   'std::basic_ostream<char>' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
    6 | #define nl '\n'
      |            ^~~~
skyscraper.cpp:23:21: note: in expansion of macro 'nl'
   23 |         cout << 1 < nl;
      |                     ^~
In file included from /usr/include/c++/9/deque:67,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:68,
                 from /var/local/lib/isolate/159/box/prog