This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long dp[15][32768];
int G,n;
bool get(long long X,long long i) {
return (X>>i)&1;
}
long long tr(vector<long long> cur) {
if(cur.size()<G) {
long long best = LONG_MAX;
for (long long i = 0; i < G; ++i) {
bool av = true;
for (long long k = 0; k < cur.size(); ++k) {
if(i==cur[k]) av=false;
}
cur.push_back(i);
if(av) best = min(best,tr(cur));
cur.pop_back();
}
return best;
}
long long v = 0;
long long s = 0;
for (long long i = 0; i < cur.size(); ++i) {
v+=dp[cur[i]][s];
s+=1<<cur[i];
}
return v;;
}
int main() {
string s; cin>>s;
G=0;n=s.size();
for (long long i = 0; i < s.size(); ++i) {
G=max(G,s[i]-'A'+1);
}
long long G2=1;
vector<long long> count(G,0);
for (long long i = 0; i < n; ++i) {
count[s[i]-'A']++;
}
for (long long i = 0; i < G; ++i) G2*=2;
;
for (long long i = 0; i < G2; ++i) {
for (long long j = 0; j < G; ++j) {
if(get(i,j)==1) continue;
dp[j][i]=LONG_MAX;
long long countj = 0;
long long totalj=count[j],totale=0;
long long counte = 0;
long long totalupto[n];
vector<long long> val(n,0);
for (long long k = 0; k < G; ++k) {
if(get(i,k)==1) totale+=count[k];
}
for (long long k = 0; k < n; ++k) {
if(get(i,s[k]-'A')==1) counte++;
if(s[k]=='A'+j) {
totalupto[k]=counte;
}
}
long long run = 0;
for (long long k = 0; k < n; ++k) {
if(s[k]=='A'+j) {
val[k]=2*run;
run+=totalupto[k];
}
}
dp[j][i]=min(dp[j][i],2*run+((totalj-1)*totalj)/2);
run = 0;
for (long long k = n-1; k >-1; --k) {
if(s[k]=='A'+j) {
run+=totale-totalupto[k];
val[k]+=2*run;
}
}
for (long long k = 0; k < n; ++k) {
if(s[k]=='A'+j) {
val[k]+=((countj-1)*(countj))/2+((totalj-countj-1)*(totalj-countj))/2;;
dp[j][i]=min(dp[j][i],val[k]);
countj++;
}
}
}
}
long long l = tr(vector<long long>());
cout<<l/2;
if(l%2==1) cout<<".5";
}
Compilation message (stderr)
passes.cpp: In function 'long long int tr(std::vector<long long int>)':
passes.cpp:11:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
11 | if(cur.size()<G) {
| ~~~~~~~~~~^~
passes.cpp:15:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (long long k = 0; k < cur.size(); ++k) {
| ~~^~~~~~~~~~~~
passes.cpp:26:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (long long i = 0; i < cur.size(); ++i) {
| ~~^~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:35:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (long long i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |