結果
問題 | No.1268 Fruit Rush 2 |
ユーザー |
![]() |
提出日時 | 2020-10-23 23:35:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,307 bytes |
コンパイル時間 | 917 ms |
コンパイル使用メモリ | 89,024 KB |
実行使用メモリ | 8,956 KB |
最終ジャッジ日時 | 2024-07-21 13:31:00 |
合計ジャッジ時間 | 3,025 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; int n; ll a[200000]; void input(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; } void solve(){ sort(a, a+n); ll ans = 0; int cnt = 0; vector<ll> dp; dp.push_back(1); for(int i = 1; i < n; i++){ int sz = dp.size(); if(a[i-1]+1 == a[i]){ if(sz <= 1) dp.push_back(1); else dp.push_back(dp[sz-2]+1); }else if(a[i-1]+2 == a[i]){ if(sz == 1) { ans += dp[0]; dp.clear(); dp.push_back(1); }else if(sz >= 2){ dp.push_back(dp[sz-2]); dp.push_back(1); } }else{ for(ll x : dp) ans += x; if(dp.size() >= 2) ans += dp[sz-2]; dp.clear(); dp.push_back(1); } } // cout << ans << endl; // for(ll x : dp) cout << x << ' '; // cout << endl; for(ll x : dp) ans += x; if(dp.size() >= 2) ans += dp[dp.size()-2]; cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; input(); solve(); }