Submission #124482

#	Time	Username	Problem	Language	Result	Execution time	Memory
124482		DJ035	요리 강좌 (KOI17_cook)	C++14	56 / 100	1049 ms	97212 KiB

cook

#include <bits/stdc++.h>



using namespace std;



const int N = 3005;





#define ll long long





ll cost[N][N];



ll dp[N][N];



int ban[N];

ll val[N];



queue<ll> q[N];



set<pair<ll,int> > s[N];





int main(){

    int n,m,S,e,t,i;

    

    

    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>S>>e>>t;

    

    int j;

    for(i=1;i<=n;++i)

        for(j=1;j<=m;++j){

            cin>>cost[i][j];

        }

    for(i=1;i<=n;++i)

        for(j=1;j<=m;++j){

            dp[i][j]= 1e13;

        }

    

    for(i=1;i<=n;++i)

        cin>>ban[i];

    

    set<pair<ll,int> >v;

    set<pair<ll,int> >::iterator it;

    int id;

    

    for(int IND = 1;IND<=m;++IND){    

        v.clear();

        for(id = 1;id<=n;++id){

            v.insert(make_pair(dp[id][IND-1],id));

            

            if(v.size()>3)v.erase(*v.rbegin());

        }

        

        for(id=1;id<=n;++id){

            

            for(it = v.begin();it!= v.end();++it){

                if( (*it).second== id || (*it).second == ban[id])

                    continue;

                q[id].push((*it).first - val[id]);

                break;

            }

            

            if(q[id].size()==S){

                s[id].insert( make_pair(q[id].front(),IND-S));

                q[id].pop();

            }



            while((int)s[id].size()>0){

                int len = (*s[id].begin()).second;

                len = IND- len;

                

                if(len>e){

                    s[id].erase(s[id].begin());

                }

                else

                    break;

            }

            

            val[id]+= cost[id][IND];

            

            if(s[id].size()>0){

                dp[id][IND]= val[id] + (*s[id].begin()).first + t;

                dp[id][IND]= min(dp[id][IND],(ll)1e13);

                

                if(IND==m){

                    dp[id][IND]-=t;

                    

                    while(!q[id].empty()){

                        dp[id][IND] = min(dp[id][IND], q[id].front() +val[id]);

                        q[id].pop();

                    }

                }

            }

        }

    }

    ll ret = 1e13;

    for(i=1;i<=n;++i)

        ret= min(ret, dp[i][m]);

    cout<<ret<<'\n';

}

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:127:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(q[id].size()==S){
                ~~~~~~~~~~~~^~~

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