Submission #1133423

#TimeUsernameProblemLanguageResultExecution timeMemory
1133423wavydangSkyscraper (JOI16_skyscraper)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> //#include "debug.h" using namespace std; #define pb push_back typedef long long ll; const int MOD = 1e9 + 7; const int MX = 300000; int N, L; vector<int> bs; template<class T> T invGeneral(T a, T b) { a %= b; if (a == 0) return b == 1 ? 0 : -1; T x = invGeneral(b,a); return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b; } template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; } template<class A, class B> A operator-=(A& l, const B& r) { return l = l-r; } template<class A, class B> A operator*=(A& l, const B& r) { return l = l*r; } template<class A, class B> A operator/=(A& l, const B& r) { return l = l/r; } template<class T> struct modInt { T val; T mod = 0; // static const T mod = MOD; void normalize() { if (mod == 0) return; val %= mod; if (val < 0) val += mod; } modInt(T v = 0, T m = 0) : val(v), mod(m) { normalize(); } // modInt(T v = 0, T m = 0) : val(v) { normalize(); } explicit operator T() const { return val; } friend ostream& operator<<(ostream& os, const modInt& a) { return os << a.val; } friend bool operator==(const modInt& a, const modInt& b) { return a.val == b.val; } friend bool operator!=(const modInt& a, const modInt& b) { return !(a == b); } friend void check(modInt& a, modInt& b) { // make sure all operations are valid // comment out if mod is static const if (a.mod > 0 && b.mod > 0) { assert(a.mod == b.mod); return; } T mod = max(a.mod,b.mod); if (mod == 0) mod = MOD; if (a.mod != mod) { a.mod = mod; a.normalize(); } if (b.mod != mod) { b.mod = mod; b.normalize(); } } friend modInt operator+(modInt a, modInt b) { check(a,b); a.val += (T)b; if (a.val >= a.mod) a.val -= a.mod; return a; } friend modInt operator-(modInt a, modInt b) { check(a,b); a.val -= (T)b; if (a.val < 0) a.val += a.mod; return a; } friend modInt operator-(const modInt& a) { return modInt(0)-a; } friend modInt operator*(modInt a, modInt b) { check(a,b); a.val = (ll)a.val*(T)b%a.mod; return a; } friend modInt exp(modInt a, ll p) { modInt ans(1,a.mod); for (; p; p /= 2, a *= a) if (p&1) ans *= a; return ans; } friend modInt inv(const modInt& a) { //return {invGeneral(a.val,a.mod),a.mod}; return exp(a,a.mod-2); } friend modInt operator/(modInt a, modInt b) { check(a,b); return a*inv(b); } }; typedef modInt<ll> mi; mi dp[101][101][1001][2][2]; //what is the maximal cost mi dfs(int i, int comp, int cst, int lend, int rend){ int cstp = cst + (bs[i] - bs[i - 1]) * (2*comp + lend + rend); if (cstp > L) return 0; if (comp < 0) return 0; if (i == N){ if (comp == 0) return 1; else return 0; } if (dp[i][comp][cst][lend][rend] != 0) return dp[i][comp][cst][lend][rend]; mi val = 0; //sps lend, rend aren't comp val += dfs(i + 1, comp, cstp, 1, rend); //add to left end val += dfs(i + 1, comp - 1, cstp, 1, rend) * comp; //join middle to left val += dfs(i + 1, comp, cstp, lend, 1); //add to right val += dfs(i + 1, comp - 1, cstp, lend, 1); //join middle to right if (comp > 1) val += dfs(i + 1, comp - 1, cstp, lend, rend) * (comp) * (comp - 1); //merge two comps in the middle val += dfs(i + 1, comp, cstp, lend, rend) * 2*comp; //add to a component val += dfs(i + 1, comp + 1, cstp, lend, rend); //start new one dp[i][comp][cst][lend][rend] = val; //tuple t = {i, comp, cst, lend, rend}; // debug(t); // debug((ll) dp[i][comp][cst][lend][rend]); return val; } int main(){ cin >> N >> L; memset(dp, 0, sizeof(dp)); for (int i = 0; i < N; i++){ int x; cin >> x; bs.pb(x); } sort(bs.begin(), bs.end()); bs.insert(bs.begin(), bs[0]); cout << dfs(1, 0, 0, 0, 0); }

Compilation message (stderr)

In file included from /usr/include/c++/11/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/fs_path.h: In instantiation of 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::filesystem::__cxx11::path::generic_string(const _Allocator&) const [with _CharT = char; _Traits = std::char_traits<char>; _Allocator = std::allocator<char>]':
/usr/include/c++/11/bits/fs_path.h:1163:32:   required from here
/usr/include/c++/11/bits/fs_path.h:1150:21: error: ambiguous overload for 'operator+=' (operand types are 'std::__cxx11::basic_string<char>' and 'std::__cxx11::basic_string<char>::__sv_type' {aka 'std::basic_string_view<char>'})
 1150 |               __str += basic_string_view<value_type>(__elem._M_pathname);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/basic_string.h:1203:9: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator+=(const _Tp&) [with _Tp = std::basic_string_view<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> = std::__cxx11::basic_string<char>&]'
 1203 |         operator+=(const _Tp& __svt)
      |         ^~~~~~~~
