제출 #654118

#제출 시각아이디문제언어결과실행 시간메모리
654118aebovFinancial Report (JOI21_financial)C++17
28 / 100
37 ms964 KiB
#include<iostream> #include<algorithm> #include<vector> #include<utility> #define ll long long #define F first #define S second #define pll pair<ll , ll> #define pii pair<int, int> #define pb push_back using namespace std; const int N = 402, inf = (int)1e9 + 7; int n, d, a[N]; int dp[N][N]; vector<int> vct; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> d; for(int i = 1; i <= n; i ++) cin >> a[i], vct.pb(a[i]); sort(vct.begin(), vct.end()); unique( vct.begin(), vct.end()); for(int i = 1; i <= n; i ++){ a[i] = (lower_bound(vct.begin(), vct.end(), a[i]) - vct.begin()); // cout << a[i] << " ";//endl; }//cout << endl; for(int i = 0; i <= n; i ++)fill(dp[i], dp[i] + N, -inf); dp[1][a[1]] = 1; for(int i = 2; i <= n; i ++){ dp[i][a[i]] = 1; for(int k = 0 ; k < a[i]; k ++) for(int j = max(1, i-d); j < i; j ++)dp[i][a[i]] = max(dp[i][a[i]] , dp[j][k] + 1); for(int k = a[i]; k <= n; k ++) for(int j = max(1 ,i-d); j < i; j ++)dp[i][k] = max(dp[i][k], dp[j][k]); // for(int j = 0 ; j <= n; j ++)cout << i << " " << j << " : " <<max(0, dp[i][j]) << endl; } int ret = 0; for(int i = 0; i <= n; i ++)ret = max(ret, dp[n][i]); cout << ret << endl; }
#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...