D. Arpa and a list of numbers Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017)

时间：2022-06-22 22:36:13

http://codeforces.com/contest/851/problem/D

分区间操作

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <time.h>

 #include <string>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <vector>

 #include <bitset>

 #include <ext/rope>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 #define ll long long

 #define minv 1e-6

 #define inf 1e18

 #define pi 3.1415926536

 #define E  2.7182818284

 const ll mod=1e9+;//

 const int maxn=2e6+;

 bool vis[maxn]={};

 ll tot[maxn]={},sum[maxn]={};

 int main()

 {

     int n,x,y,z,i,j,pos;

     ll v,r=inf,a;

     scanf("%d%d%d",&n,&x,&y);

     z=x/y;

     for (i=;i<=n;i++)

     {

         scanf("%lld",&a);

         tot[a]++;

         sum[a]+=a;

     }

     for (i=;i<=2e6;i++)

         tot[i]+=tot[i-],sum[i]+=sum[i-];

     for (i=;i<=1e6;i++)

         if (!vis[i])

         {

             v=;

             //(j-i,j)

             for (j=i;j<=2e6;j+=i)

             {

                 pos=max(j-z,j-i+);//[pos,j]

                 v+= (ll)(tot[pos-]-tot[j-i])*x + ( (ll)(tot[j]-tot[pos-])*j-(ll)(sum[j]-sum[pos-]) )*y;

                 vis[j]=;

             }

             r=min(r,v);

         }

     cout<<r;

     return ;

 }

相关文章