Pagini recente » Cod sursa (job #3151631) | Cod sursa (job #3039949) | Cod sursa (job #2176471) | Clasament oni2015day1 | Cod sursa (job #2866448)
#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;
}