oj.uz

Submission #994816

# Submission time Handle Problem Language Result Execution time Memory
994816 2024-06-08T06:43:23 Z debargha Global Warming (CEOI18_glo) C++14
0 / 100
 39 ms 262144 KB 
//JAI SHREE RAM
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 1e18
#define MAXN 1123456
#define MOD 1000000007
/*
-----------------------------ordered set--------------------
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
#include <iostream>  
using namespace __gnu_pbds;  
using namespace std;  

typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update>  
    ordered_set;  
*/  
/*-----------------PRIME FACTOR-------------
for (int i = 2; i*i <= n; i = i+2)
    {
        // While i divides n, print i and divide n
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }
*/
/*-----------------------sieve----------------
vector<bool> prime(MAXN, false);
vector<bool> used(MAXN, false);
void precalc() {
    for (int i = 2; i < MAXN; ++i) {
        if (!   used[i]) {
            prime[i] = true;
            for (int j = i; j < MAXN; j += i) {
                used[j] = true;
            }
        }
    }
}*/
/*--------------------------------sqrt function------------------------
ll my_sqrt(ll a)
{
    ll l=0,r=5000000001;
    while(r-l>1)
    {
        ll mid=(l+r)/2;
        if(1ll*mid*mid<=a)l=mid;
        else r=mid;
    }
    return l;
}
int getclosest(int x)
{
    int n = sqrt(x);
    if(n*n==x)
    {
        return 0;
    }
    else
    {
        return (n+1)*(n+1) - x;
    }
}

const int N = 40004;
const int M = 502;
int dp[N][M];

int reverse(int n) {
    int r = 0;
    while (n > 0) {
        r = r * 10 + n % 10;
        n = n / 10;
    }
    return r;
}

int palindrome(int i) {
    return reverse(i) == i;
}

void precompute_palindromes(vector<int>& palin) {
    palin.push_back(0);
    for (int i = 1; i < 2 * N; i++) {
        if (palindrome(i)) {
            palin.push_back(i);
        }
    }
}
*/
void solve() 
{
    int x,n;
    cin>>x>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    vector<int>dp(n,INT_MAX);
    vector<int>pref(n);
    int len = 0;
    for(int i=0;i<n;i++)
    {
        int pos = lower_bound(dp.begin(),dp.end(),v[i])-dp.begin();
        dp[pos] = v[i];
        pref[i] = pos+1;
        len = max(len,pref[i]);
    }
    dp = vector<int>(n,INT_MAX);
    for(int i=n-1;i>=0;i--)
    {
        int pos = lower_bound(dp.begin(),dp.end(),-v[i]+x)-dp.begin();
        len = max(len,pref[i]+pos);
        int insert = lower_bound(dp.begin(),dp.end(),-v[i])-dp.begin();
        dp[insert] = -v[i];
    }
    cout<<len<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t=1;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -