QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649157#8860. Pirate Chestgarlic_MWTWA 1ms3684kbC++172.2kb2024-10-17 21:53:492024-10-17 21:53:49

Judging History

This is the latest submission verdict.

  • [2024-10-17 21:53:49]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3684kb
  • [2024-10-17 21:53:49]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'