第一次秒掉IOI的题

啥？数字三角形？

第一，很明显n^3可以过，那不就水了吗？

但事实上村庄带权依旧可做

而且有朴素的n^2*logn做法

甚至整体二分或是决策单调性都可以AC

而且复杂度为严格的nlogn

所以水过啊

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef  int INT;#define int long long const int INF=1e18;int f[60000][35]={0};int p_sum_a[60000]={0};int p_sum_l[60000]={0};int p_sum[60000]={0};int s_sum_a[60000]={0};int s_sum_l[60000]={0};int s_sum[60000]={0};int a[60000]={0};int p_l[60000]={0};int s_l[60000]={0};int n,k;int getsum(int l,int r){	if(l==r)		return 0;	if(l
         
          =1;i--){ s_sum_a[i]=s_sum_a[i+1]+a[i]; } for(int i=1;i<=n;i++){ p_sum_l[i]=p_sum_l[i-1]+p_l[i]; } for(int i=n-1;i>=0;i--){ s_sum_l[i]=s_sum_l[i+1]+s_l[i]; } for(int i=2;i<=n;i++){ p_sum[i]=p_sum[i-1]+p_sum_a[i-1]*p_l[i]; } for(int i=n-1;i>=1;i--){ s_sum[i]=s_sum[i+1]+s_sum_a[i+1]*s_l[i]; }// for(int i=n;i>=1;i--){// cout<
          
           <<" ";// }// cout<<" kkk "<
          
         
        
       
      
     
    

附带权的题目（考场只写了60）

带权可过n=1e5代码

#include
    
     using namespace std;typedef int INT;#define int long long#define insert Insert#define LL long longconst int N=2e5+100;const int INF=1e17;int suma[N]={0};int sumf[N]={0};int sum[N]={0};int g[N][23];int f[N][23];int n,k;struct hh{LL x,y;};double suan(hh a,hh b){	if(b.x-a.x==0){return (b.y>a.y)?INF:-INF;}	return (double)(b.y-a.y)/(b.x-a.x);}struct que1{	hh q[N];int l,r;	que1(){l=1;r=0;}	void pop(LL x){while(l
     
      
       =suan(q[r],a))r--;		q[++r]=a;	}	hh top(){return q[l];}}q1[21],q2[21];/*struct Node{	int x,y;}q[N];double judge(Node A,Node B){	if(A.x==B.x){		return B.y>A.y?INF:-INF;	}	return (double)(B.y-A.y)/(B.x-A.x);}struct humdrum_queue{	int head,tail;	humdrum_queue(){head=1;tail=0;}	void pop(int x){while(head
       
        
         =judge(q[tail],A))			tail--;		q[++tail]=A;	}	Node top(){return q[head];}*///}q1[21],q2[21];INT main(){	scanf("%lld%lld",&n,&k);	for(int i=1;i<=n;++i)		scanf("%lld",&suma[i]);	for(int i=2;i<=n;++i)		scanf("%lld",&sum[i]),sum[i]+=sum[i-1];	for(int i=1;i<=n;++i)		sumf[i]=suma[i]*sum[i]+sumf[i-1],suma[i]+=suma[i-1];	/*scanf("%lld%lld",&n,&k);	for(int i=1;i<=n;i++){		scanf("%lld",&suma[i]);	}	for(int i=2;i<=n;i++){		scanf("%lld",&sum[i]);		sum[i]+=sum[i-1];	}	for(int i=1;i<=n;i++){		sumf[i]=suma[i]*sum[i]+sumf[i-1];		suma[i]+=suma[i-1];	}*/	for(int i=0;i<=k;++i)		q1[i].Insert((hh){suma[0],g[0][i]+sumf[0]}),q2[i].Insert((hh){sum[0],f[0][i]-sumf[0]+suma[0]*sum[0]});	for(int i=1;i<=n;i++){		for(int j=1;j<=k;j++){			q1[j-1].pop(sum[i]);hh now=q1[j-1].top();			f[i][j]=now.y-now.x*sum[i]+suma[i]*sum[i]-sumf[i];			q2[j].pop(suma[i]);now=q2[j].top();			g[i][j]=now.y-now.x*suma[i]+sumf[i];			g[i][j]=min(g[i][j],f[i][j]);			q1[j].Insert((hh){suma[i],g[i][j]+sumf[i]});			q2[j].Insert((hh){sum[i],f[i][j]-sumf[i]+suma[i]*sum[i]});						/*q1[j-1].pop(sum[i]);			Node now=q1[j-1].top();			f[i][j]=now.y-now.x*sum[i]+suma[i]*sum[i]-sumf[i];			q2[j].pop(suma[i]);			now=q2[j].top();			g[i][j]=now.y-now.x*suma[i]+sumf[i];			g[i][j]=min(g[i][j],f[i][j]);			q1[j].Insert((Node){suma[i],g[i][j]+sumf[i]});			q2[j].Insert((Node){sum[i],f[i][j]-sumf[i]+suma[i]*sum[i]});*/		}	}	int ans=g[n][k];	for(int i=1;i<=k;i++){		ans=min(ans,g[n][i]);	}	cout<