oj.uz

Submission #1099038

# Submission time Handle Problem Language Result Execution time Memory
1099038 2024-10-10T12:38:13 Z razivo Boarding Passes (BOI22_passes) C++14
25 / 100
 41 ms 604 KB 
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long dp[10][2048];
int G,n;
bool get(int X,int i) {
    return (X>>i)&1;
}
long long tr(vector<int> cur) {
    if(cur.size()<G) {
        long long best = LONG_MAX;
        for (int i = 0; i < G; ++i) {
            bool av = true;
            for (int 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 (int 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 (int i = 0; i < s.size(); ++i) {
        G=max(G,s[i]-'A'+1);
    }
    int G2=1;
    vector<int> count(G,0);
    for (int i = 0; i < n; ++i) {
        count[s[i]-'A']++;
    }
    for (int i = 0; i < G; ++i) G2*=2;
    ;
    for (int i = 0; i < G2; ++i) {
        for (int 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;
            int counte = 0;
            long long totalupto[n];
            vector<long long> val(n,0);
            for (int k = 0; k < G; ++k) {
                if(get(i,k)==1) totale+=count[k];
            }
            for (int 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 (int 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 (int k = n-1; k >-1; --k) {
                if(s[k]=='A'+j) {
                    run+=totale-totalupto[k];
                    val[k]+=2*run;
                }
            }
            for (int 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++;
                }
            }
        }
    }
    cout<<((double)tr(vector<int>()))/2;
}

Compilation message

passes.cpp: In function 'long long int tr(std::vector<int>)':
passes.cpp:11:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |     if(cur.size()<G) {
      |        ~~~~~~~~~~^~
passes.cpp:15:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |             for (int k = 0; k < cur.size(); ++k) {
      |                             ~~^~~~~~~~~~~~
passes.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < cur.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 440 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 440 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 444 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 41 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Incorrect 41 ms 604 KB 1st numbers differ - expected: '12495000.5000000000', found: '12495000.0000000000', error = '0.0000000400'
37 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -