#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int main()
{
int n,i,j,ans;
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
cin>>a[i][j];
for(i=2;i<=n;i++)
for(j=1;j<=i;j++)
{
if(a[i-1][j]>=a[i-1][j-1]) a[i][j]+=a[i-1][j];
else a[i][j]+=a[i-1][j-1];
}
ans=a[n][1];
for(j=2;j<=i;j++)
if(a[n][j]>ans) ans=a[n][j];
cout<<ans;
}
#include<bits/stdc++.h>
using namespace std;
string s,t;
int main()
{
cin>>s>>t;
if(s.size()!=t.size()){
printf("-1\n");
}else
if(s==t){
printf("0\n");
}else{
for(int i=1;i<s.size();++i){
char tmp=s[s.size()-1];
s=s.substr(0,s.size()-1);
s=tmp+s;
if(s==t){
printf("%d\n",i);
return 0;
}
}
printf("-1\n");
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans=INT_MIN;
const int N=200050;
int n;
int u,v;
vector<int>tree[N];
int f[N][2];
int p,maxn=INT_MIN;
void dfs(int i,int fa,int len){
if(len>maxn) maxn=len,p=i;
for(int j=0;j<tree[i].size();++j){
if(tree[i][j]==fa) continue;
dfs(tree[i][j],i,len+1);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1,0,0);
maxn=INT_MIN;
dfs(p,0,0);
printf("%d",maxn);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=200050;
int n;
vector<int>tree[N];
int dis[N];
int ans=0;
void dfs(int i,int fa)
{
int mx=INT_MIN;
for(int k=0;k<tree[i].size();k++)
{
int ch=tree[i][k];
if(ch==fa)continue;
dfs(ch,i);
dis[i]=max(dis[ch]+1,dis[i]);
ans=max(ans,dis[ch]+mx+2);
mx=max(mx,dis[ch]);
}
}
int main()
{
scanf("%d",&n);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1,0);
if(ans<dis[1])ans=dis[1];
printf("%d",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans=INT_MIN;
const int N=200050;
int n;
int u,v;
vector<int>tree[N];
int f[N][2];
void dfs(int i,int fa){
ll tot=0;
int maxn=INT_MIN;
for(int j=0;j<tree[i].size();++j){
if(tree[i][j]==fa) continue;
dfs(tree[i][j],i);
tot+=f[tree[i][j]][0];
maxn=max(maxn,f[tree[i][j]][1]-f[tree[i][j]][0]+1);
}
f[i][1]=tot;
f[i][0]=tot+maxn;
ans=max(f[i][0],f[i][1]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1,0);
printf("%d",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,llt,rrt,cct,tty;
int a[110][110],s[110][110],maxn=-0x3f3f3f;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&a[i][j]);
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<n;++i)
for(int j=1;j<n;++j)
for(int u=i+1;u<=n;++u)
for(int v=j+1;v<=n;v++)
maxn=max(maxn,s[u][v]-s[u][j-1]-s[i-1][v]+s[i-1][j-1]);
printf("%d\n",maxn);
return 0;
}
/*
我们考虑二分答案 x，只要判断是否存在 ≥x 的解。
在判断时，把大于等于 x 的数替换成 1，其他数替换成 -1。
那么就进行了一个转换：一段中位数至少是 x 转换为了这段的和是正的。
所以查找新序列中有没有一个长度至少是 k 的子串满足和为正即可。
发现就是求长度至少是 k 的子串的和的最大值。
这个问题可以使用前缀和，维护前缀和的前缀最小值。
枚举子串长度的右端点 i，找到 1到 i-k 的前缀最小值即可。
所以总复杂度是O(nlogn) 的。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll l,r;
ll ans;
ll a[200005],s[200005],maxn[200005];
bool check(ll mid)
{
for(ll i=1;i<=n;++i)
{
s[i]=s[i-1]+(a[i]<mid?-1:1);
maxn[i]=min(maxn[i-1],s[i]);
if(i>=k&&s[i]-maxn[i-k]>0) return 1;
}
return 0;
}
int main()
{
scanf("%lld%lld",&n,&k);
for(ll i=1;i<=n;++i) scanf("%lld",&a[i]);
l=1;
r=n;
ans=-1;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);cin>>ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t,n;
map<int,int>s;
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d",&n);
bool f=0;
for(int j=1;j<=n;++j){
int x;
scanf("%d",&x);
s[x]++;
if(s[x]>n/2&&!f){
printf("YES %d\n",x);
f=1;
}
}
if(!f){
printf("NO\n");
}
s.clear();
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
while(1){
scanf("%d%d%d",&a,&b,&c);
if(a==0&&b==0&&c==0) break;
long long a_=a*a,b_=b*b,c_=c*c;
if(a_==b_+c_||b_==a_+c_||c_==a_+b_){
printf("right\n");
}else{
printf("wrong\n");
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
long long s;
bool fo,fj;
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
s=0,fo=0,fj=0;
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
if(x%2==0) fo=1;else fj=1;
s+=x;
}
if(s%2==1){
printf("YES\n");
}else
if(fo&&fj){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
bool f[20][20];
int s[20][20];
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;++i){
int x,y;
scanf("%d%d",&x,&y);
f[x][y]=1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(f[i][j]) continue;
s[i][j]=s[i-1][j]+s[i][j-1];
if(i==1&&j==1) s[i][j]=1;
}
}
printf("%d",s[n][m]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
ans+=x;
ans%=10;
}
if(ans&1) printf("Alice"); else printf("Bob");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,a[1010],maxn;
int f1[1010],f2[1010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
f1[i]=1;
for(int j=1;j<i;++j){
if(a[j]<a[i]){
f1[i]=max(f1[i],f1[j]+1);
}
}
}
for(int i=n;i>=1;--i){
f2[i]=1;
for(int j=n;j>i;--j){
if(a[j]<a[i]){
f2[i]=max(f2[i],f2[j]+1);
}
}
}
for(int i=0;i<=n;++i){
maxn=max(f1[i]+f2[i]-1,maxn);
}
printf("%d\n",maxn);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t,n,maxn;
int a[110];
int f[110];
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d",&n);
maxn=0;
for(int j=1;j<=n;++j){
scanf("%d",&a[j]);
}
memset(f,0,sizeof(f));
for(int j=1;j<=n;++j){
f[j]=1;
for(int k=1;k<j;++k){
if(a[k]<a[j]){
f[j]=max(f[j],f[k]+1);
}
}
maxn=max(f[j],maxn);
}
memset(f,0,sizeof(f));
for(int j=1;j<=n;++j){
f[j]=1;
for(int k=1;k<j;++k){
if(a[k]>a[j]){
f[j]=max(f[j],f[k]+1);
}
}
maxn=max(f[j],maxn);
}
printf("%d\n",maxn);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int s[50010];
int l[10],r[10];
int maxn;
void IN(){scanf("%d",&n);for(int i=1;i<=n;++i){int x;scanf("%d",&x);s[i]=(s[i-1]+x)%7;}}
void OUT(){printf("%d\n",maxn);}
int main()
{
IN();
for(int i=n;i>=1;--i){l[s[i]]=i;}/*记录最左边的 |余相| */
for(int i=1;i<=n;++i){r[s[i]]=i;}/*记录最右边的 |数同| */
l[0]=0;/*若余数本为0,无需相减抵消余数*/
for(int i=0;i<7;++i){maxn=max(r[i]-l[i],maxn);}//余数相同的两数相减余数为0
OUT();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
void in(int &x){
char c=getchar(); ;
while (c<'0' || c>'9') c=getchar();
for (x=0; c>='0' && c<='9'; c=getchar())
x=x*10+c-'0';
}
int main(){
int t=1, n;
while (t--){
scanf("%d", &n);
int sum=0;
for (int i=0; i<n; i++){
in(a[i]);
sum+=a[i];
}
sort(a, a+n);
int avg=sum/n, ans=0, k=sum%n;
for (int i=0; i<n-k; i++)
ans+=abs(a[i]-avg);
for (int i=n-k; i<n; i++)
ans+=abs(a[i]-avg-1);
printf("%d\n", ans/2);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int f[55][55][55][55];
int v[55][55];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&v[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int u=1;u<=n;u++)
{
for(int w=1;w<=m;w++)
{
if(i+j==u+w)
{
int s1,s2;
s1=max(f[i-1][j][u-1][w],f[i-1][j][u][w-1]);
s2=max(f[i][j-1][u-1][w],f[i][j-1][u][w-1]);
f[i][j][u][w]=max(s1,s2)+v[i][j]+v[u][w];
if(i==u&&j==w) f[i][j][u][w]-=v[u][w];
}
}
}
}
}
printf("%d",f[n][m][n][m]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dp[12][12][12][12],a[12][12];
int n;
int x=1,y=1,z=1;
int main()
{
cin>>n;
while(x!=0||y!=0||z!=0)
{
cin>>x>>y>>z;
a[x][y]=z;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
for(int q=1;q<=n;q++)
{
int u=max(dp[i-1][j][k-1][q],dp[i-1][j][k][q-1]);
int v=max(dp[i][j-1][k-1][q],dp[i][j-1][k][q-1]);
dp[i][j][k][q]=max(u,v)+a[i][j]+a[k][q];//数字三角
if(i==k&&q==j)dp[i][j][k][q]-=a[i][j];
}
}
}
}
cout<<dp[n][n][n][n];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110][110];
int f[110][110];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%d",&a[i][j]);
}
}
memset(f,0x3f3f, sizeof f);
f[1][1]=a[1][1];
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
f[i][j]=min(f[i][j],f[i-1][j]+a[i][j]);
f[i][j]=min(f[i][j],f[i][j-1]+a[i][j]);
}
}
printf("%d",f[n][n]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t;
int r,c;
int a[110][110];
int f[110][110];
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;++i){
scanf("%d%d",&r,&c);
for(int j=1;j<=r;++j){
for(int k=1;k<=c;++k){
scanf("%d",&a[j][k]);
}
}
for(int j=1;j<=r;++j){
for(int k=1;k<=c;++k){
f[j][k]=max(f[j-1][k],f[j][k-1])+a[j][k];
}
}
printf("%d\n",f[r][c]);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,dis,ans;
int a[100050];
int main()
{
scanf("%d%d",&n,&dis);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=2;i<n;++i){
if(a[i+1]-a[i-1]<=dis){
ans++;
a[i]=a[i-1];
}
}
printf("%d",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
string a,b;
int main()
{
cin>>a>>b;
for(int i=0;i<a.size();i++)
{
for(int j=0;j<b.size();j++)
{
dp[i][j]=max(i>0?dp[i-1][j]:0,j>0?dp[i][j-1]:0);
if(a[i]==b[j]) {dp[i][j]=max(dp[i][j],i>0&&j>0?dp[i-1][j-1]+1:1);}
}
}
printf("%d",dp[a.size()-1][b.size()-1]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100050];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;++i){
int x;
scanf("%d",&x);
if(x<=a[1]){printf("%d\n",a[1]);continue;}
int it=lower_bound(a+1,a+n+1,x)-a;
if(a[it]==x) {printf("%d\n",x);continue;}
int itt=it-1;
if(abs(a[itt]-x)<=abs(a[it]-x)){
printf("%d\n",a[itt]);
}else{
printf("%d\n",a[it]);
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m;
int maxn;
int p[380];
int find(int x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
struct node{
int u,v,vol;
}a[100050];
bool cmp(node a,node b){
return a.vol<b.vol;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) p[i]=i;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].vol);
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;++i){
int fx=find(a[i].u),fy=find(a[i].v);
if(fx!=fy) p[fx]=fy,maxn=a[i].vol;
}
printf("%d %d",n-1,maxn);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
bool check(int x,int y){
if(x<0||x>n||y>m) return false;
return true;
}
void dfs(int x,int y){
if(!check(x,y)) return;
if(x==n&&y==m){
++ans;
}
dfs(x+1,y+2);
dfs(x-1,y+2);
dfs(x+2,y+1);
dfs(x-2,y+1);
}
int main()
{
scanf("%d%d",&n,&m);
dfs(0,0);
printf("%d",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
int stu,km;
string name;
}sta[200];
long long minn=LONG_LONG_MAX;
string mina;
int l;
int main()
{
while(1){
++l;cin>>sta[l].stu>>sta[l].km>>sta[l].name;
if(sta[l].name=="Moscow") break;
}
for(int i=1;i<=l;++i){
long long sum=0;
for(int j=1;j<=l;++j){
if(i==j) continue;
sum+=sta[j].stu*(abs(sta[i].km-sta[j].km));
}
if(sum<=minn){
minn=sum;
mina=sta[i].name;
}
}
cout<<mina;printf(" %d\n",minn);
cin>>minn;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n;
int lf[110],rf[110],a[110];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
lf[i]=1;
for(int j=1;j<i;++j){
if(a[i]>a[j]) lf[i]=max(lf[i],lf[j]+1);
}
}
for(int i=n;i>=1;--i){
rf[i]=1;
for(int j=i+1;j<=n;++j){
if(a[i]>a[j]) rf[i]=max(rf[i],rf[j]+1);
}
}
int maxn=0;
for(int i=1;i<=n;++i){
int s=lf[i]+rf[i]-1;
maxn=max(maxn,s);
}
printf("%d",n-maxn);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int t;
int a[101];
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++){
int n;
scanf("%d",&n);
for(int j=1;j<=n;j++){
scanf("%d",&a[j]);
}
int ans=0;
for(int j=1;j<=n;j++){
for(int k=j;k<=n;k++){
for(int x=k;x<=n;x++){
if(a[j]+a[k]==a[x]) ans++;
}
}
}
printf("%d\n",ans);
}
}
