ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#212181 | #3817. 写字 | zhangry | 0 | 0ms | 1272kb | C++11 | 1.5kb | 2024-10-13 11:53:27 | 2024-10-13 12:30:28 |
answer
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define awa return 0;
using namespace std;
int n,m;
string s,t;
bool find(string s,string t)
{
unordered_map<char,int>scnt;
for(char c:s)
{
scnt[c]++;
}
unordered_map<char,int>tcnt;
for(char c:t)
{
tcnt[c]++;
if(scnt[c]<tcnt[c])
{
return false;
}
}
return true;
}
signed main()
{
IOS;
unordered_map<char,vector<int>> pos;
cin>>n>>m;
cin>>s>>t;
if(find(s,t))
{
for (int i = 0; i < n; ++i)
{
pos[s[i]].push_back(i);
}
vector<int> dp(m+1,numeric_limits<int>::max());
dp[0]=0;
for (int i=0;i<m;++i)
{
char c=t[i];
if (pos.find(c)==pos.end())
{
cout<<-1<<endl;
return 0;
}
for (int j=0;j<pos[c].size(); ++j) {
int s_idx=pos[c][j];
for (int k=0;k<=i;++k)
{
if(dp[k]!=numeric_limits<int>::max())
{
int t=(k==0)?s_idx+1:dp[k]+abs(s_idx-pos[s[k-1]].back())+1;
dp[i+1]=min(dp[i+1],t);
}
}
}
}
cout<<dp[m]<<endl;
}
else
{
cout<<-1;
awa
}
awa
}
//
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1260kb
input:
1 1 v v
output:
1
result:
wrong answer 1st numbers differ - expected: '0', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 1268kb
input:
26 300 ywzhvjnpdfqtukimsrbxageloc brsmsrbxbxbxbxagagagegelococololegaxagaxaxbxbrbxbrsrsmikimikikimim...
output:
-1
result:
wrong answer 1st numbers differ - expected: '299', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 1272kb
input:
300 300 hgbfdbgcghedefchdabhgdddahcdedebceffegfbceehceeheggffhhddbecbfdhceeedcaeeebdaddfgccggfdcachg...
output:
-1
result:
wrong answer 1st numbers differ - expected: '3643', found: '-1'