Thonk2

Dorijanko

Nov 29th, 2018

217

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

text 2.52 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
int l,n,m[1001],a;
int pr1[1001][1001];
int h[1001][1001],mi[1001][1001],s[1001][1001];
int ti[51][30001];
int pr2[1001][1001];
int dp[51][30001];
vector<int> ho[51][30001];
bool bio[51][30001];
int mat[1001];
int wh[1001];
int re[1001];
int mgc;
const int MAXGEMS=20000;
const int HAR=0;
int dp1(int i,int j)
{
if (j<0) return MAXGEMS;
if (i<0) return 0;
if (bio[i][j]) return dp[i][j];
bio[i][j]=1;
int mi=-1;
for (int k=0;k<m[i];++k)
{
if (i==0 && pr1[i][k]<HAR*60) continue;
if (mi==-1 || pr2[i][k]+dp1(i-1,j-pr1[i][k])<pr2[i][mi]+dp1(i-1,j-pr1[i][mi]) ||
((pr2[i][k]+dp1(i-1,j-pr1[i][k])==pr2[i][mi]+dp1(i-1,j-pr1[i][mi])) && (ti[i-1][j-pr1[i][k]]<ti[i-1][j-pr1[i][mi]]))) mi=k;
}
if (j-pr1[i][mi]<0) return dp[i][j]=MAXGEMS;
if (mi==-1) return dp[i][j]=MAXGEMS;
if (i==0)
{
vector<int> o;
o.push_back(mi);
ho[i][j]=o;
ti[i][j]=pr1[i][mi];
}
else
{
vector<int> o=ho[i-1][j-pr1[i][mi]];
o.push_back(mi);
ho[i][j]=o;
ti[i][j]=pr1[i][mi]+ti[i-1][j-pr1[i][mi]];
}
return dp[i][j]=pr2[i][mi]+dp1(i-1,j-pr1[i][mi]);
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin>>l>>a;
cin>>n;
l*=1440;
l+=a*60;
for (int i=0;i<n;++i)
{
cin>>m[i];
for (int j=0;j<m[i];++j)
{
cin>>h[i][j]>>mi[i][j]>>s[i][j]>>pr2[i][j];
mi[i][j]+=s[i][j]/60;
s[i][j]%=60;
h[i][j]+=mi[i][j]/24;
mi[i][j]%=24;
pr1[i][j]=h[i][j]*1440+mi[i][j]*60+s[i][j];
}
}
for (int i=n-1;i>=0;--i)
{
mat[i]=mat[i+1]+pr1[i][m[i]-1];
}
l+=2880;
for (int o=0;o<20 && l>=HAR;++o)
{
for (int i=0;i<n;++i)
{
for (int j=0;j<l;++j)
{
bio[i][j]=0;
dp[i][j]=0;
ho[i][j].clear();
}
}
mgc=dp1(n-1,l);
l-=480;
if (mgc==0) continue;
l+=480;
bool ima=0;
for (int i=0;i<n;++i)
{
//cout<<ho[n-1][l].size()<<endl;
re[i]=ho[n-1][l][i];
if (mi[i][re[i]]%8)
{
cout<<"On quest "<<i+1<<", use "<<pr2[i][re[i]]<<" gems at "<<h[i][re[i]]<<" days and "<<mi[i][re[i]]<<" hours."<<endl;
ima=1;
}
else cout<<"On quest "<<i+1<<", use "<<pr2[i][re[i]]<<" gems after "<<(mi[i][re[i]]/8+h[i][re[i]]*3)<<" collections, not including the first one."<<endl;
}
cout<<"Total gem cost: "<<mgc<<" gems."<<endl;
if (ima) cout<<"Total time: "<<ti[n-1][l]/1440<<" days and "<<(ti[n-1][l]%1440)/60<<" hours.";
else cout<<"Total collections(not including the first one on each node): "<<ti[n-1][l]/480<<".";
cout<<endl<<endl<<endl;
l-=480;
}
}

Add Comment

Please, Sign In to add comment