Submission #1247290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247290		trimkus	상형문자열 (IOI24_hieroglyphs)	C++20	0 / 100	1030 ms	2162688 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;

void chmax(int& x, int y){
    x=max(x,y);
}

std::vector<int> ucs(std::vector<int> A, std::vector<int> B) {
    int n = A.size(), m = B.size();
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
        chmax(dp[i+1][j],dp[i][j]);
        chmax(dp[i][j+1],dp[i][j]);
        if(A[i]==B[j]){
        chmax(dp[i+1][j+1],dp[i][j]+1);
        }
        
        }
        }
        vector<int>res;
        int i=n,j=m;
        while(i>0&&j>0){
        if(A[i-1]==B[j-1]){
        res.push_back(A[i-1]);
        i--;
        j--;
        }else if(dp[i-1][j]>=dp[i][j-1])i--;
        else j--;
        }
        reverse(begin(res),end(res));
        map<int,int>cnt1,cnt2,cnt3;
        for(auto u :A)cnt1[u]++;
        for(auto u:B) cnt2[u]++;
        for(auto u:res)cnt3[u]++;
        for(auto [a, c]:cnt1){
            c =min(c,cnt2[a]);
            if(c>cnt3[a])return{-1};
        
        }
        
        
        return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42