답안 #956868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956868 2024-04-02T15:10:22 Z Trisanu_Das Building Bridges (CEOI17_building) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 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 l.k * x + l.m;
	}
};

int main(){
  int n; cin >> n;
  int h[n + 2], w[n + 2], dp[n + 1];
  for(int i = 1; i <= n; i++) cin >> h[i];
  for(int i = 1; i <= n; i++) cin >> w[i];
  LineContainer hull;
  dp[1] = -w[i];
  for(int i = 2; i <= n; i++){
    hull.add(2 * h[i - 1], h[i - 1] * h[i - 1] + dp[i - 1]);
    dp[i] = hull.query(h[i]) + h[i] * h[i] - w[i];
  }
  cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
}

Compilation message

building.cpp:5:10: error: 'll' does not name a type
    5 |  mutable ll k, m, p;
      |          ^~
building.cpp:7:17: error: 'll' has not been declared
    7 |  bool operator<(ll x) const { return p < x; }
      |                 ^~
building.cpp: In member function 'bool Line::operator<(const Line&) const':
building.cpp:6:47: error: 'k' was not declared in this scope
    6 |  bool operator<(const Line& o) const { return k < o.k; }
      |                                               ^
building.cpp:6:53: error: 'const struct Line' has no member named 'k'
    6 |  bool operator<(const Line& o) const { return k < o.k; }
      |                                                     ^
building.cpp: In member function 'bool Line::operator<(int) const':
building.cpp:7:38: error: 'p' was not declared in this scope
    7 |  bool operator<(ll x) const { return p < x; }
      |                                      ^
building.cpp: At global scope:
building.cpp:12:15: error: 'll' does not name a type
   12 |  static const ll inf = LLONG_MAX;
      |               ^~
