Submission #499269

#	Time	Username	Problem	Language	Result	Execution time	Memory
499269		tphuc2908	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	31 ms	5356 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
#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 fi first
#define se second
#define ci(x) int x; cin >> x
#define cii(x,y) int x, y; cin >> x >> y
#define ciii(x,y,z) int x,y,z; cin >> x >> y >> z
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
//#define int long long
typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 23;
const ll inf = 1e18 + 5;

void read_file(){
    freopen("text.inp", "r", stdin);
//    freopen("SEARCHING.INP" , "r", stdin);
//    freopen("SEARCHING.OUT", "w", stdout);
}

/*
    dp[bit][i] is the minimal time to get at i with i is in the subset bit
    then we will binary search the initial velocity
    as time = d1 / v1 + d2 / (v2 *m) + ... + dn / (vn * m^(n-1))
    so if we increase or decrease v, time will decrease or increase
*/

int n, m;
ll h[N];

void inp(){
    cin >> n >> m;
    h[0] = (1ll)*n*m;
    rep(i,1,n){
        ci(x);
        h[i] += (1ll)*(n-i)*m + x;
    }
}

ll dp[N];

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

int main()
{
    //read_file();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    inp();
    process();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37