Submission #124479

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

cook

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;
int C[3005][6005], E[3005][6005];
deque<pii> D[3005];
int n, m, s, e, t;
int psum[3005][6005];
int fb[3005];
void input(){
    cin >> n >> m >> s >> e >> t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> psum[i][j];
            psum[i][j] += psum[i][j-1];
        }
        for(int j = m + 1; j < m + s; j++) psum[i][j] = psum[i][j-1];
    }
    for(int i=1;i<=n;i++){
        cin >> fb[i];
    }
}
void trim(deque<pii>& d, int second_th){
    while(!d.empty() && d.front().second < second_th) d.pop_front();
}
void pback(deque<pii>& d, pii v){
    while(!d.empty() && d.back() >= v) d.pop_back();
    d.push_back(v);
}
void pass(pii &n1, pii &n2, pii &n3, pii v){
    if(n1 >= v){
        n3 = n2; n2 = n1; n1 = v;
    }else if(n2 >= v){
        n3 = n2; n2 = v;
    }else if(n3 >= v){
        n3 = v;
    }
}
void dp(){
    for(int i=1;i<=n;i++){
        for(int j = 1; j < s; j++){
            C[i][j] = inf;
        }
    }
    for(int j = s; j < m + s; j++){
        pii m[3] = {{INT_MAX,-1}, {INT_MAX,-1}, {INT_MAX,-1}};
        for(int i = 1; i <= n; i++){
            trim(D[i], j-e);
            if(j - s >= s) pback(D[i], {E[i][j-s],j-s});
            C[i][j] = inf;
            if(!D[i].empty()) C[i][j] = min(C[i][j], D[i].front().first + psum[i][j] + t);
            if(j <= e) C[i][j] = min(C[i][j], psum[i][j]);
            pass(m[0],m[1],m[2],{C[i][j],i});
        }
        for(int i = 1; i <= n; i++){
            for(int b = 0; b < 3; b++){
                if(m[b].second != i && m[b].second != fb[i]){
                    E[i][j] = m[b].first - psum[i][j];
                    break;
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i=1;i<=n;i++){
        ans = min(ans, *min_element(C[i] + m, C[i] + m + s));
    }
    cout << ans << endl;
}
main(){
    input();
    dp();
}

Compilation message (stderr)

cook.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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