結果
問題 | No.838 Noelちゃんと星々3 |
ユーザー |
|
提出日時 | 2019-06-14 21:57:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 482 bytes |
コンパイル時間 | 1,638 ms |
コンパイル使用メモリ | 169,424 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 05:40:52 |
合計ジャッジ時間 | 2,986 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; void chmin(int64_t& a, int64_t b){ a = min(a, b); } int main(){ int N; int64_t A[100000]; cin >> N; for(int i=0; i<N; i++) cin >> A[i]; sort(A, A+N); int64_t dp[100001] = {0}; for(int i=1; i<=N; i++) dp[i] = 1e18; for(int i=0; i<N-1; i++){ chmin(dp[i+2], dp[i] + A[i+1] - A[i]); if(i+3 <= N) chmin(dp[i+3], dp[i] + A[i+2] - A[i]); } cout << dp[N] << endl; return 0; }