oj.uz

답안 #58983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58983 2018-07-20T01:31:09 Z red1108 요리 강좌 (KOI17_cook) C++17
0 / 100
 8 ms 2644 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Correct 6 ms 2532 KB Output is correct
3 Correct 6 ms 2568 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Incorrect 8 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Correct 6 ms 2532 KB Output is correct
3 Correct 6 ms 2568 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Incorrect 8 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Correct 6 ms 2532 KB Output is correct
3 Correct 6 ms 2568 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Incorrect 8 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Correct 6 ms 2532 KB Output is correct
3 Correct 6 ms 2568 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Incorrect 8 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2424 KB Output is correct
2 Correct 6 ms 2532 KB Output is correct
3 Correct 6 ms 2568 KB Output is correct
4 Correct 5 ms 2568 KB Output is correct
5 Incorrect 8 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -