# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
580192 | 2022-06-20T17:19:44 Z | wdjpng | Boarding Passes (BOI22_passes) | C++17 | 2000 ms | 1484 KB |
#include <bits/stdc++.h> #define int long long #define double long double #define rep(i,n) for(int i =0; i<n; i++) #define all(a) a.begin(),a.end() using namespace std; string s; int n; double f(int n) { return ((double) n)*((double) (n-1))/4.0; } string ord; vector<double>mem; vector<vector<int>>pos; int g; // cost to add the group gr with all members of that group with and index <= to maxi boarding on the left double cost(int bor, int gr, int maxi) { double sum = 0; int firstr = maxi+1; sum+=f(pos[gr].size()-firstr) + f(firstr); vector<int>otherpos; rep(i,n) if(((1<<(s[i]-'A'))&bor)==0) otherpos.push_back(i); rep(i,firstr) { sum+=upper_bound(all(otherpos),pos[gr][i])-otherpos.begin(); } for(int i = firstr; i < pos[gr].size(); i++) sum+=otherpos.end()-upper_bound(all(otherpos),pos[gr][i]); return sum; } vector<int>lookup; double dfs(int bor) { if(mem[bor]>-0.9) return mem[bor]; double sol = 1e18; rep(ck,g) { int i=lookup[ck]; if(!((1<<i)&bor)) continue; int nbor = bor^(1<<i); int start = -1, end = pos[i].size()-1; // while(end-start>1) // { // int c = (start+end)/2; // double l =cost(bor,i,c), r=cost(bor,i,c+1); // if(r>=l) end=c; // else start=c; // }; double minn = 1e18; rep(j,pos[i].size()) if(cost(bor,i,j)<minn) {minn=cost(bor,i,j); end=j;} sol=min(sol, cost(bor,i,end)+dfs(nbor)); } return mem[bor] = sol; } signed main() { cin>>s; s.size(); n=s.size(); double sum = f(n/2) + f((n+1)/2); cout.precision(300); char maxx=0; rep(i,n) maxx=max(maxx, s[i]); g=maxx-'A'+1; pos.resize(g); rep(i,n) pos[(s[i]-'A')].push_back(i); lookup.assign(g,0); rep(i,g) lookup[i]=i; mem.assign(1<<g,-1.0); mem[0]=0; cout<<dfs((1<<g)-1)<<'\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 18 ms | 308 KB | Output is correct |
6 | Execution timed out | 2052 ms | 1484 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 2 ms | 300 KB | Output is correct |
3 | Correct | 9 ms | 232 KB | Output is correct |
4 | Correct | 10 ms | 212 KB | Output is correct |
5 | Correct | 12 ms | 300 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 6 ms | 212 KB | Output is correct |
8 | Incorrect | 1 ms | 212 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 2 ms | 300 KB | Output is correct |
3 | Correct | 9 ms | 232 KB | Output is correct |
4 | Correct | 10 ms | 212 KB | Output is correct |
5 | Correct | 12 ms | 300 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 6 ms | 212 KB | Output is correct |
8 | Incorrect | 1 ms | 212 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 18 ms | 308 KB | Output is correct |
6 | Execution timed out | 2052 ms | 1484 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |