Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
2
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

ifstream fin("axel.in");
ofstream fout("axel.out");

long long int n, v[1505][1505], cost[1505][8005], minnr=2e9, ans, raspuns;
bool ok=true;

void solve(){
    fin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            fin>>v[i][j];
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(cost[j][v[i][j]] == 0) cost[j][v[i][j]] = 2e9;
            if(i>=j){
                cost[j][v[i][j]]=min(cost[j][v[i][j]], i-j*1LL+1);
            }
            else if(i<j){
                cost[j][v[i][j]]=min(cost[j][v[i][j]], i+(n-j)*1LL+1);
            }
        }
    }

    for(int i=0; i<=8000; i++){
        ok=true;
        ans=0;
        for(int j=1; j<=n; j++){

            if(cost[j][i]==0){
                ok=false; break;
            }
            ans+=cost[j][i]-1;
        }
        if(ok){
            minnr=min(minnr, ans*1LL);
            raspuns = max(raspuns, i - ans);
        }

    }
    if(minnr==2e9){
        fout<<"NU";
    }
    else{
        fout<<"DA\n"<<raspuns;
    }
}

int main(){
    solve();
    return 0;
}