skyscraper.cpp:17:30: note: candidate: 'A operator+=(A&, const B&) [with A = std::__cxx11::basic_string<char>; B = std::basic_string_view<char>]'
   17 | template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; }
      |                              ^~~~~~~~
In file included from /usr/include/c++/11/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/fs_path.h: In instantiation of 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::filesystem::__cxx11::path::generic_string(const _Allocator&) const [with _CharT = wchar_t; _Traits = std::char_traits<wchar_t>; _Allocator = std::allocator<wchar_t>]':
/usr/include/c++/11/bits/fs_path.h:1168:35:   required from here
/usr/include/c++/11/bits/fs_path.h:1150:21: error: ambiguous overload for 'operator+=' (operand types are 'std::__cxx11::basic_string<char>' and 'std::__cxx11::basic_string<char>::__sv_type' {aka 'std::basic_string_view<char>'})
 1150 |               __str += basic_string_view<value_type>(__elem._M_pathname);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/basic_string.h:1203:9: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator+=(const _Tp&) [with _Tp = std::basic_string_view<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> = std::__cxx11::basic_string<char>&]'
 1203 |         operator+=(const _Tp& __svt)
      |         ^~~~~~~~
skyscraper.cpp:17:30: note: candidate: 'A operator+=(A&, const B&) [with A = std::__cxx11::basic_string<char>; B = std::basic_string_view<char>]'
   17 | template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; }
      |                              ^~~~~~~~
In file included from /usr/include/c++/11/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/fs_path.h: In instantiation of 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::filesystem::__cxx11::path::generic_string(const _Allocator&) const [with _CharT = char8_t; _Traits = std::char_traits<char8_t>; _Allocator = std::allocator<char8_t>]':
/usr/include/c++/11/bits/fs_path.h:1174:35:   required from here
/usr/include/c++/11/bits/fs_path.h:1150:21: error: ambiguous overload for 'operator+=' (operand types are 'std::__cxx11::basic_string<char>' and 'std::__cxx11::basic_string<char>::__sv_type' {aka 'std::basic_string_view<char>'})
 1150 |               __str += basic_string_view<value_type>(__elem._M_pathname);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/basic_string.h:1203:9: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator+=(const _Tp&) [with _Tp = std::basic_string_view<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> = std::__cxx11::basic_string<char>&]'
 1203 |         operator+=(const _Tp& __svt)
      |         ^~~~~~~~
skyscraper.cpp:17:30: note: candidate: 'A operator+=(A&, const B&) [with A = std::__cxx11::basic_string<char>; B = std::basic_string_view<char>]'
   17 | template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; }
      |                              ^~~~~~~~
In file included from /usr/include/c++/11/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/fs_path.h: In instantiation of 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::filesystem::__cxx11::path::generic_string(const _Allocator&) const [with _CharT = char16_t; _Traits = std::char_traits<char16_t>; _Allocator = std::allocator<char16_t>]':
/usr/include/c++/11/bits/fs_path.h:1183:36:   required from here
/usr/include/c++/11/bits/fs_path.h:1150:21: error: ambiguous overload for 'operator+=' (operand types are 'std::__cxx11::basic_string<char>' and 'std::__cxx11::basic_string<char>::__sv_type' {aka 'std::basic_string_view<char>'})
 1150 |               __str += basic_string_view<value_type>(__elem._M_pathname);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/basic_string.h:1203:9: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator+=(const _Tp&) [with _Tp = std::basic_string_view<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> = std::__cxx11::basic_string<char>&]'
 1203 |         operator+=(const _Tp& __svt)
      |         ^~~~~~~~
skyscraper.cpp:17:30: note: candidate: 'A operator+=(A&, const B&) [with A = std::__cxx11::basic_string<char>; B = std::basic_string_view<char>]'
   17 | template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; }
      |                              ^~~~~~~~
In file included from /usr/include/c++/11/filesystem:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:129,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/fs_path.h: In instantiation of 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::filesystem::__cxx11::path::generic_string(const _Allocator&) const [with _CharT = char32_t; _Traits = std::char_traits<char32_t>; _Allocator = std::allocator<char32_t>]':
/usr/include/c++/11/bits/fs_path.h:1187:36:   required from here
/usr/include/c++/11/bits/fs_path.h:1150:21: error: ambiguous overload for 'operator+=' (operand types are 'std::__cxx11::basic_string<char>' and 'std::__cxx11::basic_string<char>::__sv_type' {aka 'std::basic_string_view<char>'})
 1150 |               __str += basic_string_view<value_type>(__elem._M_pathname);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from skyscraper.cpp:1:
/usr/include/c++/11/bits/basic_string.h:1203:9: note: candidate: 'std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::operator+=(const _Tp&) [with _Tp = std::basic_string_view<char>; _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::_If_sv<_Tp, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&> = std::__cxx11::basic_string<char>&]'
 1203 |         operator+=(const _Tp& __svt)
      |         ^~~~~~~~
skyscraper.cpp:17:30: note: candidate: 'A operator+=(A&, const B&) [with A = std::__cxx11::basic_string<char>; B = std::basic_string_view<char>]'
   17 | template<class A, class B> A operator+=(A& l, const B& r) { return l = l+r; }
      |                              ^~~~~~~~