fork download
copy 
  1. #include <limits>
  2.         #include<bits/stdc++.h>
  3.         using namespace std;
  4.         #define int  long long
  5.         #define dl '\n'
  6.         const int INF = 1e18;
  7.         #define printvec(v) for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;
  8.         #define loop(i,n){} for(int i=0;i<n;i++){}
  9.         #define read(v,n)   for(int i=0;i<n;i++){cin>>v[i];}
  10.         #define all(v)                ((v).begin()), ((v).end())
  11.         #define rall(v)                ((v).rbegin()), ((v).rend())
  12.         typedef vector<int> vi;
  13.         typedef vector<pair<int,int>> vip;
  14.         #define ll long long
  15.         void Antoine_Sobhy(){
  16.             ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  17.         #ifndef ONLINE_JUDGE
  18.             // freopen("business.in", "r", stdin);
  19.             freopen("/home/antoine/Desktop/acpc/input.txt", "r", stdin);
  20.             freopen("/home/antoine/Desktop/acpc/output.txt", "w", stdout);
  21.         #endif
  22.         }
  23.  
  24.         void Read_Write() {
  25.             ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  26.             freopen("nocross.in", "r", stdin);
  27.             freopen("nocross.out", "w", stdout);
  28.         }
  29.     const int N=5e2+5;
  30.     int dp[N][N];
  31.     vi sp(N);
  32.     vi no(N);
  33.     int n,l,K;
  34.     int rec(int i,int last,int k,int lastno){
  35.         if (i==n-1)
  36.         {
  37.             int opt1=INF;
  38.             int opt2=INF;
  39.             if (k>0){
  40.                 opt1= ((l-lastno) *last);
  41.             }
  42.             else{
  43.                 opt2=((l-no[i]) *sp[i]) + ((no[i]-lastno)*last) ;
  44.             }
  45.             return min(opt1,opt2);
  46.         }
  47.  
  48.         int &ret=dp[i][k];
  49.         if(~ret) return ret;
  50.         ret=INF;
  51.         ret=rec(i+1,sp[i],k,no[i]) + ((no[i]-lastno)*last)  ;
  52.  
  53.         for (int j=1;j<=k;j++){
  54.             if (i+j<n){
  55.                 ret=min(ret,rec(i+j,last,k-j,lastno)+ ((no[i+j]-lastno)*last) );
  56.             }
  57.             }
  58.         return ret;
  59.  
  60.      }
  61.  
  62.     void solve(){
  63.     memset(dp,-1,sizeof(dp));
  64.         cin>>n>>l>>K;
  65.         for(int i=0;i<n;i++)
  66.         {
  67.             cin>>no[i];
  68.         }
  69.         for(int i=0;i<n;i++)
  70.         {
  71.             cin>>sp[i];
  72.         }
  73.         if (n==1)
  74.         {
  75.             cout<<(l-0)*sp[0];
  76.             return;
  77.         }
  78.         cout<<rec(1,sp[0],K,0)<<endl;
  79.  
  80.        }
  81.         int32_t main() {
  82.             Antoine_Sobhy();
  83.  
  84.             int t=1;
  85.             // cin>>t;
  86.             while(t--) {
  87.                 solve();
  88.             }
  89.  
  90.             return 0;
  91.  
  92.  
  93.         }
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5iW3HH
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!