oj.uz

Submission #257440

# Submission time Handle Problem Language Result Execution time Memory
257440 2020-08-04T09:16:50 Z uacoder123 Vještica (COCI16_vjestica) C++14
160 / 160
 173 ms 10488 KB 
#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

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)
               ~^~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2816 KB Output is correct
2 Correct 11 ms 2816 KB Output is correct
3 Correct 11 ms 2816 KB Output is correct
4 Correct 139 ms 10080 KB Output is correct
5 Correct 139 ms 10232 KB Output is correct
6 Correct 173 ms 10360 KB Output is correct
7 Correct 150 ms 10484 KB Output is correct
8 Correct 145 ms 10488 KB Output is correct
9 Correct 145 ms 10480 KB Output is correct
10 Correct 150 ms 10488 KB Output is correct