oj.uz

Submission #1088305

# Submission time Handle Problem Language Result Execution time Memory
1088305 2024-09-14T08:18:15 Z rlx0090 Split the sequence (APIO14_sequence) C++14
Compilation error
 0 ms 0 KB 
oj.uz
대회
문제
답안 목록
기여하기
답안 #1088294
#	제출 시각UTC+9	아이디	문제	언어	결과	실행 시간	메모리
1088294	2024-09-14 17:10:03	rlx0090	수열 (APIO14_sequence)	C++14	
71 / 100
2000 ms	100364 KB
sequence
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <string.h>
#include <stack>
#include <limits>
 
using namespace std;
int N, K;
long long p[100005], dp[201][100005];
long long minf = numeric_limits<long long>::min();
struct seg {
    long long k = 0, b = minf;
    seg() {}
    seg(long long _k, long long _b) :k(_k), b(_b) {}
    long long f(long long x) {
        return k * x + b;
    }
};
struct Node {
    Node * left = nullptr;
    Node * right = nullptr;
    seg s;
    ~Node() {
        if(left != nullptr) delete left;
        if(right != nullptr) delete right;
    }
};

void add(Node* cur, seg ns, int nl, int nr) {
    if(cur->s.b == minf && ns.b == minf) return;
    int m = (nl + nr) / 2;
    bool lef = cur->s.f(nl) < ns.f(nl);
    bool mid = cur->s.f(m) < ns.f(m);
    if(mid) swap(cur->s, ns);
    if(nl == nr) return;
    else if(lef != mid) {
        if(cur->left == nullptr) cur->left = new Node();
        add(cur->left, ns, nl, m);
    }
    else {
        if(cur->right == nullptr) cur->right = new Node();
        add(cur->right, ns, m + 1, nr);
    }
}
 
long long query(Node* cur, int x, int nl, int nr) {
    if(cur == nullptr) return 0;
    if(nl == nr) return cur->s.f(x);
    int m = (nl + nr) / 2;
    if(x <= m)
        return max(cur->s.f(x), query(cur->left, x, nl, m));
    else
        return max(cur->s.f(x), query(cur->right, x, m + 1, nr));
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> K;
    long long q;
    for(int i = 1; i <= N; ++i) {
        cin >> q;
        p[i] = p[i - 1] + q;
    }
    Node * tree;
    long long ans = 0;
    for(int k = 1; k <= K; ++k) {
        tree = new Node();
        for(int i = N - k - 1;  i >= 0; --i){
            add(tree, seg(p[i + 1], - p[i + 1] * p[i + 1] + p[N] * p[i + 1] + dp[k - 1][i + 1]), 0, 1000 * N);
            dp[k][i] = query(tree, p[i], 0, 1000 * N) - p[N] * p[i];
        }
        delete(tree);
    }
    ans = dp[K][0];
    cout << ans << '\n';
    int s = 0;
    for(int k = K; k >= 1; --k) {
        for(int i = s + 1; i <= N - k; ++i) {
            long long q = (p[N] - p[i]) * (p[i] - p[s]);
            if(ans - q == dp[k - 1][i] ) {
                cout << i << ' ';
                ans -= q;
                s = i;
                break;
            }
        }
    }
 
    return 0;
}

Compilation message

sequence.cpp:7:8: error: stray '#' in program
    7 | 답안 #1088294
      |      ^
sequence.cpp:8:3: error: invalid preprocessing directive #\U0000c81c\U0000cd9c
    8 | # 제출 시각UTC+9 아이디 문제 언어 결과 실행 시간 메모리
      |   ^~~~
sequence.cpp:9:14: error: invalid digit "9" in octal constant
    9 | 1088294 2024-09-14 17:10:03 rlx0090 수열 (APIO14_sequence) C++14
      |              ^~
sequence.cpp:2:1: error: 'oj' does not name a type
    2 | oj.uz
      | ^~
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/bits/postypes.h:98:11: error: 'ptrdiff_t' does not name a type
   98 |   typedef ptrdiff_t streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/10/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:126:26: error: declaration of 'operator new' as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:126:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:128:26: error: declaration of 'operator new []' as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:128:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:135:34: error: 'std::size_t' has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                  ^~~~~~
/usr/include/c++/10/new:137:36: error: 'std::size_t' has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                                    ^~~~~~
/usr/include/c++/10/new:140:26: error: declaration of 'operator new' as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:140:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:140:52: error: expected primary-expression before 'const'
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/10/new:142:26: error: declaration of 'operator new []' as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:142:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:142:54: error: expected primary-expression before 'const'
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                      ^~~~~
/usr/include/c++/10/new:174:33: error: declaration of 'operator new' as non-function
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:174:51: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                   ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:174:59: error: expected primary-expression before 'void'
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                           ^~~~
/usr/include/c++/10/new:176:33: error: declaration of 'operator new []' as non-function
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:176:53: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/new:176:61: error: expected primary-expression before 'void'
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                             ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:402:31: error: 'std::size_t' has not been declared
  402 |   template<typename _Tp, std::size_t _Size>
      |                               ^~~~~~
/usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope
  403 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid
  403 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
In file included from /usr/include/c++/10/bits/cxxabi_init_exception.h:38,
                 from /usr/include/c++/10/bits/exception_ptr.h:38,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
  433 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
In file included from /usr/include/c++/10/bits/cxxabi_init_exception.h:38,
                 from /usr/include/c++/10/bits/exception_ptr.h:38,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
  433 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid
  508 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid
 1351 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1360 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from sequence.cpp:13:
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1360 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c+