제출 #524556

#제출 시각아이디문제언어결과실행 시간메모리
524556ezdp호화 벙커 (IZhO13_burrow)C++14
100 / 100
923 ms17868 KiB
#pragma GCC target ("sse4") #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define endl '\n' #define pb push_back #define fr first #define sc second #define ll long long int #define ld long double #define lsb(idx) idx&(-idx) #define bin(x) bitset<32>(x).to_string() #define all(A) A.begin(), A.end() #define de(x) cout << #x << " = " << x << endl; using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> using matrix = vector<vector<T>>; /// find_by_order(x) -> x-th element in the set /// order_of_key(x) -> how many elements are less than x /// insert(x) -> inserts x into the set const int MAXN = 1e3 + 3; int n, m, k, A[MAXN][MAXN], dp[MAXN][MAXN], L[MAXN], R[MAXN]; int eval(int x){ for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++){ dp[i][j] = (A[i][j] >= x ? 1 : 0); } for(int i = 1; i < n; i ++) for(int j = 0; j < m; j ++){ if(dp[i][j]) dp[i][j] = dp[i - 1][j] + 1; } int ret = 0; for(int i = 0; i < n; i ++){ stack<int> st; for(int j = 0; j < m; j ++){ while(!st.empty() && dp[i][st.top()] >= dp[i][j]){ st.pop(); } L[j] = (st.empty() ? 0 : st.top() + 1); st.push(j); } while(!st.empty()) st.pop(); for(int j = m - 1; j >= 0; j --){ while(!st.empty() && dp[i][st.top()] >= dp[i][j]){ st.pop(); } R[j] = (st.empty() ? m - 1 : st.top() - 1); st.push(j); } for(int j = 0; j < m; j ++){ ret = max(ret, dp[i][j] * (R[j] - L[j] + 1)); } } return ret; } int main(){ /// ios_base::sync_with_stdio(false); cin.tie(NULL); /// freopen("filename.in" , "r", stdin); /// freopen("filename.out", "w", stdout); cin >> n >> m >> k; for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++){ cin >> A[i][j]; } int l = 0, r = 1e9; while(l < r - 1){ int m = (l + r) / 2; if(eval(m) >= k) l = m; else r = m; } cout << l << " " << eval(l) << endl; } /** 3 3 3 1 1 1 1 2 2 1 2 2 2 4 1 10 5 4 3 2 5 10 7 6 5 1 100 5 5 3 5 2 5 7 5 5 5 8 5 5 7 5 8 5 8 8 8 8 3 */

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

burrow.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
burrow.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...