Submission #47841015

Source Code Expand

// LUOGU_RID: 136458849
#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 

int n, m; 
int a[5005], _b[205][5005]; 
int _st[205][5005], _tot[5005]; 
i64 c[5005], ans[5005]; 
inline void add(int l, int r, int k) { c[l] += k; c[r + 1] -= k; }

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i < n; ++i) cin >> a[i]; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> _b[j][i]; 
    for (int i = 1; i <= m; ++i) _st[i][_tot[i] = 1] = n + 1, _b[i][n + 1] = 1e9 + 1; 
    i64 tans = 0; 
    for (int i = n; i >= 1; --i) {
        add(i + 1, n, -a[i]); 
        for (int j = 1; j <= m; ++j) {
            int *b = _b[j], *st = _st[j], &tot = _tot[j]; add(i, i, b[i]); 
            while (tot && b[st[tot]] <= b[i]) 
                add(st[tot], st[tot - 1] - 1, b[i] - b[st[tot]]), --tot; 
            st[++tot] = i; 
        }
        i64 res = 0; 
        for (int j = i; j <= n; ++j)
            res += c[j], c[j] = 0, tans = max(tans, ans[j] += res); 
    }
    cout << tans << "\n"; 
    return 0; 
}

Submission Info

Submission Time
Task F - Yakiniku Restaurants
User james1BadCreeper
Language C++ 17 (gcc 12.2)
Score 1000
Code Size 1109 Byte
Status AC
Exec Time 91 ms
Memory 8332 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_dense_max_01.txt, subtask_1_dense_max_02.txt, subtask_1_dense_max_03.txt, subtask_1_dense_max_04.txt, subtask_1_dense_rand_01.txt, subtask_1_dense_rand_02.txt, subtask_1_dense_rand_03.txt, subtask_1_dense_rand_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_max_03.txt, subtask_1_max_04.txt, subtask_1_min_01.txt, subtask_1_min_02.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt, subtask_1_widemax_01.txt, subtask_1_widemax_02.txt, subtask_1_widemax_03.txt, subtask_1_widemax_04.txt, subtask_1_widemax_05.txt, subtask_1_widemax_06.txt, subtask_1_widemax_07.txt, subtask_1_widemax_08.txt, subtask_1_widemax_09.txt, subtask_1_widemax_10.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 3484 KiB
sample_02.txt AC 1 ms 3456 KiB
subtask_1_dense_max_01.txt AC 90 ms 8276 KiB
subtask_1_dense_max_02.txt AC 89 ms 8252 KiB
subtask_1_dense_max_03.txt AC 90 ms 8248 KiB
subtask_1_dense_max_04.txt AC 89 ms 8332 KiB
subtask_1_dense_rand_01.txt AC 56 ms 7468 KiB
subtask_1_dense_rand_02.txt AC 62 ms 7820 KiB
subtask_1_dense_rand_03.txt AC 3 ms 3828 KiB
subtask_1_dense_rand_04.txt AC 13 ms 4628 KiB
subtask_1_max_01.txt AC 89 ms 8312 KiB
subtask_1_max_02.txt AC 90 ms 8272 KiB
subtask_1_max_03.txt AC 90 ms 8184 KiB
subtask_1_max_04.txt AC 89 ms 8188 KiB
subtask_1_min_01.txt AC 1 ms 3580 KiB
subtask_1_min_02.txt AC 1 ms 3508 KiB
subtask_1_rand_01.txt AC 16 ms 5596 KiB
subtask_1_rand_02.txt AC 8 ms 4104 KiB
subtask_1_rand_03.txt AC 15 ms 5060 KiB
subtask_1_rand_04.txt AC 21 ms 4400 KiB
subtask_1_widemax_01.txt AC 91 ms 8332 KiB
subtask_1_widemax_02.txt AC 90 ms 8304 KiB
subtask_1_widemax_03.txt AC 90 ms 8332 KiB
subtask_1_widemax_04.txt AC 90 ms 8264 KiB
subtask_1_widemax_05.txt AC 90 ms 8240 KiB
subtask_1_widemax_06.txt AC 91 ms 8248 KiB
subtask_1_widemax_07.txt AC 91 ms 8260 KiB
subtask_1_widemax_08.txt AC 89 ms 8260 KiB
subtask_1_widemax_09.txt AC 90 ms 8332 KiB
subtask_1_widemax_10.txt AC 90 ms 8204 KiB