2013-08-12

■ SRM588 03:28

参加しました。Writerは準急さん。

Easy:

pairでもちtoneでソートして順にとればいい。

一つ目のときにもtoneの差をとるというアホすぎるミスを犯す。

80ptsの損害。

137.26pts

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int dp[55][55]={};
class GUMIAndSongsDiv1
{
public:

int maxSongs(vector <int> duration, vector <int> tone, int T)
{
	P s[55];
	for(int i=0;ifor(int i=0;i<55;i++)for(int j=1;j<55;j++) dp[i][j]=1e8;
	for(int i=0;i0]=0;
		dp[i][1]=s[i].second;
	}
	for(int i=1;ifor(int j=0;jfor(int k=2;k<=i+1;k++)
			{
				dp[i][k]=min(dp[i][k],dp[j][k-1]+s[i].second+abs(s[j].first-s[i].first));
			}
		}
	}
	int ans=0;
	for(int i=0;i<55;i++)
	{
		for(int j=0;j<55;j++)
		{
			if(dp[i][j]<=T)
			{
			
				ans=max(ans,j);
			}
		}
	}
	return ans;
	}
};

Medium:

(行った所,赤、緑)のBFSしか思いつかなかった。

けどdp[行った所][赤]=maxwhiteの解法より10倍遅いだけだったのでセーフだった。

本当に良かった...

214.98pts

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class KeyDungeonDiv1{
public:
int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
{
	queueque;
	que.push(mp(0,mp(keys[0],keys[1])));
	int n=doorR.size();
	int val=0;
	mapint>ma;
	while(!que.empty())
	{
		int a=que.front().first;
		int b=que.front().second.first;
		int c=que.front().second.second;
		P1 p=que.front();
		que.pop();
		if(ma[p]) continue;
		ma[p]++;
		int r=keys[0];
		int g=keys[1];
		int w=keys[2];
		for(int i=0;iif(((a>>i) & 1))
			{
				r+=roomR[i];
				r-=doorR[i];
				g+=roomG[i];
				g-=doorG[i];
				w+=roomW[i];
			}
		}
		val=max(val,r+g+w);
		int dif1=b-r;
		int dif2=c-g;
		int nowr=b;
		int nowg=c;
		int noww=w-dif1-dif2;
		for(int i=0;iif(!((a>>i) & 1))
			{
				nowr=b;
				nowg=c;
				noww=w-dif1-dif2;		
				if(doorR[i]>nowr)
				{
					noww-=(doorR[i]-nowr);
					nowr=0;
				}
				else
				{
					nowr-=doorR[i];
				}
				
				if(doorG[i]>nowg)
				{
					noww-=(doorG[i]-nowg);
					nowg=0;
				}
				else
				{
					nowg-=doorG[i];
				}
				nowr+=roomR[i];
				nowg+=roomG[i];			
				if(noww<0) continue;
				que.push(mp((a ^ (1<return val;
	}
};

challenge

PetrさんhosさんVasylさんjapljさんがいる部屋で競技歴1年未満の僕に

落とせと？？？？

Systest　通る！！！

137.26 214.98 0.0 +0/-0 121位

Rating 1772->1839(+67)

Med三回連続で通せたのうれしすぎる。

次回はだいぶ先になってしまうけどそのときも頑張りたい。

ツイートする