제출 #897507

#제출 시각아이디문제언어결과실행 시간메모리
897507Phan_Tien_DungK개의 묶음 (IZhO14_blocks)C++17
0 / 100
1 ms468 KiB
// #pragma GCC optimize("unroll-loops") // #pragma gcc optimize("Ofast") // #pragma GCC optimization("Ofast") // #pragma optimize(Ofast) #include <bits/stdc++.h> using namespace std; #define f first #define s second #define int long long #define sz(A) (int)A.size() #define m_p(A, B) make_pair(A, B) #define all(A) A.begin(), A.end() #define forcin(A, X, Y) for (int i = X; i <= Y; ++i) cin >> A[i] //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; void SetIO(string name) { if (fopen((name + ".INP").c_str(), "r")) { freopen((name + ".INP").c_str(), "r", stdin); freopen((name + ".OUT").c_str(), "w", stdout); } } template <class T> bool Minimize(T &a, T b) { if (a > b) return a = b, true; return false; } template <class T> bool Maximize(T &a, T b) { if (a < b) return a = b, true; return false; } const int INF = 4557430888798830399; const int MOD = 998244353; const int N = 100005; const int MX = 20; int n, k, spatab[N][20]; vector<int> cur, nex; int GetMax(int l, int r) { int lg = log2(r - l + 1); return max(spatab[l][lg], spatab[r - (1 << lg) + 1][lg]); } void Compute(int l, int r, int optl, int optr) { if (l > r) return; int m = l + r >> 1; ii best = m_p(INF, -1); for (int i = optl; i <= min(m, optr); ++i) { Minimize(best, m_p(cur[i - 1] + GetMax(i, m), i)); } nex[m] = best.f; int optm = best.s; Compute(l, m - 1, optl, optm); Compute(m + 1, r, optm, optr); } void Solve() { cin >> n >> k; cur.resize(n + 1, 0); nex.resize(n + 1, 0); for (int i = 1; i <= n; ++i) { cin >> spatab[i][0]; } for (int i = 1; (1 << i) <= n; ++i) { for (int j = 1; j + (1 << i) - 1 <= n; ++j) { spatab[j][i] = max(spatab[j][i - 1], spatab[j + (1 << i - 1)][i - 1]); } } for (int i = 1; i <= n; ++i) { cur[i] = GetMax(1, i); } for (int i = 1; i < k; ++i) { Compute(i + 1, n, i + 1, n); cur.swap(nex); } cout << cur[n]; } signed main() { cin.tie(0)->sync_with_stdio(false); clock_t tStart = clock(); SetIO("main"); int t = 1; // cin >> t; while (t--) { Solve(); } cerr << "\nTime Taken: "; cerr << fixed << setprecision(10) << (double)(clock() - tStart) / CLOCKS_PER_SEC; }

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In function 'void Compute(long long int, long long int, long long int, long long int)':
blocks.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int m = l + r >> 1;
      |          ~~^~~
blocks.cpp: In function 'void Solve()':
blocks.cpp:78:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |    spatab[j][i] = max(spatab[j][i - 1], spatab[j + (1 << i - 1)][i - 1]);
      |                                                          ~~^~~
blocks.cpp: In function 'void SetIO(std::string)':
blocks.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...