oj.uz

Submission #56240

# Submission time Handle Problem Language Result Execution time Memory
56240 2018-07-10T14:35:25 Z dennisstar None (KOI17_cook) C++11
0 / 100
 5 ms 2808 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 5 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 5 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 5 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 5 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 5 ms 2808 KB Output isn't correct
3 Halted 0 ms 0 KB -