Submission #101211

#TimeUsernameProblemLanguageResultExecution timeMemory
101211knon0501요리 강좌 (KOI17_cook)C++14
0 / 100
6 ms3072 KiB
#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)

cook.cpp: In function 'int main()':
cook.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d",&n,&m,&s,&e,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:17:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1 ; i<=n ; i++)for(j=1 ; j<=m ; j++)scanf("%d",&a[i][j]);
                                               ~~~~~^~~~~~~~~~~~~~~
cook.cpp:18:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1 ; i<=n ; i++)scanf("%d",&b[i]);
                          ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...