oj.uz

Submission #483606

# Submission time Handle Problem Language Result Execution time Memory
483606 2021-10-31T05:06:21 Z tphuc2908 Rabbit Carrot (LMIO19_triusis) C++14
0 / 100
 3 ms 332 KB 
#include<bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31, pii = 29, piii = 41;
const ll inf = 2e18 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("cowjog.in", "r", stdin);
//    freopen("cowjog.out", "w", stdout);
}

int n, m;
ll a[N];

void inp(){
    cin >> n >> m;
    rep(i,1,n){
        cin >> a[i];
        a[i] -= (1ll)*i*m;
    }
}

ll dp[N];

void process(){
    dp[0] = -inf;
    rep(i,1,n+1)
        dp[i] = inf;
    repi(i,n,0){
        if(a[i] > 0) continue;
        int pos = upper_bound(dp + 1, dp + n + 1, a[i]) - dp;
        dp[pos] = a[i];
    }
    repi(i,n+1,0)
        if(dp[i]!=inf){
            cout << n - i + 1;
            return;
        }
}

int main() {
    readfile();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    TC(t){
        inp();
        process();
//    }
    return 0;
}

Compilation message

triusis.cpp: In function 'void readfile()':
triusis.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 37.0

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