제출 #1287063

#제출 시각아이디문제언어결과실행 시간메모리
1287063cowkimUplifting Excursion (BOI22_vault)C++20
0 / 100
5095 ms56540 KiB
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <math.h>
#include <cctype>
#include <cstdint>
#include <climits>
#include <iomanip>
#define ll long long
#define endl "\n"
using namespace std;
map<pair<int,int>,int> dp;
int solve(int index,ll pos,vector<pair<int,int>>& nums,int target){
    if(dp.find({index,pos}) != dp.end()) return dp[{index,pos}];
    if(index == nums.size()) return pos == target? 0:-1;
    int ret = -1;
    for(int i = 0; i<= nums[index].second; i++){
        int cur = solve(index +1,pos + nums[index].first * i,nums,target);
        if(cur == -1) continue;
        cur += i;
        ret = max(cur,ret);
    }
    dp[{index,pos}] = ret;
    return ret;
}
int main(){
    ll m,l;
    cin >> m >> l;
    vector<pair<int,int>> pars;
    for(int i = -m; i<= m; i++){
        int a;
        cin >> a;
        pars.push_back({i,a});
    }
    int ans = solve(0,0,pars,l);
    if(ans == -1) cout << "impossible" << endl;
    else cout << ans << endl;
    return 0;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...