#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; const int INF=1e9+5; int n,m,k,w,tot,minn=INF,mark; int f[1005][1005],a[1005],b[101],d[101]; template <class t>void red(t &x) { x=0; int w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } x*=w; } void input() { freopen("luogu.txt","r",stdin); freopen("lemon.out","w",stdout); } int main() { input(); red(n); red(m); red(k); red(w); while(n--) { memset(f,0x3f,sizeof(f)); for(int i=0;i<=m;++i) { f[i][i]=0; if(!i) continue; red(a[i]); } a[m+1]=w; for(int i=2;i<=m+1;++i) for(int j=0;j+i<=m+1;++j) { int e=j+i-1; for(int k=j;k<e;++k) if(f[j][k]+f[k+1][e]+a[e+1]-a[j]<f[j][e]) f[j][e]=f[j][k]+f[k+1][e]+a[e+1]-a[j]; } printf("%d\n",b[++tot]=f[0][m]); } for(int i=1;i<=tot;++i) if(b[i]<minn) { minn=b[i]; mark=i; } d[1]=0; for(int i=2;i<=tot;++i) d[i]=(d[i-1]+k)%i; printf("\n%d",1+abs(d[tot]+1-mark)); return 0; }View Code