# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
666520 | 2022-11-28T20:32:18 Z | mychecksedad | Boarding Passes (BOI22_passes) | C++17 | 2000 ms | 1424 KB |
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define setp() cout << setprecision(15) #define all(x) x.begin(), x.end() const int N = 1e5 + 100; int n; string s; double dp[N]; vector<int> v[15], pref, vis; void solve(){ cin >> s; n = s.length(); for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i); for(int i = 0; i < (1<<15); ++i) dp[i] = 1e15; dp[0] = 0; for(int mask = 1; mask < (1<<15); ++mask){ for(int j = 0; j < 15; ++j){ if(mask&(1<<j)){ double passes = 0; pref.clear(); pref.resize(n); for(int i = 0; i < 15; ++i){ if(i != j && (mask&(1<<i)) > 0) for(int pos: v[i]) pref[pos] = 1; } for(int i = 1; i < n; ++i) pref[i] = pref[i - 1] + pref[i]; long long cur = 0; long long s = v[j].size(); for(int i = 0; i < s; ++i){ cur += pref[n - 1] - pref[v[j][i]]; } passes = cur + s*(s-1)/4.0; for(long long i = 1; i <= s; ++i){ cur -= pref[n - 1] - pref[v[j][i - 1]]; cur += pref[v[j][i - 1]]; long long k1 = s - i; passes = min(passes, cur + (i*(i-1)+k1*(k1-1))/4.0); } dp[mask] = min(dp[mask], dp[mask^(1<<j)] + passes); } } } cout << dp[(1<<15)-1]; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int T = 1, aa; // cin >> T;aa=T; setp(); while(T--){ // cout << "Case #" << aa-T << ": "; solve(); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 817 ms | 584 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 14 ms | 468 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 15 ms | 468 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 14 ms | 580 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 909 ms | 576 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Execution timed out | 2086 ms | 1424 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 468 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 99 ms | 468 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 96 ms | 564 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 95 ms | 564 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 98 ms | 572 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 18 ms | 584 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 81 ms | 596 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 30 ms | 564 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 31 ms | 584 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 33 ms | 556 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 31 ms | 468 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 35 ms | 468 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 30 ms | 584 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 32 ms | 596 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 31 ms | 468 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 30 ms | 580 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 32 ms | 468 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 468 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 99 ms | 468 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 96 ms | 564 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 95 ms | 564 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 98 ms | 572 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 18 ms | 584 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 81 ms | 596 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 30 ms | 564 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 31 ms | 584 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 33 ms | 556 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 31 ms | 468 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 35 ms | 468 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 30 ms | 584 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 32 ms | 596 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 31 ms | 468 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 30 ms | 580 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 32 ms | 468 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
18 | Correct | 16 ms | 468 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
19 | Correct | 98 ms | 468 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
20 | Correct | 100 ms | 564 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 99 ms | 564 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 100 ms | 512 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 18 ms | 568 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 81 ms | 560 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 31 ms | 468 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 31 ms | 468 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 32 ms | 468 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 38 ms | 564 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 34 ms | 580 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 36 ms | 468 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 31 ms | 468 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 31 ms | 468 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 33 ms | 468 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 37 ms | 468 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
35 | Execution timed out | 2077 ms | 596 KB | Time limit exceeded |
36 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 817 ms | 584 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 14 ms | 468 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 15 ms | 468 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 14 ms | 580 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 909 ms | 576 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Execution timed out | 2086 ms | 1424 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |