Submission #79998

#	Time	Username	Problem	Language	Result	Execution time	Memory
79998		leejseo	요리 강좌 (KOI17_cook)	C++17	100 / 100	648 ms	296492 KiB

cook

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int N, M, S, E, T, M_;
int C[3001][6001], F[3001];
int D[3001][6001];
int A[3001][6001];
int B[3001][6001];

typedef pair<int, int> pii;

deque<pii> que[3001];


int readint(){
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
void init(){
	N = readint(), M_ = readint(), S = readint(), E = readint(), T = readint();
	M = M_+S-1;
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M_; j++) C[i][j] = readint();
	for (int i=1; i<=N; i++){
		for (int j=1; j<=M; j++){ 
			D[i][j] = INF;
			A[i][j] = A[i][j-1] + C[i][j];
		}
	}
	for (int i=1; i<=N; i++) F[i] = readint();
}

void solve(){
	for (int j=1; j<=M; j++){
		pii min3[3] = {pii(INF, -1), pii(INF, -1), pii(INF, -1)};
		for (int i=1; i<=N; i++){
			while (que[i].size() && que[i].front().second < j-E) 
				que[i].pop_front();
			if (j - S >= S){
				pii tmp = pii(B[i][j-S], j-S);
				while (que[i].size() && que[i].back() >= tmp)
					que[i].pop_back();
				que[i].push_back(tmp);
			}
			if (que[i].size()) D[i][j] = min(D[i][j], que[i].front().first + A[i][j] + T);
			if (j <= E) D[i][j] = min(D[i][j], A[i][j]);
			pii tmp = pii(D[i][j], i);
			if (min3[0] >= tmp){
				min3[2] = min3[1], min3[1] = min3[0], min3[0] = tmp;
			}
			else if (min3[1] >= tmp){
				min3[2] = min3[1], min3[1] = tmp;
			}
			else if (min3[2] >= tmp){
				min3[2] = tmp;
			}
		}
		//update B
		for (int i=1; i<=N; i++){
			for (int k=0; k<3; k++){
				if (min3[k].second != i && min3[k].second != F[i]){
					B[i][j] = min3[k].first - A[i][j];
					break;
				}
			}
		}
	}	
	int ans = INF;
	for (int i=1; i<=N; i++)
		for (int j=M_; j<=M; j++)
			ans = min(ans, D[i][j]);
	printf("%d\n", ans);
}

int main(){
	init();	
	solve();
}

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