# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1004250 | 0pt1mus23 | Kitchen (BOI19_kitchen) | C++14 | 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.
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 5*1e5, prime = 23;
const int inf = INT_MAX;
int arr[sze],brr[sze];
int n;
const int dse = 1e3;
int dp[dse+1][dse+1];
map<int,int> dp2[dse+1];
int func(){
int ans=0;
if(n<=0){
for(int i=0;i<=n;i++){
for(int j=0;j<=dse;j++){
dp[i][j]=-1;
}
}
dp[0][1]=0;
for(int i=0;i<n;i++){
for(int j=1;j<=dse;j++){
if(dp[i][j]!=-1){
int y =j * arr[i];
// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
for(int k=0;k<=y;k++){
/*if(k>dse){
return 17;
}*/
dp[i+1][ y-k ] = (max( dp[i+1][y-k], (dp[i][j] + (k)* brr[i] ) %mod));
}
}
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=dse;j++){
ans=max(ans,( dp[i][j] )%mod);
}
}
}
else{
for(int i =0;i<=n;i++){
dp2[i]=map<int,int>();
}
dp2[0][1]=0;
for(int i=0;i<n;i++){
for(auto v:dp2[i]){
int y =v.first * arr[i];
// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
for(int k=0;k<=y;k++){
/*if(k>dse){
return 17;
}*/
dp2[i+1][ y-k ] = (max( dp2[i+1][y-k], (v.second + (k)* brr[i] ) %mod));
}
}
}
for(int i=0;i<=n;i++){
for(auto v:dp2[i]){
// cout<<i<<" "<<v.second<<endl;
ans=max(ans,( v.second )%mod);
}
}
}
return ans;
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++){
arr[i]=X[i];
brr[i]=Y[i];
}
return func();
}
int updateX(int pos, int val) {
arr[pos]=val;
return func();
}
int updateY(int pos, int val) {
brr[pos]=val;
return func();
}