ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212681 | #3828. B | Jacken | 100 | 2693ms | 21540kb | C++11 | 1.8kb | 2024-10-20 09:29:56 | 2024-10-20 14:36:04 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n;
int a[N];
int f[N];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int m;
int dfs(int x,int y)
{
if(f[(x-1)*m+y])
{
return f[(x-1)*m+y];
}
int ans = 0;
for(int i = 0;i<4;i++)
{
int r = dx[i]+x,c = dy[i]+y;
if(r<=n&&c<=m&&r>=1&&c>=1&&a[(x-1)*m+y]<a[(r-1)*m+c])
{
ans = max(dfs(r,c)+1,ans);
}
}
return f[(x-1)*m+y] = ans;
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
scanf("%d",&a[(i-1)*m+j]);
}
}
int maxx = 0;
int maxxx = 0;
memset(f,0,sizeof(f));
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=m;j++)
{
int t = dfs(i,j);
if(maxx<t||maxx == t&&a[(i-1)*m+j]<a[maxxx])
{
maxx = t;
maxxx = (i-1)*m+j;
}
}
}
printf("%d\n",maxx+1);
set<int>cd;
cd.insert(a[maxxx]);
int x = maxxx%m == 0?maxxx/m:maxxx/m+1,y = maxxx%m == 0?m:maxxx%m;\
while(f[(x-1)*m+y])
{
int minn = 1e9;
int minnr = 0;
int minnc = 0;
for(int i = 0;i<4;i++)
{
int r = x+dx[i],c = y+dy[i];
if(r<1||r>n||c<1||c>m)
{
continue;
}
if(f[(r-1)*m+c] == f[(x-1)*m+y]-1&&a[(x-1)*m+y]<a[(r-1)*m+c])
{
if(minn>a[(r-1)*m+c])
{
minn = a[(r-1)*m+c];
minnr = r;
minnc = c;
}
}
}
x = minnr;
y = minnc;
cd.insert(minn);
}
for(auto it = cd.begin();it!=cd.end();it++)
{
printf("%d ",*it);
}
printf("\n");
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 2020kb
input:
10 3 3 0 1 2 3 4 5 6 7 8 3 3 0 1 2 3 4 5 6 8 7 3 3 0 1 2 3 4 5 7 6 8 3 3 0 1 2 3 4 5 7 8 6 3 3 0 1 2...
output:
5 0 1 2 5 8 6 0 1 2 5 7 8 5 0 1 2 5 8 6 0 1 2 5 6 8 5 0 1 2 5 7 7 0 1 2 5 6 7 8 5 0 1 2 6 8 6...
result:
ok 64 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 2016kb
input:
10 1 10 1 5 0 8 2 9 6 3 4 7 1 10 2 5 8 0 9 7 3 1 6 4 3 3 0 1 2 5 4 3 6 7 8 1 10 3 4 7 2 5 6 9 0 1 8 ...
output:
3 3 4 7 4 1 3 7 9 9 0 1 2 3 4 5 6 7 8 4 2 5 6 9 3 1 7 9 4 4 5 6 7 3 0 4 7 10 0 1 2 3 4 5 6 7 ...
result:
ok 63 numbers
Subtask #2:
score: 20
Accepted
Test #3:
score: 20
Accepted
time: 3ms
memory: 2112kb
input:
10 22 45 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33...
output:
990 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 3...
result:
ok 5011 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 2108kb
input:
10 17 58 655 668 708 805 640 926 52 16 9 662 765 129 949 348 678 235 18 464 819 450 211 968 724 754 ...
output:
10 11 42 106 223 265 421 903 923 971 982 10 227 258 271 479 499 509 574 578 580 918 8 1 230 308 44...
result:
ok 2052 numbers
Subtask #3:
score: 10
Accepted
Test #5:
score: 10
Accepted
time: 447ms
memory: 21540kb
input:
10 2 100000 143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...
output:
13 11306 16007 49522 70570 76999 90088 97453 105217 116458 118241 145649 165150 168193 9 9688 35806...
result:
ok 600082 numbers
Subtask #4:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 377ms
memory: 21536kb
input:
10 1 200000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...
output:
200000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3...
result:
ok 400095 numbers
Subtask #5:
score: 40
Accepted
Test #7:
score: 40
Accepted
time: 519ms
memory: 21536kb
input:
10 145 1379 140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...
output:
14 8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 14 701...
result:
ok 799431 numbers
Test #8:
score: 0
Accepted
time: 448ms
memory: 21528kb
input:
10 137 1459 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...
output:
199883 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3...
result:
ok 599839 numbers
Test #9:
score: 0
Accepted
time: 437ms
memory: 21540kb
input:
10 431 464 73283 114291 153291 121544 122062 142417 169824 87437 63383 123169 5578 161240 12296 2810...
output:
13 8693 46170 58031 84535 85037 98585 107097 109913 125647 135974 173048 173291 193164 16 5468 1850...
result:
ok 400038 numbers
Test #10:
score: 0
Accepted
time: 462ms
memory: 21536kb
input:
10 287 696 42594 17204 186134 183377 153412 122746 42424 4738 107615 187084 183594 161385 57847 9481...
output:
14 136 58739 82533 100919 115173 123428 128558 129415 134074 151802 155712 174974 184151 184213 14 ...
result:
ok 599743 numbers
Extra Test:
score: 0
Extra Test Passed