結果
問題 |
No.370 道路の掃除
|
ユーザー |
![]() |
提出日時 | 2016-05-13 23:59:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,219 bytes |
コンパイル時間 | 969 ms |
コンパイル使用メモリ | 101,684 KB |
実行使用メモリ | 174,112 KB |
最終ジャッジ日時 | 2024-10-05 18:40:34 |
合計ジャッジ時間 | 4,867 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 WA * 2 TLE * 1 -- * 18 |
ソースコード
//http://yukicoder.me/problems/780 #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <functional> #include <map> #include <set> #include <deque> #include <queue> #include <limits> #include <sstream> #include <typeinfo> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> D(M); for (int i = 0; i < M; i++) { cin >> D[i]; } sort(D.begin(), D.end()); int start = 1000000000; int cur = 0; for (int i = 0; i < M; i++) { if (start > abs(D[i])) { start = abs(D[i]); cur = i; } } typedef std::tuple<int, int, int, int, int> t; //(-ans, cur, left, right, rest) priority_queue<t> q; int ans = abs(D[cur]); q.push(make_tuple(-ans, cur, cur, cur, N - 1)); while (!q.empty()) { int rev_ans, left, right, rest; tie(rev_ans, cur, left, right, rest) = q.top(); q.pop(); ans = -rev_ans; if (rest == 0) break; if (left-1 >= 0) { int d = abs(D[left - 1] - D[cur]); q.push(make_tuple(rev_ans - d, left - 1, left - 1, right, rest - 1)); } if (right + 1 < M) { int d = abs(D[right + 1] - D[cur]); q.push(make_tuple(rev_ans - d, right + 1, left, right + 1, rest - 1)); } } cout << ans << endl; return 0; }