NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#211085	#3801. Thief Masters	18112606231	100	26356ms	294296kb	C++11	1.2kb	2024-08-09 10:45:56	2024-08-09 12:44:48

answer

#include <bits/stdc++.h>
using namespace std;
int n, m, k, a[5001][5001], q[5001], h = 1, t, ans = INT_MAX, r[5001][5001], l[5001][5001], maxn[5001], minn[5001], maxx[5001], minx[5001];
void work(int a[], int ans[], int n, bool flag)
{
    h = 1, t = 0;
    for (int i = 1; i <= n; i++)
    {
        if (h <= t && q[h] <= i - k)
            h++;
        if(flag)
        {
            while (h <= t && a[i]<=a[q[t]])
                t--;
        }
        else
        {
            while (h <= t && a[i]>=a[q[t]])
                t--;
		}
        q[++t] = i;
        if (i >= k)
            ans[i - k + 1] = a[q[h]];
    }
}
signed main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
    {
        work(a[i], r[i], m , 0);
        work(a[i], l[i], m , 1);
    }
    for (int j = 1; j <= m - k + 1; j++)
    {
        for (int i = 1; i <= n; i++)
            maxn[i] = r[i][j], minn[i] = l[i][j];
        work(maxn, maxx, n, 0);
        work(minn, minx, n, 1);
        for (int i = 1; i <= n - k + 1; i++)
            ans = min(ans, maxx[i] - minx[i]);
    }
    printf("%d", ans);
    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 4464ms

memory: 294292kb

input:

5000 5000 1000
112860841 963292630 950228017 843100821 628111020 568250408 901169419 322571542 98853...

output:

999988492

result:

ok single line: '999988492'

Test #2:

score: 10

Accepted

time: 1ms

memory: 1272kb

input:

output:

result:

ok single line: '2'

Test #3:

score: 10

Accepted

time: 2ms

memory: 2508kb

input:

100 100 10
2 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 1200001 ...

output:

result:

ok single line: '908999'

Test #4:

score: 10

Accepted

time: 3973ms

memory: 294292kb

input:

5000 5000 1000
8974 8293 3530 8179 6181 2983 6500 3525 2603 1983 6720 5938 9247 2494 4568 9909 3852 ...

output:

result:

ok single line: '9999'

Test #5:

score: 20

Accepted

time: 3950ms

memory: 294292kb

input:

5000 5000 1000
3206 5640 1070 5846 5931 3274 6116 1741 543 6399 1626 115 92 3037 464 100 3700 2694 5...

output:

result:

ok single line: '9999'

Test #6:

score: 10

Accepted

time: 4283ms

memory: 294296kb

input:

5000 5000 1000
9041 1397 3723 7115 4298 5210 8033 5608 6711 6539 7140 5331 4282 2599 59 9363 5817 25...

output:

result:

ok single line: '9999'

Test #7:

score: 10

Accepted

time: 5209ms

memory: 294296kb

input:

5000 5000 1000
19636 14616 3910 15971 9484 16390 2221 13667 5771 1364 2375 15202 16870 7107 13189 16...

output:

result:

ok single line: '21813'

Test #8:

score: 20

Accepted

time: 4474ms

memory: 294296kb

input:

5000 5000 1000
3628 1018 3668 18160 14975 18599 9087 10641 19468 16400 19072 16984 6583 7925 19853 1...

output:

result:

ok single line: '21811'

Extra Test:

score: 0

Extra Test Passed