Submission #3695232

---

Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_map>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
class mywatch{
public:
	std::clock_t mybegin;
	void start(void){mybegin=std::clock();}
	double when(void){return static_cast<double>(std::clock()-mybegin)/((double)CLOCKS_PER_SEC);}
};
//1ケース1京は草
class quest{
public:
	int Sturn,Eturn,Kik;
	llint Base;
	array<int,10> neLv;
};
array<quest,30001> guild;//ギルド?
array<bool,30001>yatta={};
llint getmon(quest terget,array<int,10>taLv,int Nturn){
	if(Nturn<terget.Sturn||terget.Eturn<Nturn){return 0;}
	if(terget.Base==-1){return 1000;}
	double ans=terget.Base*(1+9*(double)(Nturn-terget.Sturn)/(terget.Eturn-terget.Sturn));
	int LvLack=0;
	for(int j=0;j<10;j++){LvLack+=max(0,terget.neLv[j]-taLv[j]);}
	if(LvLack==0){ans*=10;}
	else{ans*=pow(0.5,LvLack);ans+=1e-9;}
	return ans;
}
vector<int>Ego[1111];
/*
上位20個だけでDPする
経路をつなぎ合わせて、行けるかどうか確認する
dpの枝刈り基準 合計が25+110%ターンよりでかければ諦める
630ターンには目標を達しているはずなので考えない、あくまで645までの最大
何もしなくてもとれる場合、枝を増やさない
ピッタリ配分が同じなら自明にsetでまとめられる
枝が多すぎたら所持金だけで見て枝刈りする、ただし既存のと配分が近ければペナルティ?(未実装)

*/
class state{
public:
	llint score;
	int maezyo;
	int dregil;
	array<int,10>Lv;//降ったexp
	bool active;//これは葉ですか? 葉い。
	state(void){active=1;score=0;maezyo=0;for(int i=0;i<10;i++){Lv[i]=0;}}
	state(llint is,int im,array<int,10>iL){active=1;score=is,maezyo=im,Lv=iL;}
};
int main(int args,char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int yoyu=30;
	int T,N,M,i,j,k;cin>>T>>N>>M;
	array<int,10> SkLv={0};
	array<int,10> Skexp={0};
	llint money=1000;
	vector<pair<llint,int>>nerai;
	nerai.reserve(1000);
	for(i=0;i<M;i++){
		cin>>guild[i].Sturn>>guild[i].Eturn>>guild[i].Base;
		for(j=0;j<10;j++){cin>>guild[i].neLv[j];}
		guild[i].Kik=guild[i].Eturn-guild[i].Sturn;
		Ego[guild[i].Eturn].pub(i);
		if(guild[i].Base<3e6||guild[i].Eturn>=645){continue;}
		int maxLv=0;
		for(j=0;j<10;j++){maxeq(maxLv,(guild[i].neLv[j]-1)/2);}
		int neeps=0;
		for(j=0;j<10;j++){
			maxeq(guild[i].neLv[j],maxLv);
			neeps+=(guild[i].neLv[j]+1)*guild[i].neLv[j]/2;
		}
		if(yoyu+neeps*13/12<=guild[i].Eturn){nerai.pub(mp(guild[i].Base,i));}
	}
	SO(nerai);REV(nerai);
	int miru=31;
	vector<pair<int,int>>kouga(miru);//高額依頼
	for(i=0;i<miru;i++){
		int ban=nerai[i].sec;
		kouga[i]=mp(guild[ban].Eturn,ban);
	}
	SO(kouga);
	//実質ビームサーチ?
	deque<state> dp(1);
	map<array<int,10>,pair<llint,int>>highest;
	//最高得点はどこのだれ? 全く同じのは一つしか活性化されない
	
	dp[0].maezyo=-1;dp[0].dregil=0;
	int keisan=0;
	for(i=0;i<miru;i++){
		
		int ban=kouga[i].sec;
		llint pot=guild[ban].Base;
		int X=dp.size();
		auto itLv=guild[ban].neLv;
		for(j=0;j<X;j++){
			if(!dp[j].active){continue;}
			keisan++;
			//ここからとる
			auto newLv=dp[j].Lv;
			bool kawa=0;
			for(k=0;k<10;k++){kawa|=maxeq(newLv[k],itLv[k]);}
			int neeps=0;
			for(k=0;k<10;k++){neeps+=(newLv[k]+1)*newLv[k]/2;}
			if(yoyu+neeps*13/12>guild[ban].Eturn){continue;}
			if(!kawa){dp[j].active=0;}
			llint newpot=pot+dp[j].score;
			if(highest.count(newLv)==0){
				highest[newLv]=mp(newpot,(int)dp.size());
				dp.pub(state(newpot,j,newLv));
				dp.back().dregil=ban;
			}else if(highest[newLv]<mp(newpot,(int)dp.size())){
				dp[highest[newLv].sec].active=0;
				highest[newLv]=mp(newpot,dp.size());
				dp.pub(state(newpot,j,newLv));
				dp.back().dregil=ban;
			}
			//else 何もしない
		}
	}
	cerr<<"keisan="<<keisan<<endl;
	//この中の最大値に対して、計画を立てる
	pair<llint,int> Keiban=mp(0LL,0);
	for(i=0;i<dp.size();i++){maxeq(Keiban,mp(dp[i].score,i));}
	int gensta=Keiban.sec;
	vector<array<int,10>>checkpot;
	vector<int>checktime;
	array<int,10>Last;
	for(j=0;j<10;j++){Last[j]=10;}
	Last[0]=11;checkpot.pub(Last);checktime.pub(1e7);
	Last[0]=10;checkpot.pub(Last);checktime.pub(645);
	cerr<<"tooru"<<endl;
	
	bool toota[30001]={0};
	while(gensta!=-1){
		//cerr<<"gesnsta="<<gensta<<endl;
		checkpot.pub(dp[gensta].Lv);
		int terban=dp[gensta].dregil;
		int neeps=0;
		for(k=0;k<10;k++){neeps+=dp[gensta].Lv[k]*(dp[gensta].Lv[k]+1)/2;}
		checktime.pub(yoyu+neeps*13/12);
		toota[terban]=1;
		gensta=dp[gensta].maezyo;
	}
	for(i=0;i<miru;i++){
		int ban=kouga[i].sec;
		llint pot=guild[ban].Base;
		int X=dp.size();
		auto itLv=guild[ban].neLv;
		cerr<<(int)(pot/1e6)<<"億チャンス"<<guild[ban].Sturn<<" "<<guild[ban].Eturn<<"\t";
		for(j=0;j<10;j++){cerr<<itLv[j]<<" ";if(itLv[j]!=10){cerr<<" ";}}
		if(toota[ban]){cerr<<"通過!";}
		cerr<<endl;
	}
	REV(checktime);
	REV(checkpot);
	guild[30000].Sturn=-1;
	guild[30000].Eturn=1e6;
	guild[30000].Base=-1;
	guild[30000].Kik=1e6+1;
	int Lvyusen[10]={100,81,72,65,60,56,53,50,48,46};
	int stoptrain=900;
	double souba=0;
	//n億もらえたかのグラフを作る
	int DEgra[9]={10,20,50,100,200,500,1000,2000,5000};
	int DEGwer[10]={0};
	int kita=0;
	int Cnum=0;
	int abura=0;
	for(int Ntu=1;Ntu<=1000;Ntu++){
		int terSk=0;//次に目指すもの
		int terten=0;
		while(-1){
			bool mitasita=1;
			for(j=0;j<10;j++){if(SkLv[j]<checkpot[Cnum][j]){mitasita=0;break;}}
			if(mitasita){
				cerr<<"予定="<<checktime[Cnum]<<"現在="<<Ntu<<" 早い="<<checktime[Cnum]-Ntu<<endl;
				abura=checktime[Cnum]-Ntu;
				Cnum++;
			}
			else{break;}
			
		}
		for(j=0;j<10;j++){
			if(SkLv[j]>=10){continue;}
			int hosei=201;
			if(SkLv[j]>=checkpot[Cnum][j]){hosei=100;}
			if(Skexp[j]>0){terSk=j;terten=1e8;}
			if(maxeq(terten,10000*hosei/(SkLv[j]+1))){terSk=j;}
		}
		//どれをやるか、20ターン先読みして決める
		//どうしても今やりたい依頼があればやる
		llint TrainLine=1.4*souba+0.3*money;
		if(abura>12){mineq(TrainLine,1e9);}
		else if(abura>6){mineq(TrainLine,2.5e9);}
		else{mineq(TrainLine,5e9);}
		//dousitemoを超えなければトレーニングをする
		if(money<=(1LL<<SkLv[terSk])*20000){TrainLine=0;}
		if(terten==0){TrainLine=0;}
		vector<tuple<llint,llint,int,int>>kasegu;//稼ぐ金額、期間,日時、番号
		for(int Ftu=Ntu;Ftu<Ntu+50;Ftu++){
			for(auto it:Ego[Ftu]){
				llint pri=getmon(guild[it],SkLv,Ftu);
				if(!yatta[it]){kasegu.pub(mt(pri,guild[it].Kik,Ftu-Ntu,it));}
			}
		}
		//kasegu.pub(mt(1000LL,1000000LL,Ntu,30000));
		SO(kasegu);REV(kasegu);
		//金額/期間が小さければ前倒しする、
		//ただしそれがこっちまで押し出される前倒しであれば、金額/9が優先
		//開始制限に引っかかる場合は金額/期間が金額/9に代わる
		array<int,51>yotei;
		for(j=0;j<=50;j++){yotei[j]=-1;}
		int choku=-1;//予定が詰まっている、まるでchokudai
		bool dotrain=false;
		for(int j=0;j<kasegu.size();j++){
			int gen=j,Ftu=get<2>(kasegu[j]);
			if(get<0>(kasegu[j])<TrainLine&&yotei[0]==-1){
				cout<<"1 "<<terSk+1<<endl;
				money-=(1LL<<SkLv[terSk])*20000;
				Skexp[terSk]++;
				if(SkLv[terSk]<Skexp[terSk]){SkLv[terSk]++;Skexp[terSk]=0;}
				dotrain=1;break;
			}
			if(get<0>(kasegu[j])<1000&&yotei[0]==-1){
				cout<<"3"<<endl;
				money+=1000;
				dotrain=1;break;
			}
			while(Ftu>=0){
				llint Gp,Gm,gomia,gomib;
				tie(Gp,Gm,gomia,gomib)=kasegu[gen];
				if(yotei[Ftu]==-1){yotei[Ftu]=gen;break;}
				if(Ftu<=choku){break;}
				llint Gcos=Gp/Gm;
				if(Ftu+Ntu==guild[gomib].Sturn){Gcos=Gp/9;}
				llint Ep,Em;
				tie(Ep,Em,gomia,gomib)=kasegu[yotei[Ftu]];
				llint Ecos=Ep/Em;
				if(Ftu+Ntu==guild[gomib].Sturn){Ecos=Ep/9;}
				if(Ecos<Gcos){swap(yotei[Ftu],gen);}
				Ftu--;
			}
			while(choku+1<50&&yotei[choku+1]!=-1){choku++;}
		}
		if(dotrain){continue;}
		int yaru=get<3>(kasegu[yotei[0]]);
		//バイトの存在により、たぶん-1にならない
		if(yaru==-1){yaru=30000;}
		if(yaru<30000&&Ntu<guild[yaru].Sturn){yaru=30000;}
		if(yaru<30000){
			abura--;
			cout<<"2 "<<yaru+1<<endl;
			llint itget=getmon(guild[yaru],SkLv,Ntu);
			j=0;
			while(j<9&&DEgra[j]*1e8<itget){j++;}
			DEGwer[j]++;
			if(itget>=3e10){//300億円以上
				//cerr<<(int)(itget/1e8)<<"億円"<<guild[yaru].Sturn<<" "<<guild[yaru].Eturn<<endl;
				//for(j=0;j<10;j++){cerr<<guild[yaru].neLv[j]<<" ";}cerr<<endl;
			}
			money+=itget;
			souba*=0.9;souba+=itget/10;
			yatta[yaru]=1;
		}else{abura--;cout<<"3"<<endl;money+=1000;}
	}
	cerr<<"pot="<<money/100000000<<"億"<<endl;
	cerr<<"内訳="<<endl;
	cerr<<"～10o\t"<<DEGwer[0]<<endl;
	for(j=0;j<9;j++){
		cerr<<DEgra[j]<<"o～\t"<<DEGwer[j+1]<<endl;
	}
	return 0;
}
/*
progcomdp.exe < testCase_0.txt > myout_00.txt
progcomdp.exe < testCase_1.txt > myout_01.txt
progcomdp.exe < testCase_2.txt > myout_02.txt
progcomdp.exe < testCase_3.txt > myout_03.txt
progcomdp.exe < testCase_4.txt > myout_04.txt




24157
*/

Submission Info

Judge Result