oj.uz

Submission #240542

# Submission time Handle Problem Language Result Execution time Memory
240542 2020-06-19T21:46:21 Z DavidDamian Cipele (COCI18_cipele) C++11
9 / 90
 1000 ms 199296 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> A;
vector<int> B;
int memo[5005][5005];
int ugliness(int i,int j)
{
    if(m-j+1<n-i+1)
        return INT_MAX;
    if(i==n){
        if(memo[i][j]==-1){
            int minimum=INT_MAX;
            for(int k=j;k<=m;k++){
                minimum=min(minimum,abs(B[k]-A[i]));
            }
            memo[i][j]=minimum;
        }
        return memo[i][j];
    }
    if(memo[i][j]==-1){
        memo[i][j]=INT_MAX;
        int match_i=abs(A[i]-B[j]);
        for(int k=j+1;k<=m;k++){
            int ugly_value=ugliness(i+1,k);
            if(ugly_value==INT_MAX) break;
            memo[i][j]=min(memo[i][j],max(ugly_value,match_i));
            match_i=min(match_i,abs(A[i]-B[k]));
        }
    }
    return memo[i][j];
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            memo[i][j]=-1;
        }
    }
    A.push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        A.push_back(x);
    }
    B.push_back(0);
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        B.push_back(x);
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    if(n==m){
        int maximum=0;
        for(int i=1;i<=n;i++){
            maximum=max(maximum,abs(A[i]-B[i]));
        }
        cout<<maximum<<'\n';
        return 0;
    }
    cout<<ugliness(1,1)<<'\n';
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 368 ms 199032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 199160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35200 KB Output is correct
2 Correct 61 ms 98808 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 2304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 69368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 69368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 89080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 199288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 365 ms 199296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 335 ms 199032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -