#include #include #include using namespace std; const int MAX_C = 999999; const int MAX_N = 100000; int N; int S[2][MAX_N]; bool acc[2][MAX_N]; void stampaMatrice(); int calcolaCosto(int a, int b); int main() { ifstream fin("input.txt"); assert( fin ); fin >> N; for(int i = 0; i < N; i++){ fin >> S[0][i]; acc[0][i] = false; } for(int i = 0; i < N; i++){ fin >> S[1][i]; acc[1][i] = false; } /* Sostituire best */ int costo = 0, best = MAX_C; int cella[2]; int dx = MAX_C,sx = MAX_C,up = MAX_C,down = MAX_C; /* Scorro tutta la stringa */ for(int i = 0; i < N; i++){ for(int j = 0; j < 2; j++){ /* Controllo che la cella non sia gia accoppiata */ if(acc[j][i] == false){ /* Ricavo i valori adiacenti alla cella */ if((i-1 >= 0) && (acc[j][i-1] == false)) sx = S[j][i-1]; else sx = MAX_C; if((i+1 < N) && (acc[j][i+1] == false)) dx = S[j][i+1]; else dx = MAX_C; if((j-1 >= 0) && (acc[j-1][i] == false)) up = S[j-1][i]; else up = MAX_C; if((j+1 < 2) && (acc[j+1][i] == false)) down = S[j+1][i]; else down = MAX_C; /* Cerco il valore migliore tra gli adiacenti, controllo anche che una cella adiacente non * sia gia stata utilizzata */ if((sx != MAX_C) && calcolaCosto(S[j][i],sx) < best){ best = calcolaCosto(S[j][i],sx); cella[0] = j; cella[1] = i-1;} if((dx != MAX_C) && calcolaCosto(S[j][i],dx) < best){ best = calcolaCosto(S[j][i],dx); cella[0] = j; cella[1] = i+1;} if((up != MAX_C) && calcolaCosto(S[j][i],up) < best){ best = calcolaCosto(S[j][i],up); cella[0] = j-1; cella[1] = i;} if((down != MAX_C) && calcolaCosto(S[j][i],down) < best){ best = calcolaCosto(S[j][i],down); cella[0] = j+1; cella[1] = i;} /* Ho calcolato quale cella mi conviene prendere, adesso calcolo il costo */ costo += best; /* Dico che le celle che ho accoppiato non sono piu disponibili per un ulteriore accoppiamento */ assert(cella[0] >= 0); assert(cella[1] >= 0); acc[j][i] = true; acc[cella[0]][cella[1]] = true; } /* Resetto i parametri di questa iterazione */ dx = MAX_C; sx = MAX_C; up = MAX_C; down = MAX_C; cella[0] = -1; cella[1] = -1; best = MAX_C; } } ofstream fout("output.txt"); assert( fout ); fout << costo << endl; fout.close(); return 0; } int calcolaCosto(int a, int b){ if ((a - b) >= 0) return (a-b); else return -(a-b); } void stampaMatrice(){ cerr << endl; for(int i = 0; i < N; i++){ cerr << S[0][i] << "\t"; } cerr << endl; for(int i = 0; i < N; i++){ cerr << S[1][i] << "\t"; } cerr << endl; }