| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58809 |
2018-07-19T14:19:31 Z |
red1108 |
None (KOI17_cook) |
C++17 |
|
5 ms |
2424 KB |
#include <vector>
#include <stdio.h>
#include <deque>
using namespace std;
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+sum[j][i];
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(mindp[i][0].value==0||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==0||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==0||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++)
{
//printf("%d번째 날\n", i);
for(j=1;j<=n;j++)
{
while(!dq[j].empty()&&dq[j].front().second<=i-limit) dq[j].pop_front();
pair<int,int> newput={getmin(i-row,j)+change,i-row+1};
while(!dq[j].empty()&&(dq[j].back().first+input[j][i-1]>=newput.first||dq[j].back().second<=i-limit)) dq[j].pop_back();
dq[j].push_back(newput);
dp[j][i]=dq[j].front().first+sum[j][i]-sum[j][dq[j].front().second-1];
//printf("%d번째 학원을 완료했다. 크기는 %d dp[%d][%d]=%d\n", j, dq[j].size(),j,i,dp[j][i]);
gang(i,dp[j][i],j);
}
//printf("(%d,%d),(%d,%d),(%d,%d)\n",mindp[i][0].value,mindp[i][0].before,mindp[i][1].value,mindp[i][1].before,mindp[i][2].value,mindp[i][2].before);
}
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=m+row-1;j++) printf("%d ", dp[i][j]);
printf("\n");
}
*/
int ans=2147483647;
for(i=1;i<=n;i++)
{
for(j=m;j<=m+row-1;j++)
ans=min(dp[i][j],ans);
}
printf("%d",ans);
}
Compilation message
cook.cpp: In function 'int getmin(int, int)':
cook.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
cook.cpp: In function 'int main()':
cook.cpp:44: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:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&ina);
~~~~~^~~~~~~~~~~
cook.cpp:61: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 time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
