Submission #58988

#TimeUsernameProblemLanguageResultExecution timeMemory
58988red1108요리 강좌 (KOI17_cook)C++17
0 / 100
6 ms2424 KiB
#include <vector> #include <stdio.h> #include <deque> using namespace std; const int inf=2147483647; vector<vector<int>> input,sum; vector<int> dp[3010]; struct DATA{ int value; int before; }mindp[6010][3]; deque<pair<int,int>> dq[3010]; int n, m, row, limit, change, cant[3010]; int getmin(int i, int j) { if(i<row) return (-1)*change; if(mindp[i][0].before!=cant[j]&&mindp[i][0].before!=j) return mindp[i][0].value; else if(mindp[i][1].before!=cant[j]&&mindp[i][1].before!=j) return mindp[i][1].value; else if(mindp[i][2].before!=cant[j]&&mindp[i][2].before!=j) return mindp[i][2].value; } void gang(int i, int j,int bac) { if(j<1) return; if(mindp[i][0].value>=j) { mindp[i][2]=mindp[i][1]; mindp[i][1]=mindp[i][0]; mindp[i][0].value=j; mindp[i][0].before=bac; } else if(mindp[i][1].value>=j) { mindp[i][2]=mindp[i][1]; mindp[i][1].value=j; mindp[i][1].before=bac; } else if(mindp[i][2].value>=j) { mindp[i][2].value=j; mindp[i][2].before=bac; } } int main() { int i, j, ina; scanf("%d %d %d %d %d", &n, &m, &row, &limit, &change); input.push_back(vector<int>{0}); sum.push_back(vector<int>{0}); for(i=1;i<=n;i++) { input.push_back(vector<int>{0}); sum.push_back(vector<int>{0}); dp[i].push_back(0); for(j=1;j<=m;j++) { scanf("%d",&ina); input[i].push_back(ina); sum[i].push_back(sum[i][j-1]+ina); dp[i].push_back(0); } for(j=1;j<=m;j++) {sum[i].push_back(sum[i][sum[i].size()-1]);input[i].push_back(0);dp[i].push_back(0);} } for(i=1;i<=n;i++) scanf("%d", &cant[i]); for(i=row;i<=m+row-1;i++) { for(j=0;j<3;j++) mindp[i][j].value=inf*inf; for(j=1;j<=n;j++) { while(!dq[j].empty()&&dq[j].front().second<i-limit+1) dq[j].pop_front(); pair<int,int> newput={getmin(i-row,j)+change,i-row+1}; if(i-row>=row||i<=limit){ if(i-row<row&&i<=limit) newput.second=1; while(!dq[j].empty()&&(dq[j].back().first+sum[j][i]-sum[j][dq[j].back().second-1]>=newput.first+sum[j][i]-sum[j][i-row]||dq[j].back().second<i-limit+1)) dq[j].pop_back(); dq[j].push_back(newput); } if(dq[j].front().first>=inf||dq[j].empty()) dp[j][i]=inf*inf; else dp[j][i]=dq[j].front().first+sum[j][i]-sum[j][dq[j].front().second-1]; gang(i,dp[j][i],j); } } int ans=inf; for(i=1;i<=n;i++) { for(j=m;j<=m+row-1;j++) { ans=dp[i][j]<ans&&dp[i][j]>0?dp[i][j]:ans; } } printf("%d",ans); }

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:66:47: warning: integer overflow in expression [-Woverflow]
         for(j=0;j<3;j++) mindp[i][j].value=inf*inf;
                                            ~~~^~~~
cook.cpp:76:69: warning: integer overflow in expression [-Woverflow]
             if(dq[j].front().first>=inf||dq[j].empty()) dp[j][i]=inf*inf;
                                                                  ~~~^~~~
cook.cpp: In function 'int getmin(int, int)':
cook.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
cook.cpp: In function 'int main()':
cook.cpp:46: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, &row, &limit, &change);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:56:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&ina);
             ~~~~~^~~~~~~~~~~
cook.cpp:63:28: 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", &cant[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...