제출 #492419

#제출 시각아이디문제언어결과실행 시간메모리
492419TAMREFK개의 묶음 (IZhO14_blocks)C++17
100 / 100
228 ms4084 KiB
#include <bits/stdc++.h> #define va first #define vb second #define lb lower_bound #define ub upper_bound #define bs binary_search #define pp push_back #define ep emplace_back #define all(v) (v).begin(),(v).end() #define szz(v) ((int)(v).size()) #define bi_pc __builtin_popcount #define bi_pcll __builtin_popcountll #define bi_tz __builtin_ctz #define bi_tzll __builtin_ctzll #define fio ios_base::sync_with_stdio(0);cin.tie(0); #ifdef TAMREF #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif using namespace std; template<typename ...Args> void logger(string vars, Args&&... values) { cerr << vars << " = "; string delim = ""; (..., (cerr << delim << values, delim = ", ")); cerr << '\n'; } #ifdef TAMREF #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) #else #define deb(...) 42 #endif using ll = long long; using lf = long double; using pii = pair<int,int>; using ppi = pair<int,pii>; using pll = pair<ll,ll>; using pff = pair<lf,lf>; using ti = tuple<int,int,int>; using base = complex<double>; const lf PI = 3.14159265358979323846264338L; template <typename T> inline T umax(T& u, T v){return u = max(u, v);} template <typename T> inline T umin(T& u, T v){return u = min(u, v);} mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mx = 1e5 + 5; int n, k; int a[mx]; vector<int> dp, tp; int main(){ fio; cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; tp = vector<int>(n + 1, 2000000); tp[0] = 0; for(int j = 1; j <= k; j++) { dp = vector<int>(n + 1); vector<ti> stk; vector<pii> dtk; for(int i = j-1; i >= 1; i--) tp[i-1] = min(tp[i-1], tp[j]); for(int i = j; i <= n; i++) { int tpm = tp[i-1]; while(szz(stk) && get<0>(stk.back()) <= a[i]) { tpm = min(tpm, get<1>(stk.back())); stk.pop_back(); } while(szz(dtk) && a[dtk.back().vb] < a[i]) dtk.pop_back(); if(dtk.empty() || tpm + a[i] < dtk.back().va + a[dtk.back().vb]) dtk.ep(tpm, i); dp[i] = dtk.back().va + a[dtk.back().vb]; stk.ep(a[i], tpm, i); } deb(j); for(int i : dp) debug("%d ", i); debug("\n"); tp = dp; } cout << dp[n] << '\n'; }

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

blocks.cpp: In function 'int main()':
blocks.cpp:32:18: warning: statement has no effect [-Wunused-value]
   32 | #define deb(...) 42
      |                  ^~
blocks.cpp:74:9: note: in expansion of macro 'deb'
   74 |         deb(j);
      |         ^~~
blocks.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
blocks.cpp:75:25: note: in expansion of macro 'debug'
   75 |         for(int i : dp) debug("%d ", i); debug("\n");
      |                         ^~~~~
blocks.cpp:75:17: warning: unused variable 'i' [-Wunused-variable]
   75 |         for(int i : dp) debug("%d ", i); debug("\n");
      |                 ^
blocks.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
blocks.cpp:75:42: note: in expansion of macro 'debug'
   75 |         for(int i : dp) debug("%d ", i); debug("\n");
      |                                          ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...