Submission #2383

#	Time	Username	Problem	Language	Result	Execution time	Memory
2383		sebin	지우개 (GA4_eraser)	C++98	0 / 100	43 ms	4088 KiB

eraser

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

int in[100001];
long long d[100001];

long long mod(long long n){ return n%1000000007; }

int main()
{
    vector <long long> k;
    int n,a,i,maxa,mina;
    long long sum1=0,sum2=0,aa;
    cin >> n;
    if(n<3){
        cout <<"0"<<endl;
        return 0;
    }
    maxa=0;
    mina=100001;
    for(i=1;i<=n;i++){
        cin >> a;
        in[a]++;
        if(maxa<a) maxa=a;
        if(mina>a) mina=a;
    }
    for(i=mina;i<=maxa;i++){
        if(in[i]>0){
            k.push_back(i*in[i]);
        }
    }
    d[2]=mod(mod(k[0]*k[1])*k[2]);
    sum1+=k[0]+k[1]+k[2];
    sum2+=mod( mod(k[0]*k[0])+mod(k[1]*k[1])+mod(k[2]*k[2]) );
    for(i=3;i<k.size();i++){
        if(sum1>100000) sum1%=100000;
        d[i]=mod(d[i-1]+(i+1)*(mod(aa-sum2))/2);
        sum1=mod(sum1+k[i]);
        sum2=mod(sum2+k[i]*k[i]);
    }
    printf("%lld\n",d[k.size()-1]);
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 26
• Subtask 6: 0 / 28