Submission #1099040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099040		razivo	Boarding Passes (BOI22_passes)	C++14	60 / 100	974 ms	2264 KiB

passes

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long dp[10][2048];
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) {
      |                           ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40