Submission #257440

#TimeUsernameProblemLanguageResultExecution timeMemory
257440uacoder123Vještica (COCI16_vjestica)C++14
160 / 160
173 ms10488 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; pair<int,vector<int>> v[65536]; int arr[65536]={}; bool cmp(int a,int b) { return __builtin_popcount(a)<__builtin_popcount(b); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); vi v1; for(int i=0;i<65536;++i) v1.pb(i); sort(all(v1),cmp); int n; string s; cin>>n; vi v2,v3(26); for(int i=0;i<26;++i) v3[i]=0; for(int i=0;i<n;++i) { v2=v3; string s; cin>>s; for(int j=0;j<s.size();++j) v2[s[j]-'a']++; v[(1<<i)]=mp(s.size(),v2); arr[(1<<i)]=s.size(); } for(int i=1;i<v1.size();++i) { if(v1[i]>(1<<n)-1) continue; int c=0,co=0; if(__builtin_popcount(v1[i])!=1) v[v1[i]].F=100000000; for(int s=(v1[i]-1)&v1[i];s;s=(s-1)&v1[i]) { if(c==0) { v[v1[i]].S=v3; arr[v1[i]]=max(arr[s],arr[v1[i]-s]); for(int j=0;j<26;++j) { v[v1[i]].S[j]=min(v[s].S[j],v[v1[i]-s].S[j]); co+=v[v1[i]].S[j]; } if(co==arr[v1[i]]) { v[v1[i]].F=co; break; } } c=1; v[v1[i]].F=min(v[v1[i]].F,v[s].F+v[v1[i]-s].F-co); } } cout<<v[(1<<n)-1].F+1<<endl; return(0); }

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<s.size();++j)
                 ~^~~~~~~~~
vjestica.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<v1.size();++i)
               ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...