Submission #56240

#	Time	Username	Problem	Language	Result	Execution time	Memory
56240		dennisstar	요리 강좌 (KOI17_cook)	C++11	0 / 100	5 ms	2808 KiB

cook

#include <bits/stdc++.h>
using namespace std;
int Dp[3010][3010];
int N,M,S,E,T;
int ar[3010][3010], ban[3010];
deque<pair<int,int> > Dq[3010];
set<pair<int,int> > Set;
int main()
{
//	freopen("input.txt","r", stdin);
	scanf("%d %d %d %d %d", &N, &M, &S, &E, &T);
	int i, j; set<pair<int,int> >::iterator it;
	for(i=1; i<=N; i++) for (j=1; j<=M; j++) scanf("%d", &ar[i][j]), ar[i][j]+=ar[i][j-1];
	for(i=1; i<=N; i++) scanf("%d", &ban[i]);
	for(i=S; i<=M; i++) {
		Set.clear();
		if(i==S||i>=2*S) for(j=1; j<=N; j++) {
			while(!Dq[j].empty()&&Dq[j].front().second<i-E) Dq[j].pop_front();
			while(!Dq[j].empty()&&Dq[j].back().first>=Dp[j][i-S]-ar[j][i-S]) Dq[j].pop_back();
			Dq[j].push_back(make_pair(Dp[j][i-S]-ar[j][i-S],i-S));
		}
		for(j=1; j<=N; j++) Set.insert(make_pair(Dq[j].front().first+ar[j][i]+T, j));
		if (i==M) {
			printf("%d", (*Set.begin()).first-T);
			return 0;
		}
		for(j=1; j<=N; j++) {
			it=Set.begin();
			while((*it).second==j||(*it).second==ban[j]) ++it;
			Dp[j][i]=(*it).first;
		}
	}
	int mn=Dp[1][M];
	for(i=2; i<=N; i++) mn=min(mn,Dp[i][M]);
	printf("%d", mn-T);
	return 0;
}

Compilation message (stderr)

cook.cpp: In function 'int main()':
cook.cpp:11: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:13:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) for (j=1; j<=M; j++) scanf("%d", &ar[i][j]), ar[i][j]+=ar[i][j-1];
                                           ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cook.cpp:14:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &ban[i]);
                      ~~~~~^~~~~~~~~~~~~~~

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