제출 #1308211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308211		xnoel	Global Warming (CEOI18_glo)	C++20	10 / 100	96 ms	3976 KiB

glo

#include<bits/stdc++.h>
using namespace std;

int main(){
    //freopen("1.in","r",stdin);
    int n,d;
    cin>>n>>d;
    vector<int> v(n);
    for (int i=0;i<n;i++) cin>>v[i];
    vector<int> dp;
    vector<int> dp_idx;  // dp_idx[i] = index in v of element at dp[i]
    vector<int> parent(n, -1);  // parent[i] = previous index in LIS ending at i
    
    for (int i=0;i<n;i++) {
        int x=v[i];
        auto it = lower_bound(dp.begin(), dp.end(), x);
        int idx = it - dp.begin();
        
        if (it == dp.end()) {
            dp.push_back(x);
            dp_idx.push_back(i);
            if (idx > 0) {
                parent[i] = dp_idx[idx - 1];
            }
        } else {
            *it = x;
            dp_idx[idx] = i;
            if (idx > 0) {
                parent[i] = dp_idx[idx - 1];
            }
        }
    }
    
    // Reconstruct to find first and last indices
    int last_idx = dp_idx.back();
    int first_idx = last_idx;
    int cur = last_idx;
    while (cur != -1) {
        first_idx = cur;
        cur = parent[cur];
    }
    

    vector<int> dp1,dp2;
    
    for (int i=0;i<n;i++) {
        int x=v[i];
        if (i<first_idx) x-=d;
        auto it = lower_bound(dp1.begin(), dp1.end(), x);
        int idx = it - dp1.begin();
        if (it == dp1.end()) {
            dp1.push_back(x);

        } else {
            *it = x;
        }
    }


    for (int i=0;i<n;i++) {
        int x=v[i];
        if (i>last_idx) x+=d;
        auto it = lower_bound(dp2.begin(), dp2.end(), x);
        int idx = it - dp2.begin();
        if (it == dp2.end()) {
            dp2.push_back(x);
        } else {
            *it = x;
        }
    }


    cout<<max(dp1.size(),dp2.size())<<"\n";

}
        
    

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