結果
問題 | No.2539 スライムゲーム |
ユーザー |
![]() |
提出日時 | 2023-11-10 23:12:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,410 bytes |
コンパイル時間 | 3,531 ms |
コンパイル使用メモリ | 258,804 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-09-26 02:13:19 |
合計ジャッジ時間 | 4,522 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 WA * 22 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ vector<ll> ndp(1<<17,0); ndp[0] = 1; ndp[1] = 2; int no = -1; for(int i = 2;i<1<<17;i++){ ndp[i] = 2 * ndp[i-1] + 1; if(ndp[i]>1e18){ no = i; break; } } string s; cin>>s; ll ans = 0; int n = s.size(); vector<ll> need(n+1,0); stack<int> st; set<int> ss; bool ok = false; vector<ll> dp(n+1,0); for(int i = n-1;i>=0;i--){ if(s[i]==')'){ st.push(i); continue; } if(st.empty()){ ans += 1; break; } int ni = st.top(); st.pop(); if(ni==i+1){ dp[i] = 1; ss.insert(i); if(st.empty()) ans += dp[i]; ans = min(ans,(ll)2e18); continue; } ll sum = 0; while(ss.size()){ auto itr = ss.begin(); int nk = *itr; if(nk>ni) break; sum += dp[nk]; sum = min(sum,(ll)2e18); ss.erase(nk); } if(sum>=no){ dp[i] = 2e18; } if(sum<no) dp[i] = ndp[sum]; ss.insert(i); if(st.empty()) ans += dp[i]; ans = min(ans,(ll)2e18); } if(!st.empty()) ans++; if(ans<=1e18) cout<<ans<<endl; else cout<<"INFTY\n"; }