#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define num(a) a-'0'
#define charr(a) (a - 'A' + 1)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#define bin1(a) __builtin_popcount(a)
#define debug(x) cerr<<"["<<#x<<":"<<x<<"] "
#define debug2(a,b) debug(a);debug(b)
#define debug3(a,b,c) debug2(a,b);debug(c)
#define de cerr
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
typedef double d;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;
ll inf = 2e9 + 1;
/*OUTPUT
*/
void solve(){
int n,m;
cin >> n >> m;
v<vi> a(2,vi(max(n,m)));
for(int i = 0;i < n;i ++){
cin >> a[0][i];
}
for(int i = 0;i < m;i ++){
cin >> a[1][i];
}
sort(a[0].begin(),a[0].begin() + n);
sort(a[1].begin(),a[1].begin() + m);
int c = 0;
int d = 1;
if(m < n){
swap(c,d);
swap(n,m);
}
v<vi> dp(n,vi(m));
v<vi> pre(m,vi(2));
int crr = 0;
int prev = 1;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
if(i == 0){
dp[i][j] = abs(a[c][i] - a[d][j]);
}
else{
dp[i][j] = abs(a[c][i] - a[d][j]);
if(j != 0){
maxs(dp[i][j],pre[j - 1][prev]);
}
else{
dp[i][j] = inf;
}
//
// dp[i][j] = max(a[i] - b[j], min(dp[i - 1][j - 1],dp[i - 1][j - 2]....));
//
}
pre[j][crr] = dp[i][j];
if(j != 0){
mins(pre[j][crr],pre[j - 1][crr]);
}
// debug(dp[i][j]);
}
// de << ln;
crr = 1 - crr;
prev = 1 - prev;
}
int ans;
for(int j = 0;j < m;j ++){
if(j == 0){
ans = dp[n - 1][j];
}
else{
mins(ans,dp[n - 1][j]);
}
}
cout << ans << ln;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
Compilation message
cipele.cpp: In function 'void solve()':
cipele.cpp:28:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | #define ln "\n"
| ^~~~
cipele.cpp:90:6: note: 'ans' was declared here
90 | int ans;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
235 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
249 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
25088 KB |
Output is correct |
| 2 |
Correct |
155 ms |
98560 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
2560 KB |
Output is correct |
| 2 |
Correct |
159 ms |
98808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
112 ms |
69240 KB |
Output is correct |
| 2 |
Correct |
155 ms |
98680 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
113 ms |
69240 KB |
Output is correct |
| 2 |
Correct |
154 ms |
98680 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
138 ms |
88824 KB |
Output is correct |
| 2 |
Correct |
158 ms |
98808 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
239 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
248 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
239 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
