Cod sursa(job #115981)

Utilizator floringh06Florin Ghesu floringh06 Data 17 decembrie 2007 15:38:36
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>

using namespace std;

#define FIN "litere.in"
#define FOUT "litere.out"
#define MAX_N 10005
#define Sig 30

int A[Sig][MAX_N]; // preprocesare
int N;
char S[MAX_N];

     void preproc ( void )
     {
          int i, j;
          for (i = 1; i <= 26; ++i)
          {
              int ct = 0;
              for (j = N - 1; j >= 0; --j)
              {
                  if (S[j] == i + 96) ct++;
                  A[i][j] = ct;
              }
          }
     }        

     void solve ( void )
     {
          int i, j;
          int Best = 0;
          for (i = 0; i < N; ++i)
          {
              int p = S[i] - 96;
              for (j = p - 1; j; --j)
                  Best += A[j][i + 1];
          }
          printf ("%d", (int) Best);
     }

     int main ()
     {
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
         
         scanf ("%d\n", &N);
         gets (S);
     
         preproc ();
         solve ();
         
         return 0;
     }