結果

問題 No.3049 Contest Coordinator
ユーザー NakLon131
提出日時 2025-03-08 00:16:26
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,611 bytes
コンパイル時間 13,380 ms
コンパイル使用メモリ 401,860 KB
実行使用メモリ 20,912 KB
最終ジャッジ日時 2025-03-08 00:16:45
合計ジャッジ時間 19,609 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 14 WA * 44
権限があれば一括ダウンロードができます

ソースコード

diff #

fn main() {
    input!{
		n: usize, t: i64, x: i64, y: i64,
		mut d: [i64; n],
	}
	// dは昇順にする
	d.sort();
	
	// 階差を取る
	let mut diff_d = Vec::new();
	for i in 0..n-1 {
		diff_d.push(d[i+1] - d[i]);
	}

	// 順番に見て階差がt以上の個数を数える
	let mut upper_cnt = 0;
	for i in 0..n-1 {
		if diff_d[i] > t { upper_cnt += 1;}
	}
	
	// 順番を入れ替えることで、1->2に交換していき、minを得る
	let mut ret = upper_cnt * x;
	let mut pq = (upper_cnt, 0);
	for i in (0..upper_cnt).rev() {
		if ret > i * x + (upper_cnt - i) * y {
			ret = i * x + (upper_cnt - i) * y;
			pq = (i, upper_cnt - i);
		}
	}

	let mut ans = Vec::new();
	for _i in 0..n-1 {
		ans.push(pq.0 * x + pq.1 * y);
		
		// 1個ずつ取り出す
		if x > y {	
			if pq.0 > 0 { pq.0 -= 1;}
			else if pq.1 > 0 { pq.1 -= 1;}
		}
		else {
			if pq.1 > 0 { pq.1 -= 1;}
			else if pq.0 > 0 { pq.0 -= 1;}
		}
	}
	ans.push(0);
	ans.reverse();

	for i in 0..n-1 {
		print!("{} ", ans[i]);
	}
	println!("{}", ans[n-1]);
}

// const MOD17: usize = 1000000007;
// const MOD93: usize = 998244353;
// const INF: usize = 1 << 60;
// let dx = vec![!0, 0, 1, 0]; // 上左下右
// let dy = vec![0, !0, 0, 1]; // 上左下右
// let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右

#[allow(unused)]
use proconio::{input, marker::Chars, marker::Usize1};

#[allow(unused)]
use std::{
	mem::swap,
	cmp::min, cmp::max,
	cmp::Reverse,
	collections::HashSet, collections::BTreeSet,
	collections::HashMap, collections::BTreeMap,
	collections::BinaryHeap,
	collections::VecDeque,
	iter::FromIterator,
};
0