# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
375571 | 2021-03-09T14:37:03 Z | iliccmarko | Vještica (COCI16_vjestica) | C++14 | 135 ms | 8808 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 100000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define single_case solve(); #define line cerr<<"----------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); } #define mod 1000000007LL ll cnt[20][30]; ll n; ll dp[1000005]; ll prefix_cnt(int mask) { ll maks[30]; for(int i = 0;i<30;i++) maks[i] = INF; for(int i = 0;i<n;i++) { int bit = (mask>>i)&1; if(bit) { for(int j = 0;j<26;j++) maks[j] = min(maks[j], cnt[i][j]); } } ll l = 0; for(int i = 0;i<26;i++) l += maks[i]; return l; } int main() { ios cin>>n; for(int i = 0;i<1000005;i++) dp[i] = -1; for(int i = 0;i<n;i++) { string s; cin>>s; for(char c : s) { cnt[i][c-'a']++; } } ll p = prefix_cnt((1<<n)-1); for(int i = 0;i<n;i++) { int c = 0; for(int j = 0;j<26;j++) c += cnt[i][j]; dp[1<<i] = c; } for(int mask = 1;mask<(1<<n);mask++) { if(dp[mask]!=-1) continue; ll c = prefix_cnt(mask); dp[mask] = INF; for(int sub_mask = (mask-1)&mask;sub_mask>0;sub_mask=(sub_mask-1)&mask) { dp[mask] = min(dp[mask], dp[sub_mask] + dp[mask^sub_mask] - c); } } cout<<dp[(1<<n)-1]+1; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8172 KB | Output is correct |
2 | Correct | 5 ms | 8172 KB | Output is correct |
3 | Correct | 5 ms | 8172 KB | Output is correct |
4 | Correct | 105 ms | 8172 KB | Output is correct |
5 | Correct | 107 ms | 8428 KB | Output is correct |
6 | Correct | 107 ms | 8428 KB | Output is correct |
7 | Correct | 117 ms | 8808 KB | Output is correct |
8 | Correct | 135 ms | 8792 KB | Output is correct |
9 | Correct | 108 ms | 8756 KB | Output is correct |
10 | Correct | 107 ms | 8684 KB | Output is correct |