QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#649126#8860. Pirate Chestgarlic_MWTWA 511ms4664kbC++172.2kb2024-10-17 21:44:502024-10-17 21:44:52

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 21:44:52]
  • 评测
  • 测评结果:WA
  • 用时:511ms
  • 内存:4664kb
  • [2024-10-17 21:44:50]
  • 提交

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'