| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1088305 | rlx0090 | Split the sequence (APIO14_sequence) | C++14 | 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.
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 (stderr)
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+