QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#649157 | #8860. Pirate Chest | garlic_MWT | WA | 1ms | 3684kb | C++17 | 2.2kb | 2024-10-17 21:53:49 | 2024-10-17 21:53:49 |
Judging History
answer
#include <bits/stdc++.h>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (auto i = (a); i < (b); i++)
#define each(x, a) for (auto& x: a)
#define debug if constexpr (xdebug) cout << "[DEBUG] "
#ifndef ONLINE_JUDGE
constexpr bool xdebug = true;
#else
constexpr bool xdebug = false;
#endif
int table[500][500];
void update_ans(int width, int N, int A, int B, int row, ll container_area, ll& ans) {
stack<int> temp_stk;
rep(i, 0, N) {
while(!temp_stk.empty()) {
int temp_idx = temp_stk.top(), temp_ht = table[row][temp_idx];
if(temp_ht <= table[row][i]) break;
temp_stk.pop();
int length = i - 1 - (temp_stk.empty() ? -1 : temp_stk.top());
if(width > B || length > B || (width > A && length > A)) continue;
ll area = width * length;
ans = max(ans, (container_area * temp_ht - 1) / (container_area - area) * area);
}
if(temp_stk.empty() || table[row][temp_stk.top()] < table[row][i]) temp_stk.push(i);
}
while(!temp_stk.empty()) {
int temp_idx = temp_stk.top(), temp_ht = table[row][temp_idx];
temp_stk.pop();
int length = N - 1 - (temp_stk.empty() ? -1 : temp_stk.top());
if(width > B || length > B || (width > A && length > A)) continue;
ll area = width * length;
ans = max(ans, (container_area * temp_ht - 1) / (container_area - area) * area);
}
}
void solve(int testcase){
int A, B, M, N;
cin >> A >> B >> M >> N;
if(A > B) swap(A, B);
rep(i, 0, M) rep(j, 0, N) cin >> table[i][j];
ll ans = 0, container_area = M * N;
rep(i, 0, M) {
rep(j, 0, M - i) update_ans(i + 1, N, A, B, j, container_area, ans);
rep(j, 0, M - i - 1) rep(k, 0, N) table[j][k] = min(table[j][k], table[j+1][k]);
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
clock_t st = clock();
int t = 1;
// cin >> t;
rep(tc, 0, t) solve(tc);
clock_t ed = clock();
if(xdebug) {cout << '\n'; debug << ed - st << "ms\n";}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
input:
3 1 2 3 2 1 1 2 2 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 1 1 5 2 0 2 2 2
output:
12
result:
ok single line: '12'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
2 3 3 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
output:
0
result:
wrong answer 1st lines differ - expected: '18', found: '0'