# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
666511 | 2022-11-28T20:03:14 Z | mychecksedad | Boarding Passes (BOI22_passes) | C++17 | 405 ms | 1856 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; double calc(vector<int> p){ pref.clear(); pref.resize(n); vis.clear(); vis.resize(n); double S = 0; for(int i = 0; i < p.size(); ++i){ long long a = v[p[i]].size(); double best = -1; long long cur = 0; int po = n - 1; for(int j = a - 1; j >= 0; --j){ int pos = v[p[i]][j]; cur += pref[n - 1] - pref[pos]; } best = cur + a*(a-1)/4.0; for(double k = 1; k <= a; k += 1){ int pos = v[p[i]][k - 1]; cur -= pref[n - 1] - pref[pos]; cur += pref[pos]; double k1 = a - k; double val = (k*(k-1) + k1*(k1-1))/4.0 + cur; best = (best == -1 ? val : min(val, best)); } for(int pos: v[p[i]]) vis[pos] = 1; for(int j = 0; j < n; ++j){ if(j == 0) pref[j] = vis[j]; else pref[j] = pref[j - 1] + vis[j]; } S += best; } return S; } void solve(){ cin >> s; n = s.length(); for(int i = 0; i < n; ++i) v[s[i]-'A'].push_back(i); vector<int> p; double ans = 0; for(int i = 0; i < 15; ++i){ double best = -1; int pos = 0; for(int j = 0; j <= i; ++j){ p.insert(p.begin() + j, i); double ans = calc(p); if(best == -1 || best > ans) best = ans, pos = j; p.erase(p.begin() + j); } ans = best; p.insert(p.begin() + pos, i); } cout << ans; } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 340 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 5 ms | 340 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 318 ms | 1584 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 376 ms | 1780 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 400 ms | 1856 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 405 ms | 1808 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Incorrect | 1 ms | 212 KB | 1st numbers differ - expected: '1087.0000000000', found: '1090.0000000000', error = '0.0027598896' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 1 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Incorrect | 1 ms | 212 KB | 1st numbers differ - expected: '1087.0000000000', found: '1090.0000000000', error = '0.0027598896' |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 340 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 5 ms | 340 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 318 ms | 1584 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 376 ms | 1780 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 400 ms | 1856 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 405 ms | 1808 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 | Incorrect | 1 ms | 212 KB | 1st numbers differ - expected: '1087.0000000000', found: '1090.0000000000', error = '0.0027598896' |
15 | Halted | 0 ms | 0 KB | - |