Submission #124486

#	Time	Username	Problem	Language	Result	Execution time	Memory
124486		DJ035	요리 강좌 (KOI17_cook)	C++14	100 / 100	577 ms	78052 KiB

cook

#include<bits/stdc++.h>
#define OO 1987654321
using namespace std;
int N,M,S,E,T;
int A[3003][3003],B[3003];
int C[3003][3003],DP[3003][3003];
deque<pair<int,int> > dq[3003];
pair<int,int> mn[3003][3];
int get_min(int day, int academy){
	if(mn[day][0].second != academy && mn[day][0].second != B[academy]){
		return mn[day][0].first;
	}
	if(mn[day][1].second != academy && mn[day][1].second != B[academy]){
		return mn[day][1].first;
	}
	return mn[day][2].first;
}
int main(){
	scanf("%d%d%d%d%d",&N,&M,&S,&E,&T);
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++){
			scanf("%d",&A[i][j]);
			C[i][j] = C[i][j-1]+A[i][j];
		}
	}
	for(int i = 1;i<=N;i++){
		scanf("%d",&B[i]);
	}
	for(int i = 1;i<=M;i++){
		for(int j = 1;j<=N;j++){
			if(i>=S){
				int tmp = get_min(i-S,j)-C[j][i-S];
				while(!dq[j].empty() && dq[j].back().first >= tmp){
					dq[j].pop_back();
				}
				dq[j].push_back(make_pair(tmp,i-S));
			}
			while(!dq[j].empty() && dq[j].front().second < i-E){
				dq[j].pop_front();
			}
			if(dq[j].empty() || dq[j].front().first == OO){
				DP[i][j] = OO;
			}
			else{
				DP[i][j] = dq[j].front().first+T+C[j][i];
			}
		}
		for(int j = 0;j<3;j++){
			mn[i][j] = make_pair(OO,0);
		}
		for(int j = 1;j<=N;j++){
			if(DP[i][j] == OO){
				continue;
			}
			int tmp = DP[i][j];
			if(tmp<mn[i][0].first){
				mn[i][2] = mn[i][1], mn[i][1] = mn[i][0], mn[i][0] = make_pair(tmp,j);
			}
			else if(tmp<mn[i][1].first){
				mn[i][2] = mn[i][1], mn[i][1] = make_pair(tmp,j);
			}
			else if(tmp<mn[i][2].first){
				mn[i][2] = make_pair(tmp,j);
			}
		}
	}
	int ans = OO;
	for(int i = 1;i<=N;i++){
		for(int j = M-E;j<M;j++){
			int tmp = get_min(j,i);
			if(tmp == OO){
				continue;
			}
			ans = min(ans,tmp+C[i][M]-C[i][j]);
		}
	}
	printf("%d",ans);
}

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d",&N,&M,&S,&E,&T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:22:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~
cook.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&B[i]);
   ~~~~~^~~~~~~~~~~~

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