Submission #967966

#	Time	Username	Problem	Language	Result	Execution time	Memory
967966		willychan	Binaria (CCO23_day1problem1)	C++17	18 / 25	823 ms	1048576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int MOD = 1e6+3;

struct dsu{
	vector<int> arr;
	int n;
	void init(int _n){
		 n = _n;	
		 arr.resize(n);
		 for(int i=0;i<n;i++) arr[i]=i;
	}
	int query(int a){
		if(arr[a]==a) return a;
		arr[a] = query(arr[a]);
		return arr[a];
	}
	void join(int a,int b){
		a = query(a);
		b = query(b);
		if(a!=b) arr[a]=b;
	}
};

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,k;cin>>n>>k;	
	vector<int> arr(n-k+1);
	for(int i=0;i<n-k+1;i++){
		cin>>arr[i];
	}
	dsu d;
	d.init(n);
	vector<int> hasto(n,-1);
	for(int i=0;i<n-k;i++){
		if(arr[i]==arr[i+1]){
			d.join(i,i+k);
		}else if(arr[i]+1==arr[i+1]){
			hasto[i]=0;
			hasto[i+k]=1;
		}else{
			hasto[i]=1;
			hasto[i+k]=0;
		}
	}
	for(int i=0;i<n;i++)	{
		int a = d.query(i);
		if(hasto[i]!=-1) hasto[a]=hasto[i];
	}
	for(int i=0;i<n;i++)	{
		hasto[i] = hasto[d.query(i)];
	}
	map<int,int> stuff;
	int cnt = 0;
	for(int i=0;i<k;i++){
		if(hasto[i]==1) cnt++;
		if(hasto[i]==-1){
			stuff[d.query(i)]++;
		}
	}
	int K = arr[0]-cnt;
	vector<int> w;	
	for(auto i : stuff) w.push_back(i.second);
	w.push_back(0);
	sort(w.begin(),w.end());
	vector<vector<int>> dp(w.size(),vector<int>(K+1,0));
	dp[0][0]=1;
	for(int i=1;i<w.size();i++){
		for(int j=0;j<=K;j++){
			dp[i][j] = dp[i-1][j];
			if(j>=w[i]) dp[i][j] = (dp[i][j]+dp[i-1][j-w[i]])%MOD;
		}
	}
	cout<<dp[w.size()-1][K]<<"\n";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=1;i<w.size();i++){
      |              ~^~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 7