oj.uz

Submission #958454

# Submission time Handle Problem Language Result Execution time Memory
958454 2024-04-05T20:11:49 Z hariaakas646 Vještica (COCI16_vjestica) C++14
160 / 160
 110 ms 10668 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

int main() {
    // usaco();
    int n;
    cin >> n;
    vector<vi> cnt(n, vi(26));
    
    frange(i, n) {
        string str;
        cin >> str;
        for(auto e : str) {
            cnt[i][int(e-'a')]++;
        }
    }

    vector<pair<int, vi>> com(1<<n, mp(0, vi(26, 1e6)));

    frange(i, 1<<n) {
        frange(j, n) {
            if(i & (1<<j)) {
                vi tmp = com[i^(1<<j)].s;
                int tot = 0;
                frange(k, 26) {
                    tmp[k] = min(tmp[k], cnt[j][k]);
                    tot += tmp[k];
                }
                com[i] = mp(tot, tmp);
            }
        }
    }

    vector<lli> dp(1<<n, 1e18);

    frange(i, n) {
        dp[1<<i] = com[1<<i].f;
    }

    forr(i, 1, 1<<n) {
        for(int j=(i-1)&i; j>0; j=(j-1)&i) {
            dp[i] = min(dp[i], dp[j] + dp[i^j] - com[i].f);
        }
    }

    printf("%lld", dp[(1<<n)-1]+1);
}

Compilation message

vjestica.cpp: In function 'void usaco()':
vjestica.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 98 ms 9952 KB Output is correct
5 Correct 99 ms 10012 KB Output is correct
6 Correct 103 ms 10200 KB Output is correct
7 Correct 102 ms 10564 KB Output is correct
8 Correct 103 ms 10616 KB Output is correct
9 Correct 109 ms 10668 KB Output is correct
10 Correct 110 ms 10584 KB Output is correct