This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const int M=5001;
const ll inf=1e9+10;
ll n,a,b,c;
string s;
ll dp[M][M];
bool vis[M][M];
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n>>s>>a>>b>>c;
priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>>q;
q.push({0,{0,0}});
ll ans=inf;
while(!q.empty()){
pair<ll,pii>p=q.top();
q.pop();
if(max(p.S.S,p.S.F)>n||vis[p.S.F][p.S.S])
continue;
vis[p.S.F][p.S.S]=1;
if(p.S.F==n)
ans=min(ans,p.F);
q.push({p.F+a,{p.S.F+1,p.S.S}});
q.push({p.F+b,{0,p.S.F}});
q.push({p.F+c,{p.S.F+p.S.S,p.S.S}});
}
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |