답안 #548299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548299	2022-04-13T00:33:18 Z	PikaQ	Rabbit Carrot (LMIO19_triusis)	C++17	63 / 100	1000 ms	20652 KB

triusis

#include<bits/stdc++.h>
#define int ll
#define forn(i,n) for(int i=0;i<(n);i++)
#define Forn(i,n) for(int i=1;i<=(n);i++)
#define ll long long
#define pb push_back
#define F first
#define S second
#define vi vector<long long>
#define pii pair<int,int>
#define all(p) p.begin(),p.end()
#define st0(p) memset((p),0,sizeof(p))
#define sz(x) (x).size()
#define rz resize
using namespace std;

 
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
 
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cerr << a << " "; debug(b...);}
const int N = (int) 2e6+9;
const int INF = (int) 1e9 + 7;
int n,k;
struct FenwickTree{
	int t[N];
	void init(){
		for(auto &i : t) i = -INF;
	}
	void modify(int p,int v){
		for(;p <= n+1;p++){
			t[p] = max(t[p],v);
		}
	}
	int query(int p){
		int res = -INF;
		for(;p;p-=(p&-p)) res = max(res,t[p]);
		return res;
	}
}bit;
void solve(){	
	cin >> n >> k;
	vi a(n);
	forn(i,n) cin >> a[i];
	for(int i = 1;i <= n;i++){
		a[i-1] -= k * i;
		a[i-1] *= -1;
	}
	vi dp(n);
	vi rk = a;
	rk.pb(0);
	sort(all(rk));
	rk.resize(unique(all(rk)) - rk.begin());
	forn(i,n){
		a[i] = upper_bound(all(rk),a[i]) - rk.begin();
	}
	bit.init();
	bit.modify(upper_bound(all(rk),0)-rk.begin(),0);
	forn(i,n){
		dp[i] = bit.query(a[i]) + 1;
		bit.modify(a[i],dp[i]);
	}
	cout << n - bit.query(n+1) << '\n';
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	7 ms	15956 KB	Output is correct
3	Correct	7 ms	15956 KB	Output is correct
4	Correct	7 ms	15856 KB	Output is correct
5	Correct	7 ms	15956 KB	Output is correct
6	Correct	7 ms	15956 KB	Output is correct
7	Correct	7 ms	15956 KB	Output is correct
8	Correct	7 ms	15876 KB	Output is correct
9	Correct	7 ms	15956 KB	Output is correct
10	Correct	7 ms	15936 KB	Output is correct
11	Correct	6 ms	15956 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	6 ms	15956 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	8 ms	15940 KB	Output is correct
16	Correct	6 ms	15872 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	7 ms	15956 KB	Output is correct
3	Correct	7 ms	15956 KB	Output is correct
4	Correct	7 ms	15856 KB	Output is correct
5	Correct	7 ms	15956 KB	Output is correct
6	Correct	7 ms	15956 KB	Output is correct
7	Correct	7 ms	15956 KB	Output is correct
8	Correct	7 ms	15876 KB	Output is correct
9	Correct	7 ms	15956 KB	Output is correct
10	Correct	7 ms	15936 KB	Output is correct
11	Correct	6 ms	15956 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	6 ms	15956 KB	Output is correct
14	Correct	7 ms	15956 KB	Output is correct
15	Correct	8 ms	15940 KB	Output is correct
16	Correct	6 ms	15872 KB	Output is correct
17	Correct	7 ms	15956 KB	Output is correct
18	Correct	7 ms	15956 KB	Output is correct
19	Correct	7 ms	15956 KB	Output is correct
20	Correct	15 ms	16104 KB	Output is correct
21	Correct	17 ms	16012 KB	Output is correct
22	Correct	21 ms	16036 KB	Output is correct
23	Correct	18 ms	16132 KB	Output is correct
24	Correct	19 ms	16212 KB	Output is correct
25	Correct	18 ms	16104 KB	Output is correct
26	Correct	19 ms	16104 KB	Output is correct
27	Correct	28 ms	16136 KB	Output is correct
28	Correct	27 ms	16084 KB	Output is correct
29	Correct	18 ms	16104 KB	Output is correct
30	Correct	17 ms	16084 KB	Output is correct
31	Correct	25 ms	16124 KB	Output is correct
32	Correct	17 ms	16084 KB	Output is correct
33	Correct	18 ms	16084 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	7 ms	15956 KB	Output is correct
3	Correct	7 ms	15956 KB	Output is correct
4	Correct	15 ms	16104 KB	Output is correct
5	Correct	17 ms	16012 KB	Output is correct
6	Correct	21 ms	16036 KB	Output is correct
7	Correct	18 ms	16132 KB	Output is correct
8	Correct	19 ms	16212 KB	Output is correct
9	Correct	18 ms	16104 KB	Output is correct
10	Correct	19 ms	16104 KB	Output is correct
11	Correct	28 ms	16136 KB	Output is correct
12	Correct	27 ms	16084 KB	Output is correct
13	Correct	18 ms	16104 KB	Output is correct
14	Correct	17 ms	16084 KB	Output is correct
15	Correct	25 ms	16124 KB	Output is correct
16	Correct	17 ms	16084 KB	Output is correct
17	Correct	18 ms	16084 KB	Output is correct
18	Correct	7 ms	15956 KB	Output is correct
19	Correct	7 ms	15956 KB	Output is correct
20	Correct	7 ms	15956 KB	Output is correct
21	Correct	7 ms	15856 KB	Output is correct
22	Correct	7 ms	15956 KB	Output is correct
23	Correct	7 ms	15956 KB	Output is correct
24	Correct	7 ms	15956 KB	Output is correct
25	Correct	7 ms	15876 KB	Output is correct
26	Correct	7 ms	15956 KB	Output is correct
27	Correct	7 ms	15936 KB	Output is correct
28	Correct	6 ms	15956 KB	Output is correct
29	Correct	7 ms	15956 KB	Output is correct
30	Correct	6 ms	15956 KB	Output is correct
31	Correct	7 ms	15956 KB	Output is correct
32	Correct	8 ms	15940 KB	Output is correct
33	Correct	6 ms	15872 KB	Output is correct
34	Correct	18 ms	16084 KB	Output is correct
35	Correct	18 ms	16100 KB	Output is correct
36	Correct	18 ms	16084 KB	Output is correct
37	Correct	18 ms	16084 KB	Output is correct
38	Correct	31 ms	16084 KB	Output is correct
39	Correct	27 ms	16140 KB	Output is correct
40	Correct	25 ms	16104 KB	Output is correct
41	Correct	27 ms	16084 KB	Output is correct
42	Correct	19 ms	16108 KB	Output is correct
43	Correct	18 ms	16084 KB	Output is correct

Subtask #4
0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	16084 KB	Output is correct
2	Correct	18 ms	16100 KB	Output is correct
3	Correct	18 ms	16084 KB	Output is correct
4	Correct	18 ms	16084 KB	Output is correct
5	Correct	31 ms	16084 KB	Output is correct
6	Correct	27 ms	16140 KB	Output is correct
7	Correct	25 ms	16104 KB	Output is correct
8	Correct	27 ms	16084 KB	Output is correct
9	Correct	19 ms	16108 KB	Output is correct
10	Correct	18 ms	16084 KB	Output is correct
11	Correct	7 ms	15956 KB	Output is correct
12	Correct	7 ms	15956 KB	Output is correct
13	Correct	7 ms	15956 KB	Output is correct
14	Correct	15 ms	16104 KB	Output is correct
15	Correct	17 ms	16012 KB	Output is correct
16	Correct	21 ms	16036 KB	Output is correct
17	Correct	18 ms	16132 KB	Output is correct
18	Correct	19 ms	16212 KB	Output is correct
19	Correct	18 ms	16104 KB	Output is correct
20	Correct	19 ms	16104 KB	Output is correct
21	Correct	28 ms	16136 KB	Output is correct
22	Correct	27 ms	16084 KB	Output is correct
23	Correct	18 ms	16104 KB	Output is correct
24	Correct	17 ms	16084 KB	Output is correct
25	Correct	25 ms	16124 KB	Output is correct
26	Correct	17 ms	16084 KB	Output is correct
27	Correct	18 ms	16084 KB	Output is correct
28	Correct	7 ms	15956 KB	Output is correct
29	Correct	7 ms	15956 KB	Output is correct
30	Correct	7 ms	15956 KB	Output is correct
31	Correct	7 ms	15856 KB	Output is correct
32	Correct	7 ms	15956 KB	Output is correct
33	Correct	7 ms	15956 KB	Output is correct
34	Correct	7 ms	15956 KB	Output is correct
35	Correct	7 ms	15876 KB	Output is correct
36	Correct	7 ms	15956 KB	Output is correct
37	Correct	7 ms	15936 KB	Output is correct
38	Correct	6 ms	15956 KB	Output is correct
39	Correct	7 ms	15956 KB	Output is correct
40	Correct	6 ms	15956 KB	Output is correct
41	Correct	7 ms	15956 KB	Output is correct
42	Correct	8 ms	15940 KB	Output is correct
43	Correct	6 ms	15872 KB	Output is correct
44	Execution timed out	1086 ms	20652 KB	Time limit exceeded
45	Halted	0 ms	0 KB	-

답안 #548299

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 21.0 / 21.0

Subtask #3 28.0 / 28.0

Subtask #4 0 / 37.0

Subtask #1
14.0 / 14.0

Subtask #2
21.0 / 21.0

Subtask #3
28.0 / 28.0

Subtask #4
0 / 37.0