Beyond the Void

#include <iostream>
#define MAX 4000001
using namespace std;
 
int N,L;
char S[MAX];
bool F[MAX];
char W[6][10]={"one","puton","out","in","input","output"};
int Len[6];
 
void init()
{
	int i;
	freopen("1102.in","r",stdin);
	freopen("1102.out","w",stdout);
	scanf("%d\n",&N);
	for (i=0;i<6;i++)
		Len[i]=strlen(W[i]);
}
 
bool match(char *S,char *k)
{
	for (;*k;k++,S++)
		if (*k!=*S)
			return false;
	return true;
}
 
bool dynamic()
{
	int i,j;
	F[0]=true;
	for (i=1;i<=L;i++)
	{
		F[i]=false;
		for (j=0;j<6;j++)
		{
			if (i-Len[j]>=0 && match(&S[i-Len[j]+1],W[j]))
			{
				if (F[i-Len[j]])
				{
					F[i]=true;
					break;
				}
			}
		}
	}
	return F[L];
}
 
int main()
{
	init();
	for (int i=1;i<=N;i++)
	{
		scanf("%s",S+1);
		L=strlen(S+1);
		memset(F,0,sizeof(F));
		bool yes=dynamic();
		if (yes)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

#include <iostream>
#define MAX 100
using namespace std;
 
struct interval
{
	int left,right;
};
 
int N,Ans;
interval S[MAX];
int F[MAX],G[MAX],A[MAX];
 
template <class T> void SWAP(T &a,T &b)
{
	T c=a;a=b;b=c;
}
 
int cmp(const void *a,const void *b)
{
	if (((interval *)a)->left< ((interval *)b)->left)
		return -1;
	if (((interval *)a)->right< ((interval *)b)->right)
		return -1;
	return 1;
}
 
void init()
{
	int i;
	freopen("1112.in","r",stdin);
	freopen("1112.out","w",stdout);
	cin >> N;
	for (i=1;i<=N;i++)
	{
		cin >> S[i].left >> S[i].right;
		if (S[i].left > S[i].right)
			SWAP(S[i].left,S[i].right);
	}
	qsort(S+1,N,sizeof(S[0]),cmp);
}
 
void dynamic()
{
	int i,j;
	S[0].left=S[0].right=-1000;
	S[N+1].left=S[N+1].right=1000;
	for (i=1;i<=N+1;i++)
	{
		for (j=0;j<i;j++)
		{
			if (S[i].left>=S[j].right && F[j]+1>F[i])
			{
				F[i]=F[j]+1;
				G[i]=j;
			}
		}
	}
	Ans=F[N+1]-1;
	cout << Ans << endl;
	for (i=G[N+1];i;i=G[i],Ans--)
		A[Ans]=i;
	for (i=1;i<=F[N+1]-1;i++)
		cout << S[A[i]].left << ' ' << S[A[i]].right << endl;
}
 
int main()
{
	init();
	dynamic();
	return 0;
}

#include <iostream>
 
using namespace std;
 
const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;
 
int M,N,P;
bool cross[MAX][MAX];
double F[2][MAX];
 
void init()
{
	int i,a,b;
	freopen("1119.in","r",stdin);
	freopen("1119.out","w",stdout);
	cin >> M >> N >> P;
	N++;M++;
	for (i=1;i<=P;i++)
	{
		cin >> b >> a;
		a++;b++;
		cross[a][b]=true;
	}
	cross[1][1]=true;
	F[0][0]=-Dc;
}
 
void dynamic()
{
	int i,j,p;
	double min;
	for (i=p=1;i<=N;i++,p=!p)
	{
		for (j=1;j<=M;j++)
		{
			min=INF;
			if (i>1 && F[!p][j] + Dl <min)
			{
				min=F[!p][j] + Dl;
			}
			if (j>1 && F[p][j-1] + Dl <min)
			{
				min=F[p][j-1] + Dl;
			}
			if (cross[i][j] && F[!p][j-1] + Dc < min)
			{
				min=F[!p][j-1] + Dc;
			}
			F[p][j]=min;
		}
	}
	printf("%.0lf",F[!p][M]);
}
 
int main()
{
	init();
	dynamic();
	return 0;
}

#include <iostream>
 
using namespace std;
 
const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;
 
struct Point
{
	int x,y;
};
 
int M,N,P;
Point T[MAX];
int F[MAX];
double Ans;
 
inline int cmp(const void *a,const void *b)
{
	if (((Point *)a)->x==((Point *)b)->x && ((Point *)a)->y<((Point *)b)->y)
		return -1;
	return ((Point *)a)->x < ((Point *)b)->x ?-1 :1;
}
 
void init()
{
	int i,a,b;
	freopen("1119.in","r",stdin);
	freopen("1119.out","w",stdout);
	cin >> M >> N >> P;
	N++;M++;
	for (i=1;i<=P;i++)
	{
		cin >> b >> a;
		a++;b++;
		T[i].x=a;
		T[i].y=b;
	}
	qsort(T+1,P,sizeof(T[0]),cmp);
}
 
void dynamic()
{
	int i,j,max,cnt=0,d;
	for (i=1;i<=P;i++)
	{
		max=0;
		for (j=0;j<=i-1;j++)
		{
			if (T[j].x<T[i].x && T[j].y<T[i].y &&  F[j] + 1 > max)
				max=F[j]+1;
		}
		F[i]=max;
		if (F[i]>cnt)
			cnt=F[i];
	}
	d=N+M-cnt*2-2;
	Ans=d*Dl + cnt*Dc;
	printf("%.0lf",Ans);
}
 
int main()
{
	init();
	dynamic();
	return 0;
}

#include <iostream>
 
using namespace std;
 
const int MAX=10001;
 
int A,B,Ans;
int F[MAX];
 
void init()
{
	freopen("1138.in","r",stdin);
	freopen("1138.out","w",stdout);
	cin >> B >> A;
}
 
void dynamic()
{
	int i,j,k;
	Ans=F[A]=1;
	for (i=A;i<=B-1;i++)
	{
		if (!F[i]) continue;
		for (k=1;k<=100;k++)
			if (i*k%100==0)
			{
				j=i+i*k/100;
				if (j>B) continue;
				if (F[i]+1>F[j])
					F[j]=F[i]+1;
				if (F[j]>Ans)
					Ans=F[j];
			}
	}
}
 
 
int main()
{
	init();
	dynamic();
	cout << Ans;
	return 0;
}

#include <iostream>
 
using namespace std;
 
const int MAX=101;
const int INF=0x7FFFFFFF;
 
int Num[MAX][MAX],F[MAX][MAX];
int G[MAX];
int N,Ans=-INF;
 
void init()
{
	int i,j;
	freopen("1146.in","r",stdin);
	freopen("1146.out","w",stdout);
	cin >> N;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			scanf("%d",&Num[i][j]);
		}
	}
}
 
void dynamic()
{
	int i,j,k,Item;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			F[i][j]=F[i][j-1]+Num[i][j];
		}
	}
 
	for (i=1;i<=N;i++)
	{
		for (j=i;j<=N;j++)
		{
			for (k=1;k<=N;k++)
			{
				Item=F[k][j]-F[k][i-1];
				if (G[k-1] + Item > Item)
					G[k]=G[k-1] + Item ;
				else
					G[k]=Item;
				if (G[k]>Ans)
					Ans=G[k];
			}
		}
	}
}
 
int main()
{
	init();
	dynamic();
	cout << Ans ;
	return 0;
}