結果
| 問題 |
No.3303 Heal Slimes 2
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-10-08 08:45:43 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,130 bytes |
| コンパイル時間 | 6,117 ms |
| コンパイル使用メモリ | 334,888 KB |
| 実行使用メモリ | 48,640 KB |
| 最終ジャッジ日時 | 2025-10-08 08:46:47 |
| 合計ジャッジ時間 | 58,494 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 16 WA * 15 |
ソースコード
// Smartphone Coding
#include"bits/stdc++.h"
#include"atcoder/all"
using namespace std;
using namespace atcoder;
using lint = long long;
using ulint = unsigned long long;
using llint = __int128_t;
#define endl '\n'
int const INF = 1<<30;
lint const INF64 = 1LL<<61;
lint const mod107 = 1e9+7;
using mint107 = modint1000000007;
long const mod = 998244353;
using mint = modint998244353;
long myprime = 998100007;
lint ceilDiv(lint a, lint b){if(a%b==0){return a/b;}
if(a>=0){return (a/b)+1;}
else{return -((-a)/b);}}
lint floorDiv(lint a, lint b){if(a%b==0){return a/b;}
if(a>=0){return (a/b);}
else{return -((-a)/b)-1;}}
lint Sqrt(lint x){lint upper = 1e9;lint lower = 0;while(upper - lower > 0){lint mid = (1+upper + lower)/2;if(mid * mid > x){upper = mid-1;}else{lower = mid;}}return upper;}
lint gcd(lint a,lint b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
lint lcm(lint a,lint b){return (a / gcd(a,b)) * b;}
lint chmin(vector<lint>&v){lint ans = INF64;for(lint i:v){ans = min(ans, i);}return ans;}
lint chmax(vector<lint>&v){lint ans = -INF64;for(lint i:v){ans = max(ans, i);}return ans;}
double dist(double x1, double y1, double x2, double y2){return sqrt(pow(x1-x2, 2) + pow(y1-y2,2));}
string toString(lint n){string ans = "";if(n == 0){ans += "0";}else{while(n > 0){int a = n%10;char b = '0' + a;string c = "";c += b;n /= 10;ans = c + ans;}}return ans;}
string toString(lint n, lint k){string ans = toString(n);string tmp = "";while(ans.length() + tmp.length() < k){tmp += "0";}return tmp + ans;}
vector<lint>prime;void makePrime(lint n){prime.push_back(2);for(lint i=3;i<=n;i+=2){bool chk = true;for(lint j=0;j<prime.size() && prime[j]*prime[j] <= i;j++){if(i % prime[j]==0){chk=false;break;}}if(chk)prime.push_back(i);}}
lint Kai[250001]; bool firstCallnCr = true;
lint ncrmodp(lint n,lint r,lint p){ if(firstCallnCr){ Kai[0] = 1; for(int i=1;i<=250000;i++){ Kai[i] = Kai[i-1] * i; Kai[i] %= p;} firstCallnCr = false;} if(n<0)return 0;
if(n < r)return 0;if(r<0)return 0;if(n==0)return 1;lint ans = Kai[n];lint tmp = (Kai[r] * Kai[n-r]) % p;for(lint i=1;i<=p-2;i*=2){if(i & p-2){ans *= tmp;ans %= p;}tmp *= tmp;tmp %= p;}return ans;}
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >=0; i--)
#define repp(i, x, y) for(int i = x; i < y; i++)
#define vec vector
#define pb push_back
#define eb emplace_back
#define se second
#define fi first
#define al(x) x.begin(),x.end()
#define ral(x) x.rbegin(),x.rend()
#define ins insert
using str=string;
struct Frac {
lint upper, lower;
Frac() {
Frac(0,1);
}
Frac(lint u, lint l) {
assert(l != 0);
if(u <= 0 && l < 0) {
upper = -u;
lower = -l;
} else {
upper = u;
lower = l;
}
reduction();
}
Frac(lint u) {
upper = u;
lower = 1;
}
void reduction() {
if(upper != 0) {
lint g = gcd(abs(upper), abs(lower));
upper /= g;
lower /= g;
if(lower < 0) {
lower *= -1;
upper *= -1;
}
} else {
lower = 1;
}
}
Frac operator+(const Frac &other) {
lint L = lower * other.lower;
lint U = upper*other.lower + lower*other.upper;
return Frac(U, L);
}
Frac operator-(const Frac &other) {
lint L = lower * other.lower;
lint U = upper*other.lower - lower*other.upper;
upper = U;
lower = L;
return Frac(U, L);
}
bool operator<=(const Frac &other) {
return upper*other.lower <= lower*other.upper;
}
Frac operator*(const Frac &other) {
lint L = lower * other.lower;
lint U = upper * other.upper;
return Frac(U, L);
}
Frac operator/(const Frac &other) {
assert(other.upper != 0);
lint L = lower * other.upper;
lint U = upper * other.lower;
return Frac(U, L);
}
};
bool operator<(const Frac &left, const Frac &right) {
return left.upper*right.lower < left.lower*right.upper;
}
template< typename T >
T extgcd(T a, T b, T &x, T &y) {
T d = a;
if(b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
} else {
x = 1;
y = 0;
}
return d;
}
struct edge{
int to;
lint cost;
edge(int t,lint c=1){
to=t;
cost=c;
}
};
using graph = vector<vec<edge>>;
vec<lint>dijkstra(int s, graph& g){
priority_queue<pair<lint,lint>>que;
vec<lint> cost(g.size(),INF64);
cost[s]=0;
que.push({0,s});
while(!que.empty()){
auto q=que.top();
que.pop();
int v=q.second;
for(auto& e:g[v]){
if(cost[e.to]>cost[v]+e.cost){
cost[e.to]=cost[v]+e.cost;
que.push({-cost[e.to],e.to});
}
}
}
return cost;
}
struct S{
lint val;
int idx;
};
S op1(S l,S r){
if(l.val<=r.val)return l;
else return r;
}
S e1(){
return {INF64,-1};
}
S mapp1(lint f,S x){
x.val+=f;
return x;
}
lint comp1(lint f,lint g){
return f+g;
}
lint id1(){return 0;}
int main(){
lint N,K,D;cin>>N>>K>>D;
vec<lint>H(N);
rep(i,N)cin>>H[i];
map<lint,lint>mp1,mp2;
mp1[INF64]++;
mp1[-INF64]++;
rep(i,N){
mp1[H[i]]++;
mp1[H[i]+D]++;
mp1[H[i]-D]++;
}
vec<lint>inv(mp1.size());
int c=0;
for(auto p:mp1){
mp2[p.fi]=c;c++;
inv[c-1]=p.fi;
}
fenwick_tree<lint>fw(c),fwsum(c);
rep(i,K){
fw.add(mp2[H[i]],1);
fwsum.add(mp2[H[i]],H[i]);
}
lint ans=INF64;
rep(i,N-K+1){
lint upper=1e18;
lint lower=0;
while(upper>lower){
lint mid=(upper+lower+1)/2;
auto itu=mp2.upper_bound(mid+D);
auto itl=mp2.lower_bound(mid);
if(fw.sum(itu->se,c)-fw.sum(0,itl->se) >=0){
lower=mid;
}else{
upper=mid-1;
}
}
lower++;
lint L=lower;
auto itl=mp2.lower_bound(L);
lint t=fw.sum(0,itl->se)*L-fwsum.sum(0,itl->se);
auto it=mp2.upper_bound(L+D);
lint uc=it->se;
t += fwsum.sum(uc,c)-fw.sum(uc,c)*(D+L);
ans=min(ans,t);
//cerr<<L<<" "<<t<<endl;
if(i+K<N){
fw.add(mp2[H[i]],-1);
fw.add(mp2[H[i+K]],1);
fwsum.add(mp2[H[i]],-H[i]);
fwsum.add(mp2[H[i+K]],H[i+K]);
}
}
cout<<ans<<endl;
}