Submission #379645

#TimeUsernameProblemLanguageResultExecution timeMemory
379645penguinhackerHyper-minimum (IZhO11_hyper)C++14
100 / 100
473 ms57984 KiB
// source: https://oj.uz/problem/view/IZhO11_hyper #include <bits/stdc++.h> using namespace std; #define ll long long #define ar array const int mxN = 35; int n, m, a[mxN][mxN][mxN][mxN], dp[mxN][mxN][mxN][mxN], dp2[mxN][mxN][mxN][mxN], dp3[mxN][mxN][mxN][mxN], dp4[mxN][mxN][mxN][mxN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) for (int l = 0; l < n; ++l) cin >> a[i][j][k][l]; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int k = 0; k < n; ++k) { deque<int> dq; for (int l = 0; l < n; ++l) { while(!dq.empty() && a[i][j][k][l] <= a[i][j][k][dq.back()]) dq.pop_back(); if (!dq.empty() && l >= m && dq[0] == l - m) dq.pop_front(); dq.push_back(l); dp[i][j][k][l] = a[i][j][k][dq[0]]; } } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) for (int l = m - 1; l < n; ++l) { deque<int> dq; for (int k = 0; k < n; ++k) { while(!dq.empty() && dp[i][j][k][l] <= dp[i][j][dq.back()][l]) dq.pop_back(); if (!dq.empty() && k >= m && dq[0] == k - m) dq.pop_front(); dq.push_back(k); dp2[i][j][k][l] = dp[i][j][dq[0]][l]; } } for (int i = 0; i < n; ++i) for (int k = m - 1; k < n; ++k) for (int l = m - 1; l < n; ++l) { deque<int> dq; for (int j = 0; j < n; ++j) { while(!dq.empty() && dp2[i][j][k][l] <= dp2[i][dq.back()][k][l]) dq.pop_back(); if (!dq.empty() && j >= m && dq[0] == j - m) dq.pop_front(); dq.push_back(j); dp3[i][j][k][l] = dp2[i][dq[0]][k][l]; } } for (int j = m - 1; j < n; ++j) for (int k = m - 1; k < n; ++k) for (int l = m - 1; l < n; ++l) { deque<int> dq; for (int i = 0; i < n; ++i) { while(!dq.empty() && dp3[i][j][k][l] <= dp3[dq.back()][j][k][l]) dq.pop_back(); if (!dq.empty() && i >= m && dq[0] == i - m) dq.pop_front(); dq.push_back(i); dp4[i][j][k][l] = dp3[dq[0]][j][k][l]; } } for (int i = m - 1; i < n; ++i) for (int j = m - 1; j < n; ++j) for (int k = m - 1; k < n; ++k) for (int l = m - 1; l < n; ++l) cout << dp4[i][j][k][l] << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...