Cod sursa(job #2866448)

Utilizator Maniu_DianaManiu Maria Diana Maniu_Diana Data 9 martie 2022 18:33:40
Problema Stramosi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scara3.in");
ofstream fout("scara3.out");

const int nmax = 1205;

int n, k, l;
int apa[nmax], eng[nmax], dp[nmax][2];

void read()
{
    int x, y;
    fin >> n;
    fin >> k;
    while(k--)
    {
        fin >> x >> y;
        apa[x] = y;
    }

    fin >> l;
    while(l--)
    {
        fin >> x >> y;
        eng[x] = y;
    }
}


void calc(int poz, int t, int eng)
{
    if(dp[poz][0] > t)
    {
        dp[poz][0] = t;
        dp[poz][1] = eng;
    }
    else if(dp[poz][0] == t && dp[poz][1] > eng)
        dp[poz][1] = eng;
}


void solve()
{
    for(int i = 2;i <= n; i ++)
        dp[i][0] = 1e9;
    dp[1][0] = 1;
    for(int i = 1; i < n; i ++)
    {
        calc(i + 1, dp[i][0] + 1, dp[i][1]);
        if(apa[i] > 0)
        {
            for(int j = 1; i + j <= n && j <= apa[i]; j ++)
                calc(i + j, dp[i][0] + 1, dp[i][1]);
        }
        if(eng[i] > 0)
        {
            for(int j = 1; i + j <= n && j <= 2 * eng[i]; j ++)
                calc(i + j, dp[i][0] + 1, dp[i][1] + (j + 1)/2);
        }
    }
    fout << dp[n][0] << " " << dp[n][1] << '\n';
}

int main()
{
    read();
    solve();
    return 0;
}