Pagini recente » Statistici Medar Andrei (AndreiMedar) | Cod sursa (job #1121618) | Cod sursa (job #2339989) | Istoria paginii utilizator/maia_tomita | Cod sursa (job #2780089)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("summax.in");
ofstream fout("summax.out");
const int LIMIT = 2000000001;
int n, st, dr;
vector <int> v[2001];
vector <int> dp[2001];
void Reconstructie(int i, int l, int c)
{
fout << c << ' ';
if(l < n)
{
if(v[l + 1][c] > v[l + 1][c + 1])
Reconstructie(i, l + 1, c);
else if(v[l + 1][c] < v[l + 1][c + 1])
Reconstructie(i, l + 1, c + 1);
else
{
if(dp[l + 1][c] >= i)
Reconstructie(i, l + 1, c);
else
Reconstructie(i - dp[l + 1][c], l + 1, c + 1);
}
}
}
int main()
{
int task;
fin >> task;
fin >> n >> st >> dr;
int x;
for(int i = 1; i <= n; i++)
{
v[i].push_back(0);
dp[i].push_back(0);
for(int j = 1; j <= i; j++)
{
fin >> x;
v[i].push_back(x);
dp[i].push_back(0);
}
}
for(int j = 1; j <= n; j++)
dp[n][j] = 1;
for(int l = n - 1; l >= 1; l--)
for(int j = 1; j <= l; j++)
{
if(v[l + 1][j] > v[l + 1][j + 1])
{
v[l][j] = v[l][j] + v[l + 1][j];
dp[l][j] = dp[l + 1][j];
}
else if(v[l + 1][j] < v[l + 1][j + 1])
{
v[l][j] = v[l][j] + v[l + 1][j + 1];
dp[l][j] = dp[l + 1][j + 1];
}
else
{
v[l][j] = v[l][j] + v[l + 1][j];
dp[l][j] = min(1LL * dp[l + 1][j] + dp[l + 1][j + 1], 1LL * LIMIT);
}
}
if(task == 1)
{
fout << dp[1][1] << '\n';
return 0;
}
for(int i = st; i <= dr; i++)
{
Reconstructie(i, 1, 1);
fout << '\n';
}
return 0;
}