Cod sursa(job #181538)

Utilizator varuvasiTofan Vasile varuvasi Data 18 aprilie 2008 15:05:41
Problema Tribute Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
 #include <stdio.h>  
 #include <string.h>  
 #define maxn 60001  
 #define FOR(i, a, b) for (i = (a); i <= (b); i++)  
 #define FORD(i, a, b) for (i = (a); i >= (b); i--)  
 int N, DX, DY, maxC;  
 int count[maxn], s[maxn], revs[maxn], sumL[maxn], sumR[maxn];  
 int X[maxn], Y[maxn];  
   
 FILE *fin = fopen("tribute.in", "rt"), *fout = fopen("tribute.out", "wt");  
 int go(int pos[maxn], int D)  
 {  
     int min_val = 100000001, i;  
     memset(count, 0, sizeof(count));  
     memset(s, 0, sizeof(s));  
     memset(revs, 0, sizeof(revs));  
     memset(sumL, 0, sizeof(sumL));  
     memset(sumR, 0, sizeof(sumR));  
     FOR(i, 1, N)  
         count[pos[i]]++;  
 /*  FOR(i, 0, maxC) 
         fprintf(fout, "%d ", count[i]);*/  
 //  fprintf(fout, "\n");  
     s[0] = count[0];  
     FOR(i, 1, maxC)  
         s[i] = count[i] + s[i - 1];  
     FORD(i, maxC, 0)  
         revs[i] = count[i] + revs[i + 1];  
       
     FOR(i, 1, maxC)  
     {  
         sumL[i] = sumL[i - 1] + s[i - 1];  
 //      fprintf(fout, "%d ", sumL[i]);  
     }  
 //  fprintf(fout, "\n");  
     FORD(i, maxC, 0)  
     {  
         sumR[i] = sumR[i + 1] + revs[i + 1];  
 //      fprintf(fout, "%d ", sumR[i]);  
     }  
 //  fprintf(fout, "\n");  
   
     FOR(i, 0, maxC - D)  
         if (sumL[i] + sumR[i + D] < min_val)  
             min_val = sumL[i] + sumR[i + D];  
   
     return min_val;       
 }  
   
 int main()  
 {  
     int i;  
   
     fscanf(fin, "%d %d %d", &N, &DX, &DY);  
     FOR(i, 1, N)  
     {  
         fscanf(fin, "%d %d", &X[i], &Y[i]);  
         if (maxC < X[i]) maxC = X[i];  
         if (maxC < Y[i]) maxC = Y[i];  
     }  
     fprintf(fout, "%d", go(X, DX) + go(Y, DY));  
     fclose(fin), fclose(fout);  
 }