taokhongcoten19xx
Chú bộ đội
codeforce vẫn là 1 đẳng cấp khác, mất hơn nửa ngày. Bài này dùng sparse table vs sliding window @LQDuy2 @sangnguyen112233 @Kengoc2018
C:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 5;
int dp[N][M][20];
int a[N][M];
int log_2[N];
int n, m, k;
/**
3 2 4
1 2
1 3
2 2
**/
void prepare() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dp[i][j][0] = a[i][j];
}
}
for (int k = 1; (1<<k) <= n; ++k) {
int step = 1<<(k-1);
for (int i = 0; i + 2*step <= n; ++i) {
for (int mi = 0; mi < m; ++mi) {
int i1 = dp[i][mi][k-1];
int i2 = dp[i+step][mi][k-1];
dp[i][mi][k] = max(i1, i2);
}
}
}
log_2[1] = 0;
for (int i = 2; i <= n; i++) {
log_2[i] = log_2[i/2] + 1;
}
}
int query(int l, int r, int mi) {
int k = log_2[r - l + 1];
return max(dp[l][mi][k], dp[r - (1<<k) + 1][mi][k]);
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
prepare();
int l = 0;
int maxLen = INT_MIN;
int result[m];
int saveResult[5] = {0, 0, 0, 0, 0};
for (int r = 0; r < n; ++r) {
while(l <= r) {
int maxCount = 0;
for(int mi = 0; mi < m; ++mi) {
int qResult = query(l, r, mi);
result[mi] = qResult;
maxCount += qResult;
}
if (maxCount > k) {
++l;
} else {
int len = r-l + 1;
if (len > maxLen) {
maxLen = len;
for (int i = 0; i < m; ++i) {
saveResult[i] = result[i];
}
}
break;
}
}
}
for (int i = 0; i < m; ++i) {
cout << saveResult[i] << " ";
}
return 0;
}
, code xong đẩy lên git bảo bọn QC vào test. Logic code khi đi làm cũng ko khó bằng lúc đi học, và gần như ko dùng đến khi đi làm.
)
