Submission #1036336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036336		aymanrs	Copy and Paste 3 (JOI22_copypaste3)	C++17	5 / 100	1711 ms	147200 KiB

copypaste3

#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();
}

• Subtask 1: 0 / 1
• Subtask 2: 5 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38