Submission #785364

#	Time	Username	Problem	Language	Result	Execution time	Memory
785364		christinelynn	Global Warming (CEOI18_glo)	C++17	25 / 100	2091 ms	2988 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;

ll n, x, arr[MAXN], ans = 0;

void update(ll l, ll r, ll x) {
  for (int i = l; i <= r; ++i)
  {
    arr[i] += x;
  }
} 

ll lis() {
  vector<ll> nowvec;
  for (int i = 1; i <= n; ++i)
  {
    ll now = arr[i];
    ll idx = lower_bound(nowvec.begin(), nowvec.end(), now) - nowvec.begin();
    if (idx == nowvec.size()) {
      nowvec.push_back(now);
    } else {
      nowvec[idx] = now;
    }
  }

  return nowvec.size();
}

int main(){
  cin >> n >> x;
  for (int i = 1; i <= n; ++i)
  {
    cin >> arr[i];    
  }

  ans = lis();

  if (x == 0)
  {
    cout << ans << "\n";
    return 0;
  }

  for (int i = 1; i <= n; ++i)
  {
    for (int j = i; j <= n; ++j)
    {
      for (int k = -x; k <= x; ++k)
      {
        update(i, j, k);
        ans = max(ans, lis());
        update(i, j, -k);
      }
    }
  }

  cout << ans << "\n";
  return 0;
}

Compilation message (stderr)

glo.cpp: In function 'll lis()':
glo.cpp:21:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (idx == nowvec.size()) {
      |         ~~~~^~~~~~~~~~~~~~~~

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