結果
問題 |
No.615 集合に分けよう
|
ユーザー |
![]() |
提出日時 | 2017-12-15 23:54:55 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,096 bytes |
コンパイル時間 | 858 ms |
コンパイル使用メモリ | 118,832 KB |
実行使用メモリ | 12,384 KB |
最終ジャッジ日時 | 2024-06-12 23:08:58 |
合計ジャッジ時間 | 2,247 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 26 |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; import std.typecons; int n, k; rd(n, k); auto a=readln.split.to!(long[]); sort(a); alias T=Tuple!(long, "d", int, "i"); auto dif=new T[](n-1); foreach(i; 0..(n-1)) dif[i]=T(a[i+1]-a[i], i); sort!((x, y)=>(x.d<y.d))(dif); auto g=new int[][](n, 0); foreach(i; 0..(n-k)){ auto e=dif[i]; g[e.i]~=(e.i+1); g[e.i+1]~=e.i; } auto vis=new bool[](n); Tuple!(long, long) min_max(int i, int pre){ vis[i]=true; auto mn=a[i], mx=a[i]; foreach(j; g[i])if(j!=pre){ auto res=min_max(j, i); mn=min(mn, res[0]); mx=max(mx, res[1]); } return tuple(mn, mx); } long tot=0; foreach(i; 0..n)if(vis[i]==false){ auto res=min_max(i, -1); tot+=(res[1]-res[0]); } writeln(tot); } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; assert(l.length==x.length); foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } } void wr(T...)(T x){ import std.stdio; foreach(e; x) stderr.write(e, " "); stderr.writeln(); }