oj.uz

Submission #478728

# Submission time Handle Problem Language Result Execution time Memory
478728 2021-10-08T08:10:36 Z kshitij_sodani Diversity (CEOI21_diversity) C++14
4 / 100
 15 ms 3912 KB 
//#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+=(n-cur)*(n-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+=(n-cur)*(n-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

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Incorrect 15 ms 3912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Incorrect 15 ms 3912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Incorrect 15 ms 3912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Incorrect 15 ms 3912 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Incorrect 15 ms 3912 KB Output isn't correct
15 Halted 0 ms 0 KB -