Submission #707355

#	Time	Username	Problem	Language	Result	Execution time	Memory
707355		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	25 ms	5964 KiB

triusis

#include <bits/stdc++.h>
using namespace std ;
#define int long long
#define all(a) a.begin(), a.end()
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n , m; cin >> n >> m;
    vector<int>a(n);
    for(int i = 0 ; i < n; i++)
        cin >> a[i];
	vector < int > ans;
	for(int i = 0 ; i < n ; i++){
        if(a[i] > (m * (i + 1))) continue;
        a[i] = (m * (i + 1)) - a[i];
		auto val = upper_bound(all(ans), a[i]);
		if(val == ans.end()) ans.push_back(a[i]);
		else *val = a[i];
	}
	cout << n - ans.size() << endl;
    return 0 ;
}
/*
    5 400
    300 700 200 1000 500
    lemma:
        mmkn ageb el answer bta3t el range elle msh m7tag a8yr feh 7aga
        b-keda a2dr ageb elle m7tag yt8yr
        ummm el sample msln m7tag m8yrsh {300, 700, 200, 500}
        keda 4th value heya elle htt8yr bs 
        hgeeb tle bardo keda O(n ^ 2), dp[idx][lst]
        msln a7sn array ll-Rabbit heya {m, 2m, 3m, ...}
        lw ana 3mlt el array blshkl da keda msln
        umm ohhhh ana mmkn a3ml el shkl da en ashoof kol element m7tag 2d eh 3ashan ywsl ll-view da 
        [100, 100, 1000, 600, 1500]
        a7sn range {100, 100, 1000, 15000}
        gbt el 7l lol
*/

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:10:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   10 |     for(int i = 0 ; i < n; i++)
      |     ^~~
triusis.cpp:12:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   12 |  vector < int > ans;
      |  ^~~~~~

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