Submission #1003826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003826		MonoLith	Global Warming (CEOI18_glo)	C++17	28 / 100	2072 ms	5468 KiB

glo

/*
   ॐ नमो भगवते वासुदेवाय नमः
   ॐ भूर्भुव: स्व: तत्सवितुर्वरेण्यं भर्गो देवस्य धीमहि धियो यो न: प्रचोदयात्।
*/
// all hail Infront of almighty lord krishna (jai shri krishna ji)
  #include<bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp>
  #include <ext/pb_ds/tree_policy.hpp>
  using namespace std;
  using namespace __gnu_pbds;
  #define int long long 
  const long long INF =1e18;
  template<class T>
  using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
  template<typename T> 
  using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
  const int N=1e5 + 10;
  const int mod = 998244353;  

  void Solve()
  {
    int n,x;
    cin>>n>>x;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
    }
    vector<int>inc(n,1);
    int ans=0;
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<i;j++)
      {
        if(a[j]<a[i])
        {
          inc[i]=max(inc[i],inc[j]+1);
        }
      }
      ans=max(ans,inc[i]);
    }
    vector<int>dec(n,1);
    for(int i=n-1;i>=0;i--)
    {
      for(int j=n-1;j>i;j--)
      {
        if(a[i]<a[j])
        {
          dec[i]=max(dec[i],dec[j]+1);
        }
      }
    }
    if(x==0)
    {
      cout<<ans<<"\n";
      return ;
    }
    // deb(inc);
    // deb(dec);
    // deb(ans);
    for(int i=n-1;i>=0;i--)
    {
      for(int j=i-1;j>=0;j--)
      {
         if(a[j]<a[i]+x)
         {
          ans=max(ans,inc[j]+dec[i]);
         }
      }
    }
    cout<<ans<<"\n";
  }

  signed main()
  { 
    
      auto begin = std::chrono::high_resolution_clock::now();
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout<<fixed;
      int t = 1;
      // cin >> t;

      for(int i = 1; i <= t; i++) 
      {
          // cout << "Case #" << i << ": ";
          Solve();
 
      }
      auto end = std::chrono::high_resolution_clock::now();
      auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
      // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
      return 0;       
  }

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