oj.uz

Submission #671036

# Submission time Handle Problem Language Result Execution time Memory
671036 2022-12-11T17:15:22 Z Do_you_copy Vještica (COCI16_vjestica) C++17
160 / 160
 171 ms 1640 KB 
/*
    I find it wholesome to be alone the greater part of the time.
    To be in company, even with the best, is soon wearisome and dissipating.
    I love to be alone.
    I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 1;
//const int Mod = 1e9 + 7;
//const int inf =
int n;
int cnt[30][30];
int f[1 << 17];
int dp[1 << 17];
void Init(){
    cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; ++i){
        string s; cin >> s;
        for (char c: s){
            ++cnt[i][c - 'a'];
        }
    }
    for (int i = 1; i < 1 << n; ++i){
        int b[26]; memset(b, 0x3f, sizeof(b));
        for (int j = 0; j < n; ++j){
            if ((i & (1 << j)) == 0) continue;
            for (int k = 0; k < 26; ++k){
                b[k] = min(b[k], cnt[j][k]);
            }
        }
        for (int j = 0; j < 26; ++j) f[i] += b[j];
    }
    for (int i = 1; i < 1 << n; ++i){
        if (__builtin_popcount(i) == 1){
            dp[i] = f[i];
            continue;
        }
        for (int j = i; j; j = (j - 1) & i){
            int k = i ^ j;
            if (!k) continue;
            dp[i] = min(dp[i], dp[j] + dp[k] - f[i]);
        }
    }
    cout << dp[(1 << n) - 1] + 1;
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
vjestica.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 171 ms 1100 KB Output is correct
5 Correct 166 ms 1168 KB Output is correct
6 Correct 167 ms 1400 KB Output is correct
7 Correct 170 ms 1492 KB Output is correct
8 Correct 171 ms 1640 KB Output is correct
9 Correct 164 ms 1596 KB Output is correct
10 Correct 171 ms 1604 KB Output is correct