oj.uz

답안 #395817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395817 2021-04-29T02:19:56 Z Pichon5 Global Warming (CEOI18_glo) C++17
0 / 100
 124 ms 3336 KB 
#include <bits/stdc++.h>
using namespace std;

int temps[200005];
int pref_longest[200005];

int main() {
	int n;
	int x;
	cin >> n >> x;
	for (int i = 0; i < n; i++) {
		cin >> temps[i];
	}

	vector<int> dp(n, INT_MAX);
	int longest = 0;
	// longest increasing subsequence ending at i
	for (int i = 0; i < n; i++) {
		int j = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin();
		//j+1 es el tamaño del lis que termina en v[i] 
        dp[j] = temps[i];
		pref_longest[i] = j + 1;//el lis que termina en i
		longest = max(longest, pref_longest[i]);
	}

	dp = vector<int>(n, INT_MAX);
	// longest decreasing subsequence ending at i of reverse
	// = longest increasing subsequence starting at i
	for (int i = n - 1; i >= 0; i--) {
		int pos = lower_bound(dp.begin(), dp.end(), temps[i] + x)-dp.begin();
		longest = max(longest, pref_longest[i] + pos);
        //cout<<"pos  "<<pos<<" +  "<<pref_longest[i]<<endl;
		int insert_pos = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin();
		dp[insert_pos] = temps[i];
	}
	cout << longest << endl;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 3336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 1836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -