Submission #54500

#TimeUsernameProblemLanguageResultExecution timeMemory
54500bogdan10bosThe Kingdom of JOIOI (JOI17_joioi)C++14
100 / 100
1166 ms81468 KiB
#include <bits/stdc++.h> using namespace std; //#define FILE_IO int N, M, ans, cost; int mn, mx; int pfxmn[2005], sfxmx[2005]; int aux[2005][2005]; int a[2005][2005]; int dp[2005][2005]; void solve() { for(int i = 1; i <= N; i++) { pfxmn[0] = 1 << 30; for(int j = 1; j <= M; j++) pfxmn[j] = min(pfxmn[j - 1], a[i][j]); sfxmx[M + 1] = -1; for(int j = M; j >= 1; j--) sfxmx[j] = max(sfxmx[j + 1], a[i][j]); for(int j = M; j >= 0; j--) { cost = max(mx - pfxmn[j], sfxmx[j + 1] - mn); dp[i][j] = max(dp[i - 1][j], cost); if(j < M) dp[i][j] = min(dp[i][j], dp[i][j + 1]); } } ans = min(ans, dp[N][0]); } void rotate90() { for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) { aux[i][j] = a[i][j]; a[i][j] = 0; } for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) a[j][N - i + 1] = aux[i][j]; swap(N, M); } int main() { #ifdef FILE_IO freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); #endif scanf("%d%d", &N, &M); mn = 1 << 30, mx = -1; for(int i = 1; i <= N; i++) for(int j = 1; j <= M; j++) { scanf("%d", &a[i][j]); mn = min(mn, a[i][j]); mx = max(mx, a[i][j]); } ans = mx - mn; solve(); rotate90(); solve(); rotate90(); solve(); rotate90(); solve(); printf("%d\n", ans); return 0; }

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...