제출 #580511

#제출 시각아이디문제언어결과실행 시간메모리
580511haojiandanBoarding Passes (BOI22_passes)C++14
0 / 100
1 ms340 KiB
// wygzgyw #include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } template <typename T> void write(T t) { if (t<0) { putchar('-'); write(-t); return; } if (t>9) write(t/10); putchar('0'+t%10); } template <typename T> void writeln(T t) { write(t); puts(""); } #define MP make_pair const int maxn=(1e4)+10; int n,N; char s[maxn*10],lsh[maxn*10]; int m,pre[1<<10][maxn],suf[1<<10][maxn]; vector<int> vec[30]; double dp[1<<10]; int main() { scanf("%s",s+1); n=strlen(s+1); for (int i=1;i<=n;i++) lsh[++N]=s[i]; sort(lsh+1,lsh+N+1),N=unique(lsh+1,lsh+N+1)-lsh-1; for (int i=1;i<=n;i++) s[i]=lower_bound(lsh+1,lsh+N+1,s[i])-lsh+'A'-1; for (int i=1;i<=n;i++) m=max(m,s[i]-'A'),vec[s[i]-'A'].push_back(i); if (m==0) { m=n/2; double ans=m*0.5*(m-1)+(n-m)*0.5*(n-m-1); ans*=0.5; printf("%.6lf\n",ans); return 0; } m++; for (int t=0;t<(1<<m);t++) { for (int i=1;i<=n;i++) pre[t][i]=pre[t][i-1]+(t>>(s[i]-'A')&1); for (int i=n;i>=1;i--) suf[t][i]=suf[t][i+1]+(t>>(s[i]-'A')&1); dp[t]=1e18; } dp[0]=0; for (int t=0;t<(1<<m);t++) { for (int i=0;i<m;i++) if (!(t>>i&1)) { double tmp=0; for (int &x : vec[i]) tmp+=min(pre[t][x]+pre[1<<i][x-1]*0.5,suf[t][x]+suf[1<<i][x+1]*0.5); dp[t^(1<<i)]=min(dp[t^(1<<i)],dp[t]+tmp); } } printf("%.6lf\n",dp[(1<<m)-1]); return 0; } /* 0. Enough array size? Enough array size? Enough array size? Integer overflow? 1. Think TWICE, Code ONCE! Are there any counterexamples to your algo? 2. Be careful about the BOUNDARIES! N=1? P=1? Something about 0? 3. Do not make STUPID MISTAKES! Time complexity? Memory usage? Precision error? */

컴파일 시 표준 에러 (stderr) 메시지

passes.cpp: In function 'int main()':
passes.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%s",s+1); n=strlen(s+1);
      |  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...