제출 #771139

#제출 시각아이디문제언어결과실행 시간메모리
771139davitmargFinancial Report (JOI21_financial)C++17
0 / 100
4075 ms4688 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <random> #include <chrono> #define mod 998244353ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N = 500005; int n, d; int a[N]; void norm() { vector<pair<int, int>> v; v.push_back(MP(-1, 0)); for (int i = 1; i <= n; i++) v.push_back(MP(a[i], i)); sort(all(v)); for (int i = 1; i <= n; i++) if (v[i].first == v[i - 1].first) a[v[i].second] = a[v[i - 1].second]; else a[v[i].second] = 1 + a[v[i - 1].second]; } int dp[N], lst[N]; int stress_solve() { int best = 0; for (int mask = 0; mask < (1 << n); mask++) { vector<int> v; for (int i = 0; i < n; i++) { if(((1 << i) & mask) == 0) continue; v.push_back(i + 1); } int mx = -mod; int res = 0; for (int i = 0; i < v.size(); i++) { if (a[v[i]] > mx) { mx = a[v[i]]; res++; } if (i && v[i] - v[i - 1] > d) { res = 0; break; } } best = max(best, res); } return best; } void solve() { cin >> n >> d; for (int i = 1; i <= n; i++) cin >> a[i]; // norm(); vector<int> st; st.push_back(0); a[0] = -1; lst[0] = 1; for (int i = 1; i <= n; i++) { lst[i] = max(1, i - d); while (a[st.back()] > a[i]) st.pop_back(); if(i - st.back() <= d) lst[i] = lst[st.back()]; st.push_back(i); } for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = i - 1; j >= lst[i]; j--) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); } int ans = 1; for(int i = 1; i <= n; i++) ans = max(ans, dp[i]); cout << ans << endl; } int main() { fastIO; int T = 1; //cin >> T; while (T--) { solve(); } return 0; } /* 7 1 1 4 4 5 3 2 1 */

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int stress_solve()':
Main.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < v.size(); i++)
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...