結果

問題 No.974 最後の日までに
コンテスト
ユーザー vectorcc
提出日時 2020-01-18 23:32:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,138 bytes
コンパイル時間 1,034 ms
コンパイル使用メモリ 100,048 KB
実行使用メモリ 16,952 KB
最終ジャッジ日時 2024-06-28 12:35:06
合計ジャッジ時間 7,564 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<map>
#include<sstream>

using namespace std;

class State{
	int money_;
	bool will_date_;
	int love_;
	int small_love_;
	int week_;
	public:
		//State()::State(0,0,0,false,0){}
		State(int money__=0,int love__=0,int small_love__=0,bool will_date__=false,\
		int week__=1){
			this->money_=money__;
			this->will_date_=will_date__;
			this->love_=love__;
			this->small_love_=small_love__;
			this->week_=week__;
		}
		State(const State &dst){
			this->money_=dst.money();
			this->love_=dst.love();
			this->small_love_=dst.small_love();
			this->will_date_=dst.will_date();
			this->week_=dst.week();
		}
		bool will_date()const{return this->will_date_;}
		int money()const{return this->money_;}
		int love() const{return this->love_;}
		int small_love() const{return this->small_love_;}
		int week()const{return this->week_;}
		std::string tostring(){
			std::ostringstream osm;
			osm<<"money:"<<this->money_<<std::endl;
			osm<<"love:"<<this->love_<<std::endl;
			osm<<"small_love:"<<this->small_love_<<std::endl;
			osm<<"week:"<<this->week_<<std::endl;
			osm<<"will date:"<<(this->will_date_?"True":"False")<<std::endl;
			return osm.str();

		}
};


int solve(const std::vector<std::vector<int>> &data,\
		std::map<int,std::function<State(const State&,\
		int,int,int,int)>> &moves,int W){
	using namespace std;
	vector<State> frontier;
	int result=~0xffff;
	State now,next;
	int n;
	frontier.push_back(State());
	while(!frontier.empty()){
		now=frontier.back();
		n=now.week();
		frontier.pop_back();
//cout<<"__now__"<<endl<<now.tostring();
		if(now.week()==W+1){
			if(now.money()>=0){
				result=std::max(result,now.love()*100+now.small_love());
			//else pass
			}
		}
		else
			for(int i=0;i<moves.size();++i){
				auto move=moves[i];
				next=move(now,data[n-1][0],data[n-1][1],data[n-1][2],W);
				frontier.push_back(next);
//cout<<"__next__"<<endl<<next.tostring();
			}
	}
	return result;
}


int main(){
	using namespace std;
		map<int,function<State(const State&,int,int,int,int)>> m;
		m[0]=([](const State &s,int a,int b,int c,int W){
			if(s.will_date())
				return State(s.money(),s.love()-100,s.small_love(),false,s.week()+1);
			if(s.week()==W){
				return State(s.money(),s.love(),s.small_love(),false,s.week()+1);
			}
			return State(s.money(),s.love(),s.small_love(),true,s.week()+1);
		});
		m[1]=[](const State &s,int a,int b,int c,int W){
			if(s.will_date())
				return State(s.money()+a,s.love()-100,s.small_love(),false,s.week()+1);
			return State(s.money()+a,s.love(),s.small_love(),false,s.week()+1);
		};
		m[2]=[](const State &s,int a,int b,int c,int W){
			if(s.will_date())
				return State(s.money()-c,s.love(),s.small_love()+b,false,s.week()+1);
			return State(s.money(),s.love(),s.small_love(),false,s.week()+1);
		};
	
	int W;
	cin>>W;
	vector<vector<int>> data;
	vector<int> tmp;
	int x;
	for(int i=0;i<W;++i){
		tmp.clear();
		for(int j=0;j<3;++j){
			cin>>x;
			tmp.push_back(x);
		}
		data.push_back(tmp);
	}
//cout<<"solve:"<<solve(data,m,W)<<endl;
	cout<<solve(data,m,W)<<endl;
}
0