oj.uz

Submission #1099040

# Submission time Handle Problem Language Result Execution time Memory
1099040 2024-10-10T12:45:33 Z razivo Boarding Passes (BOI22_passes) C++14
60 / 100
 974 ms 2264 KB 
#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

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 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 444 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 3 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 4 ms 2124 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2264 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 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 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 856 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 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 436 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 360 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 464 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 344 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 440 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 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 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 856 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 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 436 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 360 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 464 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 344 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 440 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 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 344 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 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 464 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 344 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 344 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 44 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 44 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 974 ms 848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 841 ms 848 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 853 ms 604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 840 ms 616 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 922 ms 656 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 874 ms 712 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 857 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 856 ms 604 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 845 ms 848 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 862 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 0 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 444 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 3 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 4 ms 2124 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2264 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 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 348 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 2 ms 856 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 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 600 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 436 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 360 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 464 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 344 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 440 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 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 344 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 348 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 464 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 344 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 344 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 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 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 44 ms 600 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 974 ms 848 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 841 ms 848 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 853 ms 604 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 840 ms 616 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 922 ms 656 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 874 ms 712 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 857 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 856 ms 604 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 845 ms 848 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 862 ms 604 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Runtime error 1 ms 604 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -