oj.uz

Submission #821103

# Submission time Handle Problem Language Result Execution time Memory
821103 2023-08-11T07:29:37 Z alexander707070 Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 4 ms 6356 KB 
#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

const long long inf=1e17;

int n,m;
long long a[MAXN],b[MAXN],cnta,cntb;
long long dp[MAXN][MAXN],dp2[MAXN][MAXN];

long long fra[MAXN],frb[MAXN],lasta[MAXN],lastb[MAXN];
long long inda[MAXN],indb[MAXN];

bool cmp(int x,int y){
    return fra[x]<fra[y];
}

bool cmp2(int x,int y){
    return frb[x]<frb[y];
}

bool cmp3(int x,int y){
    return lasta[x]<lasta[y];
}

bool cmp4(int x,int y){
    return lastb[x]<lastb[y];
}

long long calc(long long x,long long y){
    return (lasta[x]-fra[x])*y + (lastb[y]-frb[y])*x;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=1;i<=1000;i++){
        fra[i]=frb[i]=lasta[i]=lastb[i]=100000000;
    }

    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(fra[a[i]]==100000000){
            fra[a[i]]=i; cnta++;
        }
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        if(frb[b[i]]==100000000){
            frb[b[i]]=i; cntb++;
        }
    }

    for(int i=n;i>=1;i--){
        if(lasta[a[i]]==100000000)lasta[a[i]]=i;
    }
    for(int i=m;i>=1;i--){
        if(lastb[b[i]]==100000000)lastb[b[i]]=i;
    }

    for(int i=1;i<=1000;i++){
        inda[i]=indb[i]=i;
    }

    sort(inda+1,inda+1000+1,cmp);
    sort(indb+1,indb+1000+1,cmp2);

    for(int i=1;i<=cnta;i++){
        for(int f=1;f<=cntb;f++){
            if(i==f and i==1){
                dp[inda[i]][indb[f]]=0;
                continue;
            }

            dp[inda[i]][indb[f]]=inf;

            if(i>1)dp[inda[i]][indb[f]]=min( dp[inda[i]][indb[f]],dp[inda[i-1]][indb[f]]+indb[f]*(fra[inda[i]]-fra[inda[i-1]]) );
            if(f>1)dp[inda[i]][indb[f]]=min( dp[inda[i]][indb[f]],dp[inda[i]][indb[f-1]]+inda[i]*(frb[indb[f]]-frb[indb[f-1]]) );
        }
    }

    sort(inda+1,inda+1000+1,cmp3);
    sort(indb+1,indb+1000+1,cmp4);

    for(int i=1;i<=cnta;i++){
        for(int f=1;f<=cntb;f++){
            dp2[inda[i]][indb[f]]=dp[inda[i]][indb[f]]+calc(inda[i],indb[f]);

            if(i>1)dp2[inda[i]][indb[f]]=min( dp2[inda[i]][indb[f]],dp2[inda[i-1]][indb[f]]+indb[f]*(lasta[inda[i]]-lasta[inda[i-1]]) );
            if(f>1)dp2[inda[i]][indb[f]]=min( dp2[inda[i]][indb[f]],dp2[inda[i]][indb[f-1]]+inda[i]*(lastb[indb[f]]-lastb[indb[f-1]]) );
        }
    }
    
    cout<<dp2[a[n]][b[m]]<<"\n";


    return 0;   
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 4 ms 6356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -