Submission #464666

#TimeUsernameProblemLanguageResultExecution timeMemory
464666sobaCipele (COCI18_cipele)C++14
63 / 90
425 ms201660 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5000+5; int n ,m , x; int dp[N][N]; vector<int>v1 , v2; int solve(int i , int rem) { if(rem==0) return 0; if(i==n) return 1e9; int &ret=dp[i][rem]; if(ret!=-1) return ret; ret=min( max(solve(i+1, rem-1), abs(v1[i]-v2[m-rem]) ) , solve(i+1 , rem) ); return ret; } int main() { cin>>n>>m; for(int i = 0 ; i < n; i++) { cin>>x; if(n>=m) v1.push_back(x); else v2.push_back(x); } for(int i=0 ; i < m ;i++ ) { cin >> x; if(n>=m) { v2.push_back(x); } else v1.push_back(x); } if(n<m)swap(n,m); int ans=0; sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end()); if(n==m) { for(int i = 0; i< n ;i++) { ans=max(ans , abs(v1[i]-v2[i])); } cout << ans; return 0; } memset(dp , -1 , sizeof dp); cout << solve(0 , m); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...