Submission #58983

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

cook

#include <vector>
#include <stdio.h>
#include <deque>
using namespace std;
typedef long long ll;
const long long inf=2100000000;
vector<vector<int>> input,sum;
vector<long long> dp[3010];
struct DATA{
    long long value;
    long long before;
}mindp[6010][3];
deque<pair<long long,long long>> dq[3010];
ll n, m, row, limit, change, cant[3010];
ll getmin(ll i,ll 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(ll i, ll j,ll bac)
{
    if(mindp[i][0].value==0)mindp[i][0].value=mindp[i][1].value=mindp[i][2].value=inf*inf;
    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()
{
    ll i, j, ina;
    scanf("%lld %lld %lld %lld %lld", &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("%lld",&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("%lld", &cant[i]);
    for(i=row;i<=m+row-1;i++)
    {
        if(i-row<row&&i>limit){gang(i,inf*inf,inf*inf);for(j=1;j<=n;j++) dp[j][i]=inf*inf;continue;}
        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].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);
        }
    }
    ll ans=inf*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("%lld",ans);
}

Compilation message (stderr)

cook.cpp: In function 'll getmin(ll, ll)':
cook.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
cook.cpp: In function 'int main()':
cook.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld %lld %lld", &n, &m, &row, &limit, &change);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld",&ina);
             ~~~~~^~~~~~~~~~~~~
cook.cpp:66: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("%lld", &cant[i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~

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