Submission #254596

#TimeUsernameProblemLanguageResultExecution timeMemory
254596baboThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
1188 ms197368 KiB
#include <bits/stdc++.h> #define L long long using namespace std; L n,m; L totma=0,totmi=1000000000ll; L a[2020][2020]; L c[2020][2020]; L nucolmax[2020][2020]; L xamlocun[2020][2020]; L nucolmin[2020][2020]; L nimlocun[2020][2020]; L colma[2020],colmi[2020]; void clear(){ L i; for(i=1;i<=m;i++) colma[i]=0,colmi[i]=1000000000ll; } void clear2(){ L i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) c[i][j]=0; } bool ok(L dis){ L i,j; clear(); for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]>totmi+dis) { colma[j]=max(colma[j],i); colmi[j]=min(colmi[j],i); } L now; L mamin,mimax; mamin=1000000000ll,mimax=0; now=n+1; for(j=m;j>=1;j--) { now=min(now,colmi[j]); mamin=min(mamin,nimlocun[now][j]); mimax=max(mimax,nucolmax[now-1][j]); } if(totma-mamin<=dis&&mimax-totmi<=dis) return 1; mamin=1000000000ll,mimax=0; now=n+1; for(j=1;j<=m;j++) { now=min(now,colmi[j]); mamin=min(mamin,nimlocun[now][j]); mimax=max(mimax,nucolmax[now-1][j]); } if(totma-mamin<=dis&&mimax-totmi<=dis) return 1; mamin=1000000000ll,mimax=0; now=0; for(j=1;j<=m;j++) { now=max(now,colma[j]); mamin=min(mamin,nucolmin[now][j]); mimax=max(mimax,xamlocun[now+1][j]); } if(totma-mamin<=dis&&mimax-totmi<=dis) return 1; mamin=1000000000ll,mimax=0; now=0; for(j=m;j>=1;j--) { now=max(now,colma[j]); mamin=min(mamin,nucolmin[now][j]); mimax=max(mimax,xamlocun[now+1][j]); } if(totma-mamin<=dis&&mimax-totmi<=dis) return 1; return 0; } int main() { scanf("%lld %lld",&n,&m); L i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { scanf("%lld",&a[i][j]); totma=max(totma,a[i][j]); totmi=min(totmi,a[i][j]); } } for(i=1;i<=n;i++) for(j=1;j<=m;j++) nucolmax[i][j]=max(nucolmax[i-1][j],a[i][j]); for(i=n;i>=1;i--) for(j=1;j<=m;j++) xamlocun[i][j]=max(xamlocun[i+1][j],a[i][j]); for(j=1;j<=m;j++) nucolmin[0][j]=nimlocun[n+1][j]=1000000000ll; for(i=1;i<=n;i++) for(j=1;j<=m;j++) nucolmin[i][j]=min(nucolmin[i-1][j],a[i][j]); for(i=n;i>=1;i--) for(j=1;j<=m;j++) nimlocun[i][j]=min(nimlocun[i+1][j],a[i][j]); /*for(i=1;i<=n;i++,puts("")) for(j=1;j<=m;j++) printf("%lld ",nucolmax[i][j]); puts("nucolmax"); for(i=1;i<=n;i++,puts("")) for(j=1;j<=m;j++) printf("%lld ",nucolmin[i][j]); puts("nucolmin"); for(i=1;i<=n;i++,puts("")) for(j=1;j<=m;j++) printf("%lld ",xamlocun[i][j]); puts("xamlocun"); for(i=1;i<=n;i++,puts("")) for(j=1;j<=m;j++) printf("%lld ",nimlocun[i][j]); puts("nimlocun"); for(i=1;i<=n;i++,puts("")) for(j=1;j<=m;j++) printf("%lld ",nimlocun[i][j]); puts("nimlocun");*/ L s=0,e=1000000000ll; while(s<e) { L mid=(s+e)/2; if(ok(mid)) e=mid; else s=mid+1; } printf("%lld",s); }

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:98:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=n;i>=1;i--)
  ^~~
joioi.cpp:102:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(j=1;j<=m;j++)
   ^~~
joioi.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
joioi.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...