Submission #992115

#	Time	Username	Problem	Language	Result	Execution time	Memory
992115		kkzyr	Global Warming (CEOI18_glo)	C++17	28 / 100	2058 ms	4432 KiB

glo

#include <iostream>
using namespace std;

int n, x;
int nums[200001];
int copy_array[200001];
int lis[200001];

const int INF = 1e9 + 5;

int binary_search(int key){
    int lo = 1;
    int hi = n;
    int ans = 0;
    while (lo <= hi){
        int mid = (lo + hi)/2;
        if (lis[mid] < key){
            ans = mid;
            lo = mid + 1;
        }
        else{
            hi = mid - 1;
        }
    }
    return ans;
}

int main(){
    cin >> n >> x;
    for (int i = 1;i <= n;i++){
        cin >> nums[i];
    }
    int ans = 0;
    for (int i = 0;i <= n;i++){
        for (int j = 1;j <= n;j++){
            copy_array[j] = nums[j];
        }
        for (int j = 1;j <= i;j++){
            copy_array[j] -= x;
        }
        for (int j = 1;j <= n;j++){
            lis[j] = INF;
        }
        for (int j = 1;j <= n;j++){
            int key = copy_array[j];
            int index = binary_search(key);
            lis[index + 1] = copy_array[j];
        }
        int curr_ans = 0;
        for (int j = 1;j <= n;j++){
            if (lis[j] != INF){
                curr_ans = j;
            }
        }
        if (curr_ans > ans){
            ans = curr_ans;
        }
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25