Cod sursa(job #989804)

Utilizator classiusCobuz Andrei classius Data 26 august 2013 15:30:16
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("trans.in");
ofstream g("trans.out");

int main()
{
    int n,m;
    int v[16001],s[2][16001]={};
    bool ok[16001];

    f>>n;

    for(int i=1;i<=n;i++){
        f>>ok[i]>>v[i];
        s[ok[i]][i]+=s[ok[i]][i-1]+v[i];
        s[!ok[i]][i]=s[!ok[i]][i-1];
    }
    f>>m;

    for(int t=1;t<=m;t++){
        int ki,ci;
        int rz[16001]={};
        f>>ki>>ci;
        for(int i=1;i<=n;i++){
            rz[i]=rz[i-1]+ci;
            for(int k=1;k<ki&&i-k>0;k++)
                rz[i]=min(rz[i],ci+min(s[0][i]-s[0][i-k-1],s[1][i]-s[1][i-k-1])+rz[i-k-1]);
        }
        g<<rz[n]<<'\n';
    }



    return 0;
}