ARC073 C問題+D問題

C - Sentou

ボタンを押すとT秒間お湯が出て、
出ている最中にボタンを押されるとまたT秒お湯が出続ける。

お湯が何秒出続けるかについて

1. ボタン押してから次のボタンを押すまでにお湯が流れきる場合
2.ボタンを押してから次のボタンを押すまでにお湯がながれきらない場合

1についてはT秒を数える
2については押した人から次に押す人までに時間をカウントする。

1,2をひたすら行えばOK

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
#define DEBUG 1
#define lli long long int
 
using namespace std;
 
int main(){
 
	int n;
	lli T;
	lli *t;
	cin>>n;
	cin>>T;
 
	t = new lli[n];
	for(int i=0;i<n;i++){
		cin>>t[i];
	}
	lli ans =0;
 
	for(int i=0;i<n;i++){
		if(i!=n-1 && t[i+1]-t[i]<=T){
			ans+=(t[i+1]-t[i]);
		}else{
			ans+=T;
		}
	}
	cout<<ans<<endl;
 
 
 
	return 0;
}





D問題 Simple Knapsack

DPで解く
dp[i] i:重さ, dp[i]:価値で行いたいが、
強度wが10^9なため、配列だと厳しい。
そのため、mapを使って実装を行う。
後余計かもしれなが、dp[i]のiの一覧が欲しかったため、
setを用いた。setは降順になるように利用
(dpの更新時に、前に更新したものの影響を次に受けないようにするため)

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
 
#define DEBUG 0
#define lli long long int
 
lli max(lli a,lli b){
	return a>=b ? a:b;
}
 
using namespace std;
 
int main(){
 
	//dp[i] i:重さ, dp:最大価値
	map<lli , lli> dp;
 
	//mapのkeyになるもの
	set<lli, greater<lli> > key;
	dp[0]=0;
	key.insert(0);
 
	lli N,W;
	lli *w,*v;
	cin>>N>>W;
 
	w = new lli[N];
	v = new lli[N];
 
	for(int i=0;i<N;i++){
		cin>>w[i]>>v[i];
	}
 
	for(int i=0;i<N;i++){
		if(DEBUG)cout<<"i="<<i<<endl;
		vector<lli> tmpKey;
		for(auto it = key.begin(); it!= key.end(); it++){
			if(DEBUG)cout<<"key="<<*it<<endl;
			dp[ *it + w[i]] = max(dp[*it]+v[i],dp[ *it + w[i]] );
			if( dp[*it] + v[i] >= dp[*it + w[i]]){
				if(DEBUG)cout<<"nextPushKey="<< *it +w[i] <<endl;
				tmpKey.push_back( *it+w[i] );
			}
		}
		for(int j=0;j<tmpKey.size();j++){
			key.insert(tmpKey.at(j));
		}
	}
 
	lli ans=0;
	for(auto it = key.begin(); it!= key.end(); it++){
		if(DEBUG)cout<<"w="<<*it<<" v="<<dp[*it]<<endl;
		if(*it > W){
			continue;
		}
		ans = max(ans, dp[*it]);
	}
	cout<<ans<<endl;
	return 0;
}