Submission #454860

#	Time	Username	Problem	Language	Result	Execution time	Memory
454860		Yuisuyuno	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	42 ms	6980 KiB

triusis

//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 200005
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, m;
int a[N];
int b[N];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >>n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        b[i] = m*i - a[i];
    }
}

/*
    thay vì tìm min các cột cần thay đổi thì ta có thể tìm
    max các cột không cần thay đổi
    giả sử các cột đấy có vị trí i1, i2, ..., ik
    ->  a[i1] <= m*i1
        a[i2] <= a[i1] + m*(i2-i1)
        ...
    bất pt ở trên có thể viết lại như sau:
        m*i1 - a[i1] >= 0
        m*i2 - a[i2] >= m*i1 - a[i1]
        ...
    -> ta chỉ cần tìm dãy con không giảm dài nhất trên mảng b[i] = m*i - a[i]
*/

void proc()
{
    vector<int> c(n+1,inf);
    c[0] = minf;
    int ans = 0;
    for(int i=1; i<=n; i++){
        if (b[i]<0) continue;
        int k = upper_bound(c.begin(),c.end(),b[i])-c.begin();
        ans = max(ans,k);
        c[k] = b[i];
    }
    cout << n-ans;
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message (stderr)

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

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