oj.uz

답안 #542223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
542223 2022-03-25T19:04:41 Z __Variatto Vještica (COCI16_vjestica) C++17
160 / 160
 1296 ms 1252 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=7e4+10, A=30, N=20, MAXV=1e6+10;
int n, dp[MAX], mini[A], roz[N];
int ile[N][A];
string s;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>s;
        roz[i]=s.size();
        for(int j=0; j<s.size(); j++)
            ile[i][s[j]-'a']++;
    }
    for(int i=1; i<(1<<n); i++){
        int x=i, l=1;
        bool pierw=true;
        vector<int>zap;
        while(x){
            if(x%2){
                if(pierw){
                    for(int j=0; j<='z'-'a'; j++)
                        mini[j]=ile[l][j];
                    pierw=false;
                }
                for(int j=0; j<='z'-'a'; j++)
                    mini[j]=min(mini[j], ile[l][j]);
                zap.pb(l);
            }
            x/=2, l++;
        }
        dp[i]=MAXV;
        if(__builtin_popcount(i)==1){
            dp[i]=roz[zap[0]];
            continue;
        }
        int maxi=0;
        for(int j=0; j<='z'-'a'; j++)
            maxi+=mini[j];
        for(int j=1; j<(1<<int(zap.size()))-1; j++){
            int l1=0, x1=j;
            int maska=0;
            while(x1){
                if(x1%2) maska+=(1<<(zap[l1]-1));
                x1/=2, l1++;
            }
            dp[i]=min(dp[i], dp[maska]+dp[i^maska]-maxi);
            //cout<<i<<" "<<maska<<" "<<(i^maska)<<"   "<<dp[maska]<<" "<<dp[i^maska]<<" "<<maxi<<"\n";
        }
    }
    cout<<dp[(1<<n)-1]+1<<"\n";
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j=0; j<s.size(); j++)
      |                      ~^~~~~~~~~

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1287 ms 688 KB Output is correct
5 Correct 1286 ms 800 KB Output is correct
6 Correct 1284 ms 1004 KB Output is correct
7 Correct 1279 ms 1056 KB Output is correct
8 Correct 1291 ms 1252 KB Output is correct
9 Correct 1296 ms 1148 KB Output is correct
10 Correct 1294 ms 1180 KB Output is correct