Submission #270332

#	Time	Username	Problem	Language	Result	Execution time	Memory
270332		anubhavdhar	Split the sequence (APIO14_sequence)	C++11	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

sequence

#include<bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define FOR(i,N) for(i=0;i<(N);++i) #define FORe(i,N) for(i=1;i<=(N);++i) #define FORr(i,a,b) for(i=(a);i<(b);++i) #define FORrev(i,N) for(i=(N);i>=0;--i) #define F0R(i,N) for(int i=0;i<(N);++i) #define F0Re(i,N) for(int i=1;i<=(N);++i) #define F0Rr(i,a,b) for(ll i=(a);i<(b);++i) #define F0Rrev(i,N) for(int i=(N);i>=0;--i) #define all(v) (v).begin(),(v).end() #define dbgLine cerr<<" LINE : "<<__LINE__<<"\n" #define ldd long double using namespace std; const int Alp = 26; const int __PRECISION = 9; const int inf = 1e9 + 8; const ldd PI = acos(-1); const ldd EPS = 1e-7; const ll MOD = 1e9 + 7; const ll MAXN = 1e5 + 5; const ll ROOTN = 320; const ll LOGN = 18; const ll INF = 1e18 + 1022; ll dp[MAXN][201], pre[MAXN], par[MAXN][201]; int N, K; struct line //mx + c { mutable ll m, c, p; bool operator < (const line& o) const {return m < o.m;} bool operator < (ll x) const {return p < x;} }; struct CHT_black_box : multiset<line, less<>> { int mode; CHT_black_box(){mode = 1;} void set_mode(string S) {mode = (S[1] == 'i' || S[1] == 'I') ? -1 : 1;} ll div(ll a, ll b) {return a/b - ((a^b) < 0 && a%b);} bool isect(iterator x, iterator y) { if(y == end()){x->p = INF; return false;} if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF; else x->p = div((y->c - x->c),(x->m - y->m)); return (x->p >= y->p); } void add(ll slope, ll intercept) { auto z = insert({mode * slope, mode * intercept, 0}), y = z++, x = y; while(isect(y, z)) z = erase(z); if(x != begin() && isect(--x, y)) isect(x, y = erase(y)); while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return mode * (l.m * x + l.c); } }box[201]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll p, q = INF; assert(N < MAXN); cin>>N>>K; pre[0] = 0; F0Re(i, N) cin>>p, pre[i] = p + pre[i-1]; p = 0; // F0Re(i, N) // cout<<pre[i]<<' '; // cout<<endl; F0R(i, N+1) F0R(j, K+1) dp[i][j] = par[i][j] = 0; // F0Rr(k, j-1, i) dp[i][j] = max(dp[k][j-1] + pre[N]*pre[i] - pre[i]*pre[i] - pre[N]*pre[k] + pre[i]*pre[k]), dp[i][j]); F0Re(i, N) { F0Re(j, min(i, K)) { if(j == 1) dp[i][j] = pre[i]*(pre[N] - pre[i]); else {pll v = box[j-1].query(pre[i]); dp[i][j] = pre[N]*pre[i] - pre[i]*pre[i] + v.ff; par[i][j] = v.ss;} // p = max(p, dp[i][j]); } if(i >= K) p = max(p, dp[i][K]); F0Re(j,min(i, K)) box[j].add(pre[i], dp[i][j] - pre[i] * pre[N], i); } cout<<p<<'\n'; F0Re(i, N) if(dp[i][K] == p) { q = i; break; } while(q and K) { cout<<q<<' '; q = par[q][K--]; } return 0; }

Compilation message (stderr)

sequence.cpp:51:43: error: wrong number of template arguments (0, should be 1)
   51 | struct CHT_black_box : multiset<line, less<>>
      |                                           ^
In file included from /usr/include/c++/9/string:48,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/stl_function.h:381:12: note: provided for 'template<class _Tp> struct std::less'
  381 |     struct less : public binary_function<_Tp, _Tp, bool>
      |            ^~~~
sequence.cpp:51:44: error: template argument 2 is invalid
   51 | struct CHT_black_box : multiset<line, less<>>
      |                                            ^~
sequence.cpp:57:13: error: 'iterator' is not a type
   57 |  bool isect(iterator x, iterator y)
      |             ^~~~~~~~
sequence.cpp:57:25: error: 'iterator' is not a type
   57 |  bool isect(iterator x, iterator y)
      |                         ^~~~~~~~
