Submission #676223

#	Time	Username	Problem	Language	Result	Execution time	Memory
676223		mseebacher	Global Warming (CEOI18_glo)	C++17	28 / 100	2067 ms	4984 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
#define pb(x) push_back(x)

vector<int> ad[MAXI];
vector<bool> vis(MAXI,0);
map<pair<int,int>,int> m;

void dfs(int x){
	if(vis[x]) return;
	vis[x] = 1;
	for(auto s:ad[x]){
		dfs(s);
	}
}

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[j-1] < a[i] && a[i] < d[j])
            d[j] = a[i];
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (d[i] < INF)
            ans = i;
    }
    return ans;
}

int main(){
	
	int n,x; cin >> n >> x;
	x *=-1;
	int maxi = 0;
	vector<int> a(n,0);
	for(int i = 0;i<n;i++) cin >> a[i];
	
		vector<int> b(a);
		for(int j = 0;j<n;j++){
			b[j] +=x;
			maxi = max(maxi,lis(b));
		}
	cout << maxi;
	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