Submission #823799

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
823799	2023-08-13 06:54:08	PoonYaPat	Boarding Passes (BOI22_passes)	C++14	60 / 100	2066 ms	1812 KiB

passes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans,dp[1<<15]; //2 times expected value
int m,n,g[100005];
vector<int> group[15];
ll cal(ll a) {
    return a*(a-1)/2;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin>>s;
    n=s.size();
    for (int i=0; i<(1<<15); ++i) dp[i]=2e15;
    
    map<char,int> mp;
    for (int i=0; i<n; ++i) mp[s[i]]=0;
    for (auto k : mp) mp[k.first]=m++;
    for (int i=0; i<n; ++i) group[mp[s[i]]].push_back(i), g[i]=mp[s[i]];
    dp[0]=0;
    for (int mask=1; mask<(1<<m); ++mask) {
        //find dp[mask]
        bool have[15];
        for (int i=0; i<m; ++i) {
            if (mask&(1<<i)) have[i]=true;
            else have[i]=false;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40