2014-02-26

■ SRM 610 Medium 16:14

やっと分かった。

refuelが大きい順に見ればよいことを示す。

これはrefuelが小さいもの->refuelが大きいものと取れるのに

refuelが大きいもの->refuelが小さいものとは取れない、ということはありえないことを示せばよい.

具体的には(duration=x,refuel=small)と(duration=y,refuel=big)を考えることにする。

もともとの量をaとすると

前者: a-x+small >= y <=> a+small >= x+y

後者: a-y+big < x <=> a+big < x+y

small

ツイートする

■ SRM 610 15:43

Easy:

O(N^3)ってどうやるんだろう。ていうかO(N^4)通す気あるならN<=50にしてほしかった

#line 2 "TheMatrix.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
// I'll become a member of  IOI 2014 Japan team.
#include 
#include 
#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;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i
class TheMatrix
{
	public:
	int MaxArea(vector  board) 
	{
		int n=board.size();
		int m=board[0].size();
		int ret=1;
		for(int i=0;ifor(int j=0;jif(ret>=(n-i)*(m-j)) continue;
				int tot=1;
				for(int k=i+1;kif(board[k-1][j]==board[k][j]) break; else tot++;
				ret=max(ret,tot);
				for(int x=j+1;xif(board[i][x]==board[i][x-1]) break;
					tot=1;
					for(int k=i+1;kfor(int y=j;y<=x;y++)
						{
							if(board[k-1][y]==board[k][y]) goto out;
						}
						tot++;
					}
					out:;
					ret=max(ret,tot*(x-j+1));
				}
			}
		}
		return ret;

	}
};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

Med:

こういう問題は大嫌いです。(解けなかった)

#line 2 "AlbertoTheAviator.cpp"
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
// I'll become a member of  IOI 2014 Japan team.
#include 
#include 
#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;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i
class AlbertoTheAviator
{
	public:
	int dp[55][5005],ret;
	int MaximumFlights(int F, vector <int> duration, vector <int> refuel) 
	{
		P s[55];
		for(int i=0;ifor(int i=0;ifor(int j=0;j<=F;j++)
			{
				dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
				if(j>=s[i].fi && j-s[i].fi+s[i].sc<=F)
				{
					dp[i+1][j-s[i].fi+s[i].sc]=max(dp[i+1][j-s[i].fi+s[i].sc],dp[i][j]+1);
					
				}
			}
		}
		for(int i=0;i<=F;i++) ret=max(ret,dp[refuel.size()][i]);
		return ret;
	}
};


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

challenge -1

systest fail

ox- 305位

Rating 2118->-INF(-85)

Medのような「実はGreedyに処理していいということに気づけばやるだけ」みたいな

問題本当に苦手なんだけどどうすればいいんだろう...もうだめぽ

ツイートする