Submission #58809

#	Time	Username	Problem	Language	Result	Execution time	Memory
58809		red1108	요리 강좌 (KOI17_cook)	C++17	0 / 100	5 ms	2424 KiB

cook

#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 (stderr)

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]);
                       ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 44