Submission #748629

#TimeUsernameProblemLanguageResultExecution timeMemory
748629inventiontimeBoarding Passes (BOI22_passes)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define endl '\n' //comment for interactive #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pb push_back #define re resize #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define all1(x) (x).begin()+1, (x).end() #define loop(i, n) for(int i = 0; i < n; i++) #define loop1(i, n) for(int i = 1; i <= n; i++) #define print(x) cout << #x << ": " << x << endl << flush typedef long long ll; typedef vector<int> vi; typedef vector<double> vd; typedef array<int, 2> ii; typedef array<int, 3> ti; typedef vector<ii> vii; typedef vector<ti> vti; typedef vector<vi> vvi; typedef priority_queue<int> pq; template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; } template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; } const int inf = 1e17; double cst(int x) { double res = 0; loop1(i, x) { res += (double) (i-1)/2; } return res; } void solve() { string s; cin >> s; int n = 899; cout << setprecision(10) << cst(n/2) + cst((n+1)/2) << endl; // vvi pos(26); // loop(i, n) // pos[s[i]-'a'].pb(i); // vi ch; // loop(i, 26) if(!pos[i].empty()) // ch.pb(i); // int g = ch.size(); // vi id(26); // loop(i, g) id[ch[i]] = i; // vi dp(1 << g, inf); // dp[0] = 0; // loop1(pre, 1 << g) { // bitset<15> prev(pre); // loop(ch, g) if(!prev[ch]) { // int nxt = pre + 1 << ch; // int cost = inf; // loop(idx, n) { // int ans = 0; // int cnt = 0, oth = 0; // for(int i = 0; i <= idx; i++) { // if(prev[id[s[i]-'a']]) oth++; // else if(id[s[i]-'a'] == ch) { // cnt++; // ans += oth; // } // } // ans += cst(cnt); // cnt = 0, oth = 0; // for(int i = n; i > idx; i--) { // if(prev[id[s[i]-'a']]) oth++; // else if(id[s[i]-'a'] == ch) { // cnt++; // ans += oth; // } // } // ans += cst(cnt); // ckmin(cost, ans); // } // ckmin(dp[nxt], dp[pre] + cost); // } // } // cout << dp[1 << g - 1] << endl; } signed main() { fast_io; int t = 1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...