| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1089663 | xnqs | K blocks (IZhO14_blocks) | C++17 | 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.
blocks
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdint>
const int BULAN = 6;
int x, p;
int arr[100005];
int sp_tb[17][100005];
int64_t dp[105][100005];
void build_sparse_table() {
for (int l = 1; l < 17; l++) {
for (int i = 1; i+(1<<l)-1 <= x; i++) {
sp_tb[l][i] = std::max(sp_tb[l-1][i], sp_tb[l-1][i+(1<<(l-1))]);
}
}
}
inline int max_query(int l, int r) {
int lvl = 31-__builtin_clz(r-l+1);
return std::max(sp_tb[lvl][l], sp_tb[lvl][r-(1<<lvl)+1]);
}
void calculate_dp() {
if (1LL*x*x*p<=50'000'000) {
dp[1][0] = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= x; i++) {
dp[1][i] = max_query(1,i);
}
for (int k = 2; k <= p; k++) {
for (int i = 0; i < k; i++) {
dp[k][i] = 0x3f3f3f3f3f3f3f3f;
}
for (int i = k; i <= x; i++) {
dp[k][i] = 0x3f3f3f3f3f3f3f3f;
for (int j = k; j <= i; j++) {
dp[k][i] = std::min(dp[k][i], dp[k-1][j-1] + max_query(j,i));
}
}
}
return;
}
dp[1][0] = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= x; i++) {
dp[1][i] = max_query(1,i);
}
for (int k = 2; k <= p; k++) {
std::priority_queue<std::pair<int64_t,int>> pq;
for (int i = 0; i < BULAN; i++) {
pq.emplace(0x3f3f3f3f3f3f3f3f,0);
}
for (int i = 0; i < k; i++) {
dp[k][i] = 0x3f3f3f3f3f3f3f3f;
pq.emplace(dp[k-1][i],i+1);
pq.pop();
}
for (int i = k; i <= x; i++) {
dp[k][i] = 0x3f3f3f3f3f3f3f3f;
auto tmp = pq;
while (!tmp.empty()) {
auto [opt_dp, idx] = tmp.top();
tmp.pop();
dp[k][i] = std::min(dp[k][i], opt_dp + max_query(idx,i));
}
pq.emplace(dp[k-1][i],i+1);
pq.pop();
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> p;
for (int i = 1; i <= x; i++) {
std::cin >> arr[i];
sp_tb[0][i] = arr[i];
}
build_sparse_table();
calculate_dp();
std::cout << dp[p][x] << "\n";
}
Compilation message (stderr)
blocks.cpp:1:1: error: 'blocks' does not name a type
1 | blocks
| ^~~~~~
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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
129 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/10/new:135:29: 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:31: 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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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:149:26: error: declaration of 'operator new' as non-function
149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
| ^~~~~~~~
/usr/include/c++/10/new:149:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
| ^~~~~~
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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/new:149:68: error: expected primary-expression before ')' token
149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
| ^
/usr/include/c++/10/new:150:41: error: attributes after parenthesized initializer ignored [-fpermissive]
150 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/10/new:151:26: error: declaration of 'operator new' as non-function
151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~~~~
/usr/include/c++/10/new:151:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~~
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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/new:151:68: error: expected primary-expression before ',' token
151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
| ^
/usr/include/c++/10/new:151:70: error: expected primary-expression before 'const'
151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~
/usr/include/c++/10/new:157:26: error: declaration of 'operator new []' as non-function
157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
| ^~~~~~~~
/usr/include/c++/10/new:157:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
| ^~~~~~
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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/new:157:70: error: expected primary-expression before ')' token
157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
| ^
/usr/include/c++/10/new:158:41: error: attributes after parenthesized initializer ignored [-fpermissive]
158 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/10/new:159:26: error: declaration of 'operator new []' as non-function
159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~~~~
/usr/include/c++/10/new:159:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~~
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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/new:159:70: error: expected primary-expression before ',' token
159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
| ^
/usr/include/c++/10/new:159:72: error: expected primary-expression before 'const'
159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
| ^~~~~
/usr/include/c++/10/new:166:29: error: 'std::size_t' has not been declared
166 | void operator delete(void*, std::size_t, std::align_val_t)
| ^~~
/usr/include/c++/10/new:168:31: error: 'std::size_t' has not been declared
168 | void operator delete[](void*, std::size_t, std::align_val_t)
| ^~~
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/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 blocks.cpp:5:
/usr/include/c++/10/type_traits:402:26: error: 'std::si