#include<bits/stdc++.h>
using namespace std;
int n,m,a[2005][2005],b[2005][2005],st,md,ed,ans1,ans2,num,dp[2005][2005];
int cnt;
vector<int> v;
vector<pair<int,int> > p;
void rotate()
{
for(int i=1;i<=m;i++)
{
for(int j=n;j>=1;j--)
{
b[i][n-j+1]=a[j][i];
}
}
swap(n,m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=b[i][j];
}
}
}
int find_ans()
{
st=0;
ed=p.size()-1;
while(ed>=st)
{
md=(st+ed)/2;
if(md==p.size()-1)
{
num=0;
}else
{
num=p[md+1].second;
}
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j+1<=m)
{
dp[i][j]=max(dp[i][j],dp[i-1][j]+(abs(a[i][j]-a[i][j+1])>p[md].first));
}else
{
dp[i][j]=max(dp[i][j],dp[i-1][j]);
}
if(i+1<=n)
{
dp[i][j]=max(dp[i][j],dp[i][j-1]+(abs(a[i][j]-a[i+1][j])>p[md].first));
}else
{
dp[i][j]=max(dp[i][j],dp[i][j-1]);
}
}
}
if(dp[n][m]==num)
{
ed=md-1;
}else
{
st=md+1;
}
}
//printf("%d %d %d\n",st,md,ed);
return p[st].first;
}
int main()
{
scanf("%d%d",&n,&m);
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++)
{
for(int j=1;j<=m;j++)
{
v.push_back(abs(a[i][j]-a[i+1][j]));
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
v.push_back(abs(a[i][j]-a[i][j+1]));
}
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
if(i==0)
{
cnt=1;
continue;
}
if(v[i]==v[i-1])
{
++cnt;
}else
{
p.push_back({v[i-1],cnt});
cnt=1;
}
}
p.push_back({v[v.size()-1],cnt});
for(int i=p.size()-2;i>=0;i--)
{
p[i].second=p[i].second+p[i+1].second;
}
ans1=find_ans();
rotate();
ans2=find_ans();
printf("%d\n",min(ans1,ans2));
}
Compilation message
joioi.cpp: In function 'int find_ans()':
joioi.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | if(md==p.size()-1)
| ~~^~~~~~~~~~~~
joioi.cpp: In function 'int main()':
joioi.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
joioi.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
joioi.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d",&a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
16084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
16084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
16084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
