四校联考——20170730模拟赛

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#pragma o1
using namespace std;
inline int read(){
    int x=0;char c=getchar();bool t=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)t=0;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();}
    return t?x:-x;
}
const int maxn=500010,mod=1e9+9;
struct Yzy{int h,x[6];}a[maxn];
int n,d,su[maxn],suf[maxn],kind;
bool cmp(Yzy i,Yzy j){
    return i.x[kind]<j.x[kind];
}
int main()
{
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    n=read();d=read();
    for(int i=1;i<=n;i++){
        a[i].h=read();
        for(int j=1;j<=d;j++)a[i].x[j]=read();
    }
    int ans=0;
    for(kind=1;kind<=d;kind++){
        sort(a+1,a+1+n,cmp);
        for(int i=n;i>=1;i--){
            su[i]=(su[i+1]+a[i].h)%mod;
            suf[i]=(suf[i+1]+(ll)a[i].h*a[i].x[kind])%mod;
        }
        for(int i=1;i<=n;i++)
            ans=((ans+(ll)a[i].h*suf[i+1]
               -(ll)a[i].h*a[i].x[kind]%mod*su[i+1])
               %mod+mod)%mod;
    }
    printf("%d\n",ans);
    return 0;
}