제출 #620029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
620029		CoolRabbitXT	Financial Report (JOI21_financial)	C++14	0 / 100	610 ms	1048576 KiB

Main

/*#include <bits/stdc++.h>
using namespace std;
int n, d;
vector <int> arr;
int current_max;
vector <int> selected;

int solve(int indx, int maxi){
  vector <int> options;
  int max_options;
  options.resize(d+5);
  int condition;


  int the_max = 0;
  if(indx == n) {
    if(arr[indx] > maxi) return 1;
    else return 0;
  }


  for(int i = 1; i<= d; i++){
    if(indx + i >= n) break;
    else{
      if(arr[indx+i] > maxi){
        condition = 1;
        the_max = arr[indx+i];
      }
      else {
        the_max = maxi;
        condition = 0;
      }

      options[i] = solve(indx + i, the_max) + condition;
    }
  }
  max_options = 0;
  for(int i = 1; i <=d; i++){
    if(options[i] > max_options) max_options = options[i];
  }
  return selected[indx] = max_options;
}



int main(){
  cin >> n >> d;
  arr.resize(n);
  selected.resize(n);

  for(int i = 0; i<n; i++){
    cin >> arr[i];
    selected[i] = -1;
  }
  solve(0, arr[0]);
  for(int i = 0; i<n; i++){
    //cout << "for indx: " << i << ": " << solve(i, arr[i]) << endl;
    if(selected[i] > current_max) {
      current_max = selected[i];
    }


  }
  cout << current_max +1;
  for(int i = 0; i<n; i++){
    cout << selected[i] + 1<< " ";
  }
}
*/
#include <bits/stdc++.h>
using namespace std;
int n, d;
vector <int> arr;
int current_max;

const int N = 7010;

int dp[N][N];

int solve(int indx, int mx){
  int maxi = arr[mx];
  vector <int> options;
  int max_options;
  options.resize(d+5);
  int condition;


  int the_max = 0;
  if(indx == n) {
    if(arr[indx] > maxi) return 1;
    else return 0;
  }
  if (dp[indx][mx]!=-1)return dp[indx][mx];

  for(int i = 1; i<= d; i++){
    if(indx + i >= n) break;
    else{
      if(arr[indx+i] > maxi){
        condition = 1;
        the_max = indx+i;
      }
      else {
        the_max = mx;
        condition = 0;
      }

      options[i] = solve(indx + i, the_max) + condition;
    }
  }
  max_options = 0;
  for(int i = 1; i <=d; i++){
    if(options[i] > max_options) max_options = options[i];
  }
  return dp[indx][mx]=max_options;
}



int main(){
  cin >> n >> d;
  arr.resize(n);
  memset(dp,-1,sizeof dp);
  for(int i = 0; i<n; i++){
    cin >> arr[i];
  }
  for(int i = 0; i<n; i++){
    //cout << "for indx: " << i << ": " << solve(i, arr[i]) << endl;
    if(solve(i, i) > current_max) {
      current_max = solve(i, arr[i]);

    }

  }
  cout << current_max + 1;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35