sequence.cpp: In member function 'bool CHT_black_box::isect(int, int)':
sequence.cpp:59:15: error: no matching function for call to 'end()'
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
                 from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/initializer_list:99:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/9/initializer_list:99:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:68:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(_Container&)'
   68 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/9/bits/range_access.h:68:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:78:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(const _Container&)'
   78 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/9/bits/range_access.h:78:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:97:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> _Tp* std::end(_Tp (&)[_Nm])'
   97 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/9/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/9/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/9/valarray:1234:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/9/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/9/valarray:1244:5: note:   template argument deduction/substitution failed:
sequence.cpp:59:15: note:   candidate expects 1 argument, 0 provided
   59 |   if(y == end()){x->p = INF; return false;}
      |               ^
sequence.cpp:59:19: error: base operand of '->' is not a pointer
   59 |   if(y == end()){x->p = INF; return false;}
      |                   ^~
sequence.cpp:60:7: error: base operand of '->' is not a pointer
   60 |   if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
      |       ^~
sequence.cpp:60:15: error: base operand of '->' is not a pointer
   60 |   if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
      |               ^~
sequence.cpp:60:21: error: base operand of '->' is not a pointer
   60 |   if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
      |                     ^~
sequence.cpp:60:29: error: base operand of '->' is not a pointer
   60 |   if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
      |                             ^~
sequence.cpp:60:36: error: base operand of '->' is not a pointer
   60 |   if(x->m == y->m) x->p = (x->c > y->c) ? INF : -INF;
      |                                    ^~
sequence.cpp:61:9: error: base operand of '->' is not a pointer
   61 |   else x->p = div((y->c - x->c),(x->m - y->m));
      |         ^~
sequence.cpp:61:21: error: base operand of '->' is not a pointer
   61 |   else x->p = div((y->c - x->c),(x->m - y->m));
      |                     ^~
sequence.cpp:61:28: error: base operand of '->' is not a pointer
   61 |   else x->p = div((y->c - x->c),(x->m - y->m));
      |                            ^~
sequence.cpp:61:35: error: base operand of '->' is not a pointer
   61 |   else x->p = div((y->c - x->c),(x->m - y->m));
      |                                   ^~
sequence.cpp:61:42: error: base operand of '->' is not a pointer
   61 |   else x->p = div((y->c - x->c),(x->m - y->m));
      |                                          ^~
sequence.cpp:62:12: error: base operand of '->' is not a pointer
   62 |   return (x->p >= y->p);
      |            ^~
sequence.cpp:62:20: error: base operand of '->' is not a pointer
   62 |   return (x->p >= y->p);
      |                    ^~
sequence.cpp: In member function 'void CHT_black_box::add(long long int, long long int)':
sequence.cpp:66:12: error: 'insert' was not declared in this scope; did you mean 'isect'?
   66 |   auto z = insert({mode * slope, mode * intercept, 0}), y = z++, x = y;
      |            ^~~~~~
      |            isect
sequence.cpp:67:15: error: 'y' was not declared in this scope
   67 |   while(isect(y, z)) z = erase(z);
      |               ^
sequence.cpp:67:26: error: 'erase' was not declared in this scope
   67 |   while(isect(y, z)) z = erase(z);
      |                          ^~~~~
sequence.cpp:68:6: error: 'x' was not declared in this scope
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |      ^
sequence.cpp:68:17: error: no matching function for call to 'begin()'
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
                 from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/initializer_list:89:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   89 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/9/initializer_list:89:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:48:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
   48 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:58:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)'
   58 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:58:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:87:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> _Tp* std::begin(_Tp (&)[_Nm])'
   87 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:87:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/9/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/9/valarray:1214:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/9/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/9/valarray:1224:5: note:   template argument deduction/substitution failed:
sequence.cpp:68:17: note:   candidate expects 1 argument, 0 provided
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                 ^
sequence.cpp:68:33: error: 'y' was not declared in this scope
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                 ^
sequence.cpp:68:50: error: 'erase' was not declared in this scope
   68 |   if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                                  ^~~~~
sequence.cpp:69:10: error: 'y' was not declared in this scope
   69 |   while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |          ^
sequence.cpp:69:12: error: 'x' was not declared in this scope
   69 |   while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |            ^
sequence.cpp:69:24: error: no matching function for call to 'begin()'
   69 |   while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                        ^
In file included from /usr/include/c++/9/bits/range_access.h:36,
                 from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/initializer_list:89:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   89 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/9/initializer_list:89:5: note:   template argument deduction/substitution failed:
sequence.cpp:69:24: note:   candidate expects 1 argument, 0 provided
   69 |   while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                        ^
In file included from /usr/include/c++/9/string:54,
                 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 sequence.cpp:1:
/usr/include/c++/9/bits/range_access.h:48:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
   48 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
sequence.cpp:69:24: note:   candidate expects 1 argument, 0 provided
   69 |   while((y=x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
      |                        ^
In file included from /usr/include/c++/9/string:54,
                 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,