Submission #865768

#TimeUsernameProblemLanguageResultExecution timeMemory
865768RifalDiversity (CEOI21_diversity)C++14
4 / 100
7027 ms4848 KiB
#include <bits/stdc++.h> #include <fstream> //#define endl '\n' #define mod 1000000007 #define INF 9000000000000000 using namespace std; //ofstream fout("intel.out"); //ifstream fin("intel.in"); const int Max = 3e5 + 5; int cnt[Max]; int who[12]; int order[12]; int now = 1; int n, q; long long ans = INF; long long sum = 0; long long dp[Max] = {}; void sol(int siz) { if(siz == now) { vector<int> v; for(int i = 1; i <= n; i++) dp[i] = 1; for(int i = 1; i < now; i++) { int x; x = cnt[who[order[i]]]; while(x--) { v.push_back(i); } } long long sum = 0; sum += dp[1]; for(long long i = 1; i < v.size(); i++) { if(v[i] != v[i-1]) { dp[i+1] += i; } dp[i+1] += dp[i]; sum += dp[i+1]; } ans = min(ans,sum); } for(int i = siz; i < now; i++) { swap(order[siz],order[i]); sol(siz+1); swap(order[siz],order[i]); } } int main() { ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); cin >> n >> q; for(int i = 0; i < 12; i++) order[i] = i; long long arr[n]; for(int i = 0; i < n; i++) { cin >> arr[i]; cnt[arr[i]]++; } for(int i = 0; i < Max; i++) { if(cnt[i] != 0) { who[now] = i; now++; } } if(q == 1) { int l, r; cin >> l >> r; } sol(1); cout << ans << endl; return 0; }

Compilation message (stderr)

diversity.cpp: In function 'void sol(int)':
diversity.cpp:29:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(long long i = 1; i < v.size(); i++) {
      |                              ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...