oj.uz

답안 #489582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489582 2021-11-23T10:01:38 Z cpp219 Vještica (COCI16_vjestica) C++14
160 / 160
 489 ms 1364 KB 
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = (1 << 16) + 1;
const ll inf = 1e9 + 7;

string s;
ll c[N],dp[N],n,cnt[20][30],sz[30];

ll LCP(ll mask){
    if (c[mask] != -1) return c[mask];
    ll tmp[30]; fill(tmp,tmp + 27,inf);
    for (ll i = 0;i < n;i++){
        if (((mask >> i) & 1) == 0) continue;
        for (ll j = 0;j < 26;j++)
            tmp[j] = min(tmp[j],cnt[i][j]);
    }
    ll ans = 0;
    for (ll j = 0;j < 26;j++) ans += tmp[j];
    return c[mask] = ans;
}

ll f(ll mask){
    if (__builtin_popcount(mask) == 1) return LCP(mask);
    ll &res = dp[mask];
    if (res != -1) return res;
    ll nw = mask; res = inf;
    while(nw){
        nw = ((nw - 1) & mask);
        res = min(res,f(nw) + f(mask ^ nw) - LCP(mask));
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 0;i < n;i++){
        cin>>s; sz[i] = s.size();
        for (ll j = 0;j < s.size();j++) cnt[i][s[j] - 'a']++;
    }
    memset(dp,-1,sizeof(dp)); memset(c,-1,sizeof(c));
    cout<<f((1 << n) - 1) + 1;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (ll j = 0;j < s.size();j++) cnt[i][s[j] - 'a']++;
      |                       ~~^~~~~~~~~~
vjestica.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 489 ms 848 KB Output is correct
5 Correct 481 ms 920 KB Output is correct
6 Correct 425 ms 1084 KB Output is correct
7 Correct 445 ms 1288 KB Output is correct
8 Correct 468 ms 1364 KB Output is correct
9 Correct 451 ms 1320 KB Output is correct
10 Correct 445 ms 1320 KB Output is correct