Submission #844490

#TimeUsernameProblemLanguageResultExecution timeMemory
844490vjudge1Holding (COCI20_holding)C++17
0 / 110
0 ms344 KiB
// Imagine not FFT #include <bits/stdc++.h> #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); #define int long long #define ll long long #define pb push_back #define ff first #define ss second #define pii std::pair < int , int > #define pll std::pair < ll , ll > #define vi std::vector < ll > #define vl std::vector < int > #define vii std::vector < pii > #define vll std::vector < pll > #define vvi std::vector < vi > #define vvii std::vector < vii > #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define forn(i,j) for(int i=0;i<j;i++) #define forr(i,j,k) for(int i=j;i<k;i++) #define mset multiset #define pqueue priority_queue #define cmax(a,b) (a = max(a,b)) #define cmin(a,b) (a = min(a,b)) #define sz(a) (int)(a.size()) using namespace std; int calc(int ans, int ind, vvi& cost, int len,vi& change, vi& from, int k,int limit,vector<int>& chosen,bool deb=true){ if(k==0 || ind>=limit) return ans; int tans = ans; forn(i,len){ if(chosen[i]==-1 && cost[ind][i]<=k) { chosen[i]=i; tans = min(tans,calc(ans,ind+1,cost,len,change,from,k-cost[ind][i],limit,chosen)-from[ind]+change[i]); chosen[i]=-1; } } return (min(tans,calc(ans,ind+1,cost,len,change,from,k,limit,chosen))); } void solve(int _t_case){ int n,l,r,k; cin >> n >> l >> r >> k; vi a(l-1); vi debt(r-l+1); vi b(n-r); for(int i=0;i<l-1;i++){ cin >> a[i]; } int ans = 0; for(int i=0;i<r-l+1;i++){ cin >> debt[i]; ans+=debt[i]; } for(int i=0;i<n-r;i++){ cin >> b[i]; } vvi cost(r-l+1,vi(n-r+l-1,1000000)); for(int d=0;d<sz(debt);d++){ for(int i=0;i<l-1;i++){ if(debt[i]>a[i]) cost[d][i]=d+l-1-i; } for(int i=0;i<n-r;i++){ if(debt[i]>b[i]) cost[d][i+l-1]=r+i-d-1; } } for(auto _b:b) a.pb(_b); vi chosen(n,-1); cout << calc(ans,0,cost,n-r+l-1,a,debt,k,sz(debt),chosen) << endl; return; } signed main(){ fastio; int t=1,_t=0; // std::cin >> t; while(_t<t){ ++_t; solve(_t); } 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...