제출 #1036336

#제출 시각아이디문제언어결과실행 시간메모리
1036336aymanrsCopy and Paste 3 (JOI22_copypaste3)C++17
5 / 100
1711 ms147200 KiB
#include<bits/stdc++.h> using namespace std; void solve(){ int n,a,b,c;string s; cin >> n >> s >> a >> b >> c; long long dp[n+1][n+1]; for(int i = 0;i <= n;i++)for(int j = 0;j <= n;j++) dp[i][j] = LONG_LONG_MAX; dp[0][0]=0; set<pair<long long, pair<int, int>>> se; se.insert({0, make_pair(0,0)}); while(!se.empty()){ auto [d, p] = *se.begin(); se.erase(se.begin()); if(p.first==n) { cout << d << '\n'; return; } vector<pair<long long, pair<int,int>>> v; v.emplace_back(d+a, pair<int,int>{p.first+1,p.second}); v.emplace_back(d+b, pair<int, int>{0, p.first}); if(p.first+p.second<=n) v.emplace_back(d+c, pair<int,int>{p.first+p.second,p.second}); for(auto [D, P] : v){ if(D>=dp[P.first][P.second]) continue; if(dp[P.first][P.second] != LONG_LONG_MAX) se.erase({dp[P.first][P.second], {P.first,P.second}}); dp[P.first][P.second]=D; se.insert({D, {P.first,P.second}}); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...