QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#649126 | #8860. Pirate Chest | garlic_MWT | WA | 511ms | 4664kb | C++17 | 2.2kb | 2024-10-17 21:44:50 | 2024-10-17 21:44:52 |
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() || 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
3 1 2 3 2 1 1 2 2 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 1 1 5 2 0 2 2 2
output:
12
result:
ok single line: '12'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 3 3 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
output:
18
result:
ok single line: '18'
Test #4:
score: -100
Wrong Answer
time: 511ms
memory: 4664kb
input:
499 499 500 500 649850711 869750238 627745405 930778599 956785748 598310756 998020082 659182553 889106939 905912562 606533068 765367617 509331841 519356700 778167157 675754469 808581870 911021086 521336619 618984603 786647531 902669308 804488018 755969003 609652761 767290830 624502151 628733548 9473...
output:
469905432033310
result:
wrong answer 1st lines differ - expected: '31156455008500822', found: '469905432033310'