# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
101211 | knon0501 | 요리 강좌 (KOI17_cook) | C++14 | 6 ms | 3072 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 <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,m;
int s,e,t;
pair<int,int> dm[3005][3];
int d[3005][3005];
deque<pair<int,int>> deq[3005];
int ss[3005][3005];
int b[3005];
int a[3005][3005];
int main(){
int i,j;
scanf("%d %d %d %d %d",&n,&m,&s,&e,&t);
for(i=1 ; i<=n ; i++)for(j=1 ; j<=m ; j++)scanf("%d",&a[i][j]);
for(i=1 ; i<=n ; i++)scanf("%d",&b[i]);
for(i=1 ; i<=n ; i++)for(j=1 ; j<=m ; j++)ss[i][j]=ss[i][j-1]+a[i][j];
for(i=1 ; i<=n ; i++)deq[i].push_front(make_pair(-t,0));
for(i=1 ; i<=n ; i++)for(j=0 ; j<3 ; j++)dm[i][j].f=2e9;
for(i=1 ;i<=m ; i++){
for(j=1 ; j<=n ; j++){
while( !deq[j].empty() && deq[j].front().s<i-e){
deq[j].pop_front();
}
/// if(deq[j].empty())printf("!!!!!!!");
d[i][j]=deq[j].front().f+ss[j][i]+t;
/// printf("%d %d : %d %d %d %d \n",i,j,d[i][j],deq[j].front().f,deq[j].front().s,ss[j][i]);
if(dm[i][0].f>=d[i][j]){
dm[i][2]=dm[i][1];
dm[i][1]=dm[i][0];
dm[i][0].f=d[i][j];
dm[i][0].s=j;
}
else if(dm[i][1].f>=d[i][j]){
dm[i][2]=dm[i][1];
dm[i][1].f=d[i][j];
dm[i][1].s=j;
}
else if(dm[i][2].f>=d[i][j]){
dm[i][2].f=d[i][j];
dm[i][2].s=j;
}
}
if(i-s<0)continue;
for(j=1 ; j<=n ; j++){
pair<int,int> v;
if(dm[i-s+1][0].s!=j && dm[i-s+1][0].s!=b[j]){
v=dm[i-s+1][0];
}
else if(dm[i-s+1][1].s!=j && dm[i-s+1][1].s!=b[j]){
v=dm[i-s+1][1];
}
else{
v=dm[i-s+1][2];
}
v.f-=ss[j][i-s+1];
v.s=i-s+1;
/// if(i==4 &&j==2)printf("%d %d\n",v.f,ss[j][i-s+1]);
if(deq[j].empty() || deq[j].front().f>=v.f){
deq[j].push_front(v);
}
else{
while(!deq[j].empty() && deq[j].back().f>=v.f){
deq[j].pop_back();
}
deq[j].push_back(v);
}
}
}
int ans=2e9;
for(i=1 ; i<=n ; i++)ans=min(ans,d[m][i]);
for(i=m-s+1 ; i<m ;i++){
for(j=1 ; j<=n ; j++){
if(j!=dm[i][0].s &&b[j]!=dm[i][0].s){
ans=min(ans,t+dm[i][0].f+ss[n][j]-ss[i][j]);
}
else if(j!=dm[i][1].s && b[j]!=dm[i][1].s){
ans=min(ans,t+dm[i][1].f+ss[n][j]-ss[i][j]);
}
else{
ans=min(ans,t+dm[i][2].f+ss[n][j]-ss[i][j]);
}
}
}
cout<<ans;
/// cout<<d[5][3]<<endl<<dm[3][0].f<<endl<<dm[3][1].f<<endl<<dm[3][2].f<<endl<<d[3][1]<<ss[1][3];
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |