Educational Codeforces Round 95 E問題 - Expected Damage

Source

Educational Codeforces Round 95 E問題
Problem description

問題概要

省略

解法

省略

cLay（version 20200916-1）のコード

C++に変換後のコードはこちら

//no-unlocked
#define MD 998244353
int N, M, D[2d5], A[2d5], B[2d5], ind[2d5];
Modint res[2d5];
{
  int ws = 0; ll w = 0;
  int ss = 0; ll s = 0;

  rd(N,M,D(N),(A,B)(M));
  rep(i,M) ind[i] = i;
  sortA(N,D);
  sortA(M,B,A,ind);

  ss = N;
  rep(i,N) s += D[i];

  rep(i,M){
    while(ws < N && D[ws] < B[i]){
      w += D[ws];
      s -= D[ws];
      ws++;
      ss--;
    }
    res[ind[i]] += Modint(w) * Kth1(ss+1-A[i], 0, ss+1) / (ss+1);
    res[ind[i]] += Modint(s) * Kth1(ss-A[i], 0, ss) / ss;
  }
  wtLn(res(M));
}

Current time: 2024年04月20日16時00分49秒
Last modified: 2020年09月16日02時28分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)