| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 844487 | vjudge1 | Holding (COCI20_holding) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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;
files;
int t=1,_t=0;
// std::cin >> t;
while(_t<t){
++_t;
solve(_t);
}
return 0;
}