/*bzoj 1613*//*暴力5884ms*/#include<cstdio>#define maxn 10010using namespace std;int n,m,a[maxn],f[maxn][510];int max(int x,int y){    return x>y?x:y;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    for(int i=1;i<=n;i++)        for(int j=0;j<=m;j++){            if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);            if(i-j>=0)for(int k=0;k<=j;k++)f[i][0]=max(f[i][0],f[i-j][k]);        }    printf("%d\n",f[n][0]);    return 0;}/*简单优化224ms*/#include<cstdio>#define maxn 10010using namespace std;int n,m,a[maxn],f[maxn][510];int max(int x,int y){    return x>y?x:y;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    for(int i=1;i<=n;i++)        for(int j=0;j<=m;j++){            if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);            if(i-j>=0)f[i][0]=max(f[i][0],max(f[i-j][j],f[i-1][0]));        }    printf("%d\n",f[n][0]);    return 0;}/*bzoj 1614 二分*/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define maxn 1010#define inf 0x3f3f3f3fusing namespace std;int n,m,k,num,head[maxn],f[maxn],dis[maxn],l,r,ans;struct node{    int v,t,pre;}e[maxn*20];queue<int>q;int init(){    int x=0;char s=getchar();    while(s<‘0‘||s>‘9‘)s=getchar();    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x;}void Add(int from,int to,int dis){    num++;e[num].v=to;    e[num].t=dis;    e[num].pre=head[from];    head[from]=num;}bool SPFA(int x){    for(int i=1;i<=n;i++)dis[i]=inf;    q.push(1);f[1]=1;dis[1]=0;    while(!q.empty()){        int k=q.front();        q.pop();f[k]=0;        for(int i=head[k];i;i=e[i].pre){            int v=e[i].v,cost=0;            if(e[i].t>x)cost++;            if(dis[v]>dis[k]+cost){                dis[v]=dis[k]+cost;                if(f[v]==0){                    q.push(v);f[v]=1;                }            }        }    }    return dis[n]<=k;}int main(){    n=init();m=init();k=init();    int u,v,t;    for(int i=1;i<=m;i++){        u=init();v=init();t=init();        Add(u,v,t);Add(v,u,t);r=max(r,t);    }    ans=-1;    while(l<=r){        int mid=(l+r)/2;        if(SPFA(mid)){            r=mid-1;            ans=mid;        }        else l=mid+1;    }    printf("%d\n",ans);    return 0;}/*bzoj 1609 记忆化*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 30010using namespace std;int n,a[maxn],f1[maxn][4],f2[maxn][4];int Dfs1(int now,int lim){    if(f1[now][lim]!=-1)return f1[now][lim];    if(now==n+1)return 0;    int r=0x7fffffff;    if(a[now]>=lim)r=min(r,Dfs1(now+1,a[now]));    r=min(r,Dfs1(now+1,lim)+1);    return f1[now][lim]=r;}int Dfs2(int now,int lim){    if(f2[now][lim]!=-1)return f2[now][lim];    if(now==n+1)return 0;    int r=0x7fffffff;    if(a[now]<=lim)r=min(r,Dfs2(now+1,a[now]));    r=min(r,Dfs2(now+1,lim)+1);    return f2[now][lim]=r;}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]);    memset(f1,-1,sizeof(f1));    memset(f2,-1,sizeof(f2));    printf("%d\n",min(Dfs1(1,0),Dfs2(1,4)));}/*bzoj 1610 模拟*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 210using namespace std;int n,x[maxn],y[maxn],ans;bool f[maxn*10][maxn*10][2];int Abs(int x){    return x<0?-x:x;}int Gcd(int a,int b){    return b==0?a:Gcd(b,a%b);}void Insert(int a,int b){    int c=0;    if(a==0)b=1;    else if(b==0)a=1;    else{        if(a*b<0)c=1;        int A=Abs(a),B=Abs(b);        int gcd=Gcd(A,B);        a=A/gcd;b=B/gcd;    }    if(f[a][b][c]==0)ans++;    f[a][b][c]=1;}int main(){    //freopen("lines.in","r",stdin);    //freopen("lines.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d%d",&x[i],&y[i]);    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++){            int X=x[i]-x[j];            int Y=y[i]-y[j];            Insert(X,Y);        }    printf("%d\n",ans);    return 0;}