結果
問題 |
No.3210 Fixed Sign Sequense
|
ユーザー |
![]() |
提出日時 | 2025-07-25 21:36:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 2,342 bytes |
コンパイル時間 | 3,513 ms |
コンパイル使用メモリ | 280,456 KB |
実行使用メモリ | 9,296 KB |
最終ジャッジ日時 | 2025-07-25 21:36:26 |
合計ジャッジ時間 | 5,364 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
main.cpp: In function ‘std::vector<int> LIS(const std::vector<int>&)’: main.cpp:76:16: warning: ‘cur’ may be used uninitialized [-Wmaybe-uninitialized] 76 | while (cur != INT_MIN) { | ^ main.cpp:68:9: note: ‘cur’ was declared here 68 | int cur; | ^~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define For(i, a, b) for(int i = (a); i < (b); i++) #define rep(i, n) For(i, 0, n) #define rFor(i, a, b) for(int i = (a); i >= (b); i--) #define ALL(v) (v).begin(), (v).end() #define rALL(v) (v).rbegin(), (v).rend() #define SZ(v) ((int)(v).size()) using lint = long long; using ld = long double; const int INF = 2000000000; const lint LINF = 1000000000000000000; // 真上から反時計回り const int di[] = {-1, 0, 1, 0}; const int dj[] = {0, -1, 0, 1}; const int di8[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dj8[] = {0, -1, -1, -1, 0, 1, 1, 1}; struct SetupIo { SetupIo() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } setupio; template <class T> bool chmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template <class T> bool chmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <class T> T mypow(T a, T b) { T res = 1; while (b) { if (b & 1) { res *= a; } a *= a; b >>= 1; } return res; } template <class T> T modpow(T a, T b, T mod) { T res = 1; while (b) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } vector<int> LIS(const vector<int> &a) { int n = a.size(); vector<int> dp(n + 1, INT_MAX), prev(n); dp[0] = INT_MIN; for (int i = 0; i < n; i++) { int len = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); prev[i] = dp[len - 1]; dp[len] = min(dp[len], a[i]); } vector<int> lis; int cur; for (int i = n; i >= 0; i--) { if (dp[i] != INT_MAX) { cur = dp[i]; break; } } int i = n - 1; while (cur != INT_MIN) { if (a[i] == cur) { lis.emplace_back(cur); cur = prev[i]; } i--; } reverse(lis.begin(), lis.end()); return lis; } int main() { int N; string S; cin >> N >> S; int posi = 1, nega = -INF; vector<int> A(N); rep(i, N) { if (S[i] == '-') { A[i] = nega; nega++; } else if (S[i] == '0') { A[i] = 0; } else { A[i] = posi; posi++; } } cout << SZ(LIS(A)) << "\n"; }