Submission #785420

#	Time	Username	Problem	Language	Result	Execution time	Memory
785420		makanhulia	Global Warming (CEOI18_glo)	C++17	0 / 100	2068 ms	3060 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main() {
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int a, b, mini = 1e9;
  cin >> a >> b;
  int arr[a + 5];
  vector<pair<int, int>> v;
  int pref[a + 5], PREF[a + 5];
  int suff[a + 5], SUFF[a + 5];
  for(int i = 1; i <= a; i++) {
    cin >> arr[i];
  }
  v.push_back({arr[1], 1});
  mini = arr[1];
  for(int i = 2; i <= a; i++) {
    if(arr[i] > arr[i - 1]) {
      int hmm = 0;
      for(int j = i - 1; j >= 1; j--) {
        if(arr[i] > arr[j]) {
          hmm = max(v[j - 1].second, hmm);
        }
      }
      v.push_back({arr[i], hmm + 1});
    } else {
      if(arr[i] <= mini) {
        v.push_back({arr[i], 1});
        mini = arr[i];
      } else {
        int hmm = 0;
        for(int j = i - 1; j >= 1; j--) {
          if(arr[i] > arr[j]) {
            hmm = max(v[j - 1].second, hmm);
          }
        }
        v.push_back({arr[i], hmm + 1});
      }
    }
  }
  
  vector<pair<int, int>> x;
  int maxi = -1e9;
  x.push_back({arr[a], 1});
  for(int i = a - 1; i >= 1; i--) {
    if(arr[i] < arr[i + 1]) {
      x.push_back({arr[i], x[a - i - 1].second + 1});
    } else {
      if(arr[i] >= maxi) {
        x.push_back({arr[i], 1});
      } else {
        int hmm = 0;
        for(int j = i + 1; j <= a; j--) {
          if(arr[i] < arr[j]) {
            hmm = max(v[j].second, hmm);
          }
        }
        x.push_back({arr[i], hmm + 1});
      }
    }
  }
  
  
  int jum = 0;
  for(int i = 1; i <= a; i++) {
    int heh = 0;
    for(int j = i + 1; j <= a; j++) {
      if(arr[j] > arr[i] - b) {
        heh = max(heh, x[a - j].second);
      }
    }
    cout << heh << "\n";
    jum = max(jum, v[i - 1].second + heh);
  }
  cout << jum << "\n";
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:12:7: warning: unused variable 'pref' [-Wunused-variable]
   12 |   int pref[a + 5], PREF[a + 5];
      |       ^~~~
glo.cpp:12:20: warning: unused variable 'PREF' [-Wunused-variable]
   12 |   int pref[a + 5], PREF[a + 5];
      |                    ^~~~
glo.cpp:13:7: warning: unused variable 'suff' [-Wunused-variable]
   13 |   int suff[a + 5], SUFF[a + 5];
      |       ^~~~
glo.cpp:13:20: warning: unused variable 'SUFF' [-Wunused-variable]
   13 |   int suff[a + 5], SUFF[a + 5];
      |                    ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25