oj.uz

Submission #1099042

# Submission time Handle Problem Language Result Execution time Memory
1099042 2024-10-10T12:46:53 Z razivo Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 3664 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1884 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2140 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2240 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2128 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 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 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 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 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 604 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 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.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 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 348 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 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 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 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 604 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 344 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 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 604 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 396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 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 444 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 1 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 2 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 44 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 43 ms 640 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 991 ms 652 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 863 ms 648 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 856 ms 604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 851 ms 604 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 848 ms 604 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 847 ms 600 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 862 ms 684 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 857 ms 656 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 858 ms 720 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 832 ms 604 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1884 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2140 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2240 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2128 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 344 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 396 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 444 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 2 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 44 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 43 ms 640 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 991 ms 652 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 863 ms 648 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 856 ms 604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 851 ms 604 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 848 ms 604 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 847 ms 600 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 862 ms 684 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 857 ms 656 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 858 ms 720 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 832 ms 604 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Execution timed out 2064 ms 3664 KB Time limit exceeded
57 Halted 0 ms 0 KB -