제출 #1022503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022503		vjudge1	Lottery (CEOI18_lot)	C++17	45 / 100	97 ms	924 KiB

lot

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e4 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,l,q,a[MAX];
int qrx[MAX];
bool idx[MAX];
int nxt[MAX];
int ans[105][MAX];

signed main(){
	
	read();
	
	cin >> n >> l;
	
	for(int i = 1;i <= n;i++)cin >> a[i];
	
	cin >> q;
	
	vector<int> rt;
	
	for(int i = 1;i <= q;i++){
		cin >> qrx[i];		
		idx[qrx[i]] = 1;
		rt.push_back(qrx[i]);
	}
	
	sort(rt.begin(),rt.end());
	rt.erase(unique(rt.begin(),rt.end()),rt.end());
	
	int k = rt.size() + 1;
	
	for(int i = n;i >= 0;i--){
		if(idx[i])k--;
		nxt[i] = k;
	}
	
	
	vector<int> f(n + 5,0);
	for(int len = 1;len <= n;len++){
		for(int i = 1;i <= n;i++)
			f[i] = f[i - 1] + (a[i] != a[i + len]);
		for(int i = 1;i + l - 1 <= n;i++){
			if(i + len + l - 1 > n)break;
			int cost = nxt[f[i + l - 1] - f[i - 1]];
			ans[cost][i]++;
			ans[cost][i + len]++;
		}
	}
	
	for(int i = 1;i <= (int)rt.size();i++){
		for(int j = 1;j <= n;j++){
			ans[i][j] += ans[i - 1][j];
		}
	}
	
	for(int i = 1;i <= q;i++){
		int x = lower_bound(rt.begin(),rt.end(),qrx[i]) - rt.begin() + 1;
		for(int j = 1;j <= n - l + 1;j++)cout << ans[x][j] << " \n"[j == n - l + 1];
	}
	
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20