building.cpp:13:2: error: 'll' does not name a type
   13 |  ll div(ll a, ll b) { // floored division
      |  ^~
building.cpp:21:11: error: 'll' has not been declared
   21 |  void add(ll k, ll m) {
      |           ^~
building.cpp:21:17: error: 'll' has not been declared
   21 |  void add(ll k, ll m) {
      |                 ^~
building.cpp:28:2: error: 'll' does not name a type
   28 |  ll query(ll x) {
      |  ^~
building.cpp: In member function 'bool LineContainer::isect(std::multiset<Line, std::less<void> >::iterator, std::multiset<Line, std::less<void> >::iterator)':
building.cpp:16:29: error: 'const struct Line' has no member named 'p'
   16 |   if (y == end()) return x->p = inf, 0;
      |                             ^
building.cpp:16:33: error: 'inf' was not declared in this scope; did you mean 'ynf'?
   16 |   if (y == end()) return x->p = inf, 0;
      |                                 ^~~
      |                                 ynf
building.cpp:17:10: error: 'const struct Line' has no member named 'k'
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |          ^
building.cpp:17:18: error: 'const struct Line' has no member named 'k'
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                  ^
building.cpp:17:24: error: 'const struct Line' has no member named 'p'
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                        ^
building.cpp:17:31: error: 'const struct Line' has no member named 'm'
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                               ^
building.cpp:17:38: error: 'const struct Line' has no member named 'm'
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                                      ^
building.cpp:17:42: error: 'inf' was not declared in this scope; did you mean 'ynf'?
   17 |   if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
      |                                          ^~~
      |                                          ynf
building.cpp:18:11: error: 'const struct Line' has no member named 'p'
   18 |   else x->p = div(y->m - x->m, x->k - y->k);
      |           ^
building.cpp:18:22: error: 'const struct Line' has no member named 'm'
   18 |   else x->p = div(y->m - x->m, x->k - y->k);
      |                      ^
building.cpp:18:29: error: 'const struct Line' has no member named 'm'
   18 |   else x->p = div(y->m - x->m, x->k - y->k);
      |                             ^
building.cpp:18:35: error: 'const struct Line' has no member named 'k'
   18 |   else x->p = div(y->m - x->m, x->k - y->k);
      |                                   ^
building.cpp:18:42: error: 'const struct Line' has no member named 'k'
   18 |   else x->p = div(y->m - x->m, x->k - y->k);
      |                                          ^
building.cpp:19:13: error: 'const struct Line' has no member named 'p'
   19 |   return x->p >= y->p;
      |             ^
building.cpp:19:21: error: 'const struct Line' has no member named 'p'
   19 |   return x->p >= y->p;
      |                     ^
building.cpp: In member function 'void LineContainer::add(int, int)':
building.cpp:22:28: error: no matching function for call to 'LineContainer::insert(<brace-enclosed initializer list>)'
   22 |   auto z = insert({k, m, 0}), y = z++, x = y;
      |                            ^
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from building.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:502:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
  502 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:502:32: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const Line&'}
  502 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:507:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
  507 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:507:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<Line, std::less<void> >::value_type&&' {aka 'Line&&'}
  507 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
  532 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:532:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:537:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::value_type = Line]'
  537 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:537:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_multiset.h:551:2: note: candidate: 'template<class _InputIterator> void std::multiset<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>]'
  551 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:551:2: note:   template argument deduction/substitution failed:
building.cpp:22:28: note:   candidate expects 2 arguments, 1 provided
   22 |   auto z = insert({k, m, 0}), y = z++, x = y;
      |                            ^
In file included from /usr/include/c++/10/set:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from building.cpp:1:
/usr/include/c++/10/bits/stl_multiset.h:563:7: note: candidate: 'void std::multiset<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>]'
  563 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:563:43: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<Line>'
  563 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_multiset.h:583:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type]'
  583 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:583:26: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::multiset<Line, std::less<void> >::node_type&&' {aka 'std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type&&'}
  583 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_multiset.h:588:7: note: candidate: 'std::multiset<_Key, _Compare, _Alloc>::iterator std::multiset<_Key, _Compare, _Alloc>::insert(std::multiset<_Key, _Compare, _Alloc>::const_iterator, std::multiset<_Key, _Compare, _Alloc>::node_type&&) [with _Key = Line; _Compare = std::less<void>; _Alloc = std::allocator<Line>; std::multiset<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::const_iterator; std::multiset<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<Line, Line, std::_Identity<Line>, std::less<void>, std::allocator<Line> >::node_type]'
  588 |       insert(const_iterator __hint, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_multiset.h:588:7: note:   candidate expects 2 arguments, 1 provided
building.cpp:23:16: error: 'y' was not declared in this scope; did you mean 'yn'?
   23 |   while (isect(y, z)) z = erase(z);
      |                ^
      |                yn
building.cpp:24:7: error: 'x' was not declared in this scope
   24 |   if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |       ^
building.cpp:24:34: error: 'y' was not declared in this scope; did you mean 'yn'?
   24 |   if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
      |                                  ^
      |                                  yn
building.cpp:25:11: error: 'y' was not declared in this scope; did you mean 'yn'?
   25 |   while ((y = x) != begin() && (--x)->p >= y->p)
      |           ^
      |           yn
building.cpp:25:15: error: 'x' was not declared in this scope
   25 |   while ((y = x) != begin() && (--x)->p >= y->p)
      |               ^
building.cpp: In function 'int main()':
building.cpp:41:14: error: 'i' was not declared in this scope
   41 |   dp[1] = -w[i];
      |              ^
building.cpp:44:18: error: 'struct LineContainer' has no member named 'query'
   44 |     dp[i] = hull.query(h[i]) + h[i] * h[i] - w[i];
      |                  ^~~~~
building.cpp:46:46: error: no matching function for call to 'accumulate(int*, int*)'
   46 |   cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
      |                                              ^
In file included from /usr/include/c++/10/numeric:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
                 from building.cpp:1:
/usr/include/c++/10/bits/stl_numeric.h:134:5: note: candidate: 'template<class _InputIterator, class _Tp> _Tp std::accumulate(_InputIterator, _InputIterator, _Tp)'
  134 |     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
      |     ^~~~~~~~~~
/usr/include/c++/10/bits/stl_numeric.h:134:5: note:   template argument deduction/substitution failed:
building.cpp:46:46: note:   candidate expects 3 arguments, 2 provided
   46 |   cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
      |                                              ^
In file included from /usr/include/c++/10/numeric:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:84,
                 from building.cpp:1:
/usr/include/c++/10/bits/stl_numeric.h:161:5: note: candidate: 'template<class _InputIterator, class _Tp, class _BinaryOperation> _Tp std::accumulate(_InputIterator, _InputIterator, _Tp, _BinaryOperation)'
  161 |     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
      |     ^~~~~~~~~~
/usr/include/c++/10/bits/stl_numeric.h:161:5: note:   template argument deduction/substitution failed:
building.cpp:46:46: note:   candidate expects 4 arguments, 2 provided
   46 |   cout << dp[n] + accumulate(w + 1, w + n + 1) << '\n';
      |                                              ^