fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3*/
  2. /*tai vi anh yeu duoi*/
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. using int64=long long;
  6. #define ll long long
  7. const int MOD=998244353;
  8. const int MAX=1e6+100;
  9. typedef pair<int,int> ii;
  10. int add(int a,int b){a+=b;if(a>=MOD)a-=MOD;return a;}
  11. int mul(long long a,long long b){ return int((a*b)%MOD);}
  12. signed main(){
  13.     #define name "HsonW"
  14.     ios::sync_with_stdio(0);
  15.     cin.tie(NULL);
  16.     if(fopen(name ".inp", "r")){
  17.         freopen(name ".inp", "r", stdin);
  18.         freopen(name ".out", "w", stdout);
  19.     }
  20.     int n,k;
  21.     cin >>n>>k;
  22.     vector<int>a(n);
  23.     for(int &x:a) cin >>x;
  24.     sort(a.begin(),a.end());
  25.     int maxd=(a[n-1]-a[0])/(k-1);
  26.     ll ans=0;
  27.     vector<int>preok(n),dp(n),pref(n);
  28.     for(int t=1;t<=maxd;t++){
  29.         int p=0;
  30.         for(int i=0;i<n;i++){
  31.             while(p<i && a[i]-a[p]>=t) p++;
  32.             preok[i]=p-1;
  33.         }
  34.         for(int i=0;i<n;i++){
  35.             dp[i]=1;
  36.             pref[i]=(i>0 ? add(pref[i-1],dp[i]):dp[i]);
  37.         }
  38.         for(int j=2;j<=k;j++){
  39.             vector<int>newdp(n),newpref(n);
  40.             for(int i=0;i<n;i++){
  41.                 int mx=preok[i];
  42.                 if(mx>=0) newdp[i]=pref[mx];
  43.                 else newdp[i]=0;
  44.                 newpref[i]=(i>0 ? add(newpref[i-1],newdp[i]):newdp[i]);
  45.             }
  46.             dp.swap(newdp);
  47.             pref.swap(newpref);
  48.         }
  49.         int ct=0;
  50.         for(int i=0;i<n;i++){
  51.             ct=add(ct,dp[i]);
  52.         }
  53.         ans=(ans+ct)%MOD;
  54.     }
  55.     cout <<ans;
  56.  
  57. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
4 3
2 3 5 7
stdout
copy 
6
https://ideone.com/MasFNp
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!