Submission #240542

#	Time	Username	Problem	Language	Result	Execution time	Memory
240542		DavidDamian	Cipele (COCI18_cipele)	C++11	9 / 90	1099 ms	199296 KiB

cipele

#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
• Subtask 2: 0 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9