oj.uz

Submission #299010

# Submission time Handle Problem Language Result Execution time Memory
299010 2020-09-14T12:11:29 Z mat_v Vještica (COCI16_vjestica) C++14
160 / 160
 241 ms 832 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define xx first
#define yy second
#define pii pair<int,int>



using namespace std;

int n;
int freq[20][30];
int dp[67000];
bool bio[67000];
int mini[30];

int resi(int mask){
    if(bio[mask])return dp[mask];
    bio[mask] = 1;
    int tr = 0;
    ff(i,0,25)mini[i] = 1e9;
    int kol = 0;
    ff(i,0,n - 1){
        if((1<<i)&mask){
            kol++;
            ff(j,0,26){
                mini[j] = min(mini[j], freq[i][j]);
            }
        }
    }
    ff(j,0,26){
        tr += mini[j];
    }
   // cout << mask << " " << tr << "\n";
    if(kol == 1)return dp[mask] = tr;
    int p1 = 1e9;
    for(int submask = mask; submask; submask = (submask - 1) & mask){
        if(submask == mask)continue;
        p1 = min(p1, resi(submask) + resi(mask^submask));
    }
    return dp[mask] = -tr + p1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    ff(i,0,n - 1){
        string x;
        cin >> x;
        int m = x.length();
        ff(j,0,m - 1)freq[i][x[j] - 'a']++;
    }
    cout << resi((1<<n) - 1) + 1;
    return 0;
}

Compilation message

vjestica.cpp: In function 'int resi(int)':
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:21:5: note: in expansion of macro 'ff'
   21 |     ff(i,0,25)mini[i] = 1e9;
      |     ^~
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:23:5: note: in expansion of macro 'ff'
   23 |     ff(i,0,n - 1){
      |     ^~
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:26:13: note: in expansion of macro 'ff'
   26 |             ff(j,0,26){
      |             ^~
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:31:5: note: in expansion of macro 'ff'
   31 |     ff(j,0,26){
      |     ^~
vjestica.cpp: In function 'int main()':
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:48:5: note: in expansion of macro 'ff'
   48 |     ff(i,0,n - 1){
      |     ^~
vjestica.cpp:2:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
vjestica.cpp:52:9: note: in expansion of macro 'ff'
   52 |         ff(j,0,m - 1)freq[i][x[j] - 'a']++;
      |         ^~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 236 ms 712 KB Output is correct
5 Correct 237 ms 764 KB Output is correct
6 Correct 234 ms 768 KB Output is correct
7 Correct 234 ms 764 KB Output is correct
8 Correct 241 ms 768 KB Output is correct
9 Correct 241 ms 832 KB Output is correct
10 Correct 238 ms 768 KB Output is correct