Submission #478682

#	Time	Username	Problem	Language	Result	Execution time	Memory
478682		kshitij_sodani	Diversity (CEOI21_diversity)	C++14	0 / 100	1 ms	332 KiB

diversity

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
//vector<llo> adj[200001];
llo it[300001];
llo dp[1001][30001];
llo pre[300001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	llo n,q;
	cin>>n>>q;
	map<llo,llo> ss;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ss[it[i]]++;
	}
	vector<llo> tt;
	for(auto j:ss){
		tt.pb(j.b);
	}
	sort(tt.begin(),tt.end());
	for(llo i=1;i<=tt.size();i++){
		pre[i]=pre[i-1]+tt[i-1];
	}
	llo m=tt.size();
	llo ans=m*n*(n+1)-(m-1)*n;
	
	if(m==1){

	}
	else{
		for(llo i=0;i<tt.size();i++){
			for(llo j=0;j<=n;j++){
				dp[i][j]=-(llo)1e18;
			}
			if(i==0){
				dp[i][tt[0]]=tt[0]*tt[0]+(n-tt[0])*(n-tt[0]);
			}
			else{
				for(llo j=0;j<=n;j++){
					llo cur=j+pre[tt.size()]-pre[i];
					llo su=0;
					su+=cur*cur;
					su+=(m-cur)*(m-cur);
					if(cur==n or cur==0){
						su=0;
					}
					dp[i][j]=max(dp[i][j],dp[i-1][j]+su);
					if(j>=tt[i]){
						llo cur=j;
						llo su=0;
						su+=cur*cur;
						su+=(m-cur)*(m-cur);
						if(cur==n or cur==0){
							su=0;
						}
						dp[i][j]=max(dp[i][j],dp[i-1][j-tt[i]]+su);
					}
				}
			}
		}
		llo ma=0;
		for(llo i=0;i<=n;i++){
			ma=max(ma,dp[tt.size()-1][i]);
		}
		ans-=ma;
	}
	ans/=2;


	//divide ans/2
	while(q--){
		llo l,r;
		cin>>l>>r;
		l--;
		r--;

		cout<<ans<<endl;
	}
 
 
 
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36