結果
問題 | No.1818 6 Operations |
ユーザー | ytft |
提出日時 | 2022-02-14 12:04:04 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,500 ms |
コード長 | 993 bytes |
コンパイル時間 | 4,358 ms |
コンパイル使用メモリ | 249,180 KB |
実行使用メモリ | 59,788 KB |
最終ジャッジ日時 | 2023-09-11 16:03:13 |
合計ジャッジ時間 | 7,116 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 23 ms
19,924 KB |
testcase_09 | AC | 50 ms
35,512 KB |
testcase_10 | AC | 22 ms
20,244 KB |
testcase_11 | AC | 21 ms
18,972 KB |
testcase_12 | AC | 40 ms
29,004 KB |
testcase_13 | AC | 28 ms
24,144 KB |
testcase_14 | AC | 35 ms
27,268 KB |
testcase_15 | AC | 40 ms
31,308 KB |
testcase_16 | AC | 33 ms
26,620 KB |
testcase_17 | AC | 49 ms
37,840 KB |
testcase_18 | AC | 75 ms
52,192 KB |
testcase_19 | AC | 64 ms
49,984 KB |
testcase_20 | AC | 74 ms
52,768 KB |
testcase_21 | AC | 78 ms
53,816 KB |
testcase_22 | AC | 56 ms
46,444 KB |
testcase_23 | AC | 81 ms
56,584 KB |
testcase_24 | AC | 67 ms
48,020 KB |
testcase_25 | AC | 76 ms
59,788 KB |
testcase_26 | AC | 69 ms
48,732 KB |
testcase_27 | AC | 72 ms
51,176 KB |
testcase_28 | AC | 24 ms
20,148 KB |
testcase_29 | AC | 21 ms
18,868 KB |
testcase_30 | AC | 80 ms
51,964 KB |
testcase_31 | AC | 69 ms
55,076 KB |
testcase_32 | AC | 81 ms
57,516 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int edit_dist(vector<int> &a,vector<int> &b){ vector<vector<int>> dp(a.size()+1,vector<int>(b.size()+1)); for(int i=0;i<=a.size();++i){ dp[i][0]=i; } for(int i=1;i<=b.size();++i){ dp[0][i]=i; } for(int i=1;i<=a.size();++i){ for(int j=1;j<=b.size();++j){ dp[i][j]=dp[i-1][j-1]; if(a[i-1]!=b[j-1]){ dp[i][j]=min(dp[i-1][j],dp[i][j]); dp[i][j]=min(dp[i][j-1],dp[i][j]); ++dp[i][j]; } } } return dp[a.size()][b.size()]; } int main(){ int input; vector<int> N(2); vector<vector<int>> A(2,vector<int>(0)); cin>>N[0]>>N[1]; for(int i=0;i<2;++i){ for(int j=0;j<N[i];++j){ cin>>input; A[i].emplace_back(0); for(int k=0;k<input;++k){ A[i].emplace_back(1); } } } cout<<(edit_dist(A[0],A[1]))<<endl; }