NOI.AC

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#213797	#2406. Thief Masters	N	100	677ms	13068kb	C++	2.1kb	2024-11-13 19:50:38	2024-11-13 23:03:49

answer

//
//  na 2406.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/13.
//

#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn = 1005;
int a, b, n, m[maxn][maxn], que[maxn], qs, qe, minm[maxn][maxn], maxm[maxn][maxn];
int fin[maxn], fout[maxn], rseq[maxn];
inline void fold(int len, bool op){ // 0: max, 1: min
    qs = 0; qe = -1;
    for(int i = 1; i <= len; ++i){
        while(qs <= qe && (fin[que[qe]] == fin[i] || ((fin[que[qe]] < fin[i]) ^ op)))
            --qe;
        while(qs <= qe && que[qs] <= i - n)
            ++qs;
        que[++qe] = i;
        if(i >= n)
            fout[i - n + 1] = fin[que[qs]];
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> a >> b >> n;
    for(int i = 1; i <= a; ++i)
        for(int j = 1; j <= b; ++j)
            cin >> m[i][j];
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j)
            fin[j] = m[i][j];
        fold(b, false);
        for(int j = 1; j <= b - n + 1; ++j)
            maxm[i][j] = fout[j];
        fold(b, true);
        for(int j = 1; j <= b - n + 1; ++j)
            minm[i][j] = fout[j];
    }
//    cerr << "max mat" << endl;
//    for(int i = 1; i <= a; ++i){
//        for(int j = 1; j <= b - n + 1; ++j)
//            cerr << maxm[i][j] << ' ';
//        cerr << endl;
//    }
//    cerr << "min mat" << endl;
//    for(int i = 1; i <= a; ++i){
//        for(int j = 1; j <= b - n + 1; ++j)
//            cerr << minm[i][j] << ' ';
//        cerr << endl;
//    }
    int ans = 0x7fffffff;
    for(int i = 1; i <= b - n + 1; ++i){
        for(int j = 1; j <= a; ++j)
            fin[j] = maxm[j][i];
        fold(a, false);
        for(int j = 1; j <= a - n + 1; ++j)
            rseq[j] = fout[j];
        for(int j = 1; j <= a; ++j)
            fin[j] = minm[j][i];
        fold(a, true);
        for(int j = 1; j <= a - n + 1; ++j)
            ans = min(ans, rseq[j] - fout[j]);
    }
    cout << ans << endl;
    return 0;
}
/*
 5 4 2
 1 2 5 6
 0 17 16 0
 16 17 2 1
 2 10 2 1
 1 2 2 2
 
 
 
 4 4 2
 0 0 0 0
 10 0 10 0
 0 0 0 0
 0 10 0 2
 */

Source code, Language: C++

Details

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

Test #1:

score: 10

Accepted

time: 133ms

memory: 13068kb

input:

1000 1000 100
804544523 340648618 718292412 235345736 704741136 942776831 741228920 463473302 677289...

output:

998893495

result:

ok single line: '998893495'

Test #2:

score: 10

Accepted

time: 0ms

memory: 1324kb

input:

output:

result:

ok single line: '2'

Test #3:

score: 10

Accepted

time: 2ms

memory: 2452kb

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: 106ms

memory: 13068kb

input:

1000 1000 20
1 100001 200001 300001 400001 500001 600001 700001 800001 900001 1000001 1100001 120000...

output:

result:

ok single line: '1901899'

Test #5:

score: 10

Accepted

time: 31ms

memory: 7172kb

input:

500 500 50
79289095 232165705 955620938 481434262 465576217 112035388 50089892 459799006 181906335 3...

output:

995944328

result:

ok single line: '995944328'

Test #6:

score: 10

Accepted

time: 69ms

memory: 7180kb

input:

500 1000 80
499163842 331022295 940054497 684192083 248823911 842132608 629298697 398526298 98438040...

output:

998299092

result:

ok single line: '998299092'

Test #7:

score: 10

Accepted

time: 98ms

memory: 13064kb

input:

1000 1000 80
102 134 429 251 299 109 264 669 727 296 112 550 270 270 544 660 131 546 968 219 113 678...

output:

result:

ok single line: '998'

Test #8:

score: 10

Accepted

time: 35ms

memory: 7168kb

input:

500 500 100
65532583 920409544 753795976 989349545 818384831 778207112 425141881 853270293 542112588...

output:

999172505

result:

ok single line: '999172505'

Test #9:

score: 10

Accepted

time: 72ms

memory: 7180kb

input:

500 1000 100
456896744 779471086 578349238 52507342 192194992 156396237 475084995 775765435 96617474...

output:

998801667

result:

ok single line: '998801667'

Test #10:

score: 10

Accepted

time: 131ms

memory: 13064kb

input:

1000 1000 100
629053044 957239666 456746076 940194386 201529807 592062148 244394389 825620014 223976...

output:

998862873

result:

ok single line: '998862873'

Extra Test:

score: 0

Extra Test Passed