Cod sursa(job #67573)

Utilizator raula_sanChis Raoul raula_san Data 25 iunie 2007 11:57:34
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 1.53 kb
#include <cstdio>
#include <set>

#define MAX_N 100001

using namespace std;

int N, S, T;
int C[MAX_N], P[MAX_N], SUM[MAX_N];

long long unsigned CM[MAX_N];

void Read();
void Dynamics();
void Print();

multiset <int> Q;

int main()
{
    Read();
    Dynamics();    
    Print();
    
    return 0;
}

void Read()
{
     FILE *f = fopen("branza.in", "rt");
     int i;
     
     for(fscanf(f, "%d %d %d", &N, &S, &T), i=1; i<=N; ++i)
     {
                   fscanf(f, "%d %d", C+i, P+i);
                   SUM[i] = SUM[i-1] + P[i];
     }
     
     fclose(f);
}

void Dynamics()
{
     int i, j;
     
     long long unsigned c, d;
     
     CM[1] = C[1] * P[1];
     
     for(i=2; i<=N; ++i)
     {
              d = 0;
              Q.insert(C[i]);
              
              if(i > T + 1)
                   Q.erase(C[i-T]);
              
              CM[i] = CM[i-1] + (C[i] * P[i]);

              for(j=i-1; j>=((i-T)>=1?(i-T):1); --j)
              {
                       d += SUM[i] - SUM[j];
                         
                       c = C[j] * (SUM[i] - SUM[j-1]) + d * S;
                       
                       if(CM[i] > c + CM[j-1])
                                CM[i] = c + CM[j-1];
                       
                       if(C[j] == *Q.begin())
                               break;
              }
     }
}

void Print()
{
     FILE *g = fopen("branza.out", "wt");
     
     fprintf(g, "%llu", CM[N]);
     
     fclose(g);
}