oj.uz

Submission #199451

# Submission time Handle Problem Language Result Execution time Memory
199451 2020-02-01T12:52:28 Z TadijaSebez Brunhilda’s Birthday (BOI13_brunhilda) C++11
100 / 100
 555 ms 120692 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=10000050;
const int Q=100050;
int dp[N],fir[N],go[Q],p[Q],n[Q],cnt[N],ptr;
void Add(int x,int i){go[i]=fir[x];fir[x]=i;}
int main(){
	int m,q;
	scanf("%i %i",&m,&q);
	for(int i=1;i<=m;i++)scanf("%i",&p[i]),Add(p[i],i),cnt[0]++;
	for(int i=1;i<N;i++){
		for(int id=fir[i],nxt;id;id=nxt){
			cnt[i-p[id]]--;
			cnt[i]++;
			nxt=go[id];
			if(i+p[id]<N)Add(i+p[id],id);
		}
		while(cnt[ptr]==0)ptr++;
		if(ptr==i){
			for(;i<N;i++)dp[i]=1e9;
			break;
		}
		dp[i]=dp[ptr]+1;
	}
	for(int i=1;i<=q;i++){
		scanf("%i",&n[i]);
		if(dp[n[i]]==1e9)printf("oo\n");
		else printf("%i\n",dp[n[i]]);
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&m,&q);
  ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:10:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++)scanf("%i",&p[i]),Add(p[i],i),cnt[0]++;
                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
brunhilda.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&n[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 39544 KB Output is correct
2 Correct 161 ms 117752 KB Output is correct
3 Correct 35 ms 41592 KB Output is correct
4 Correct 97 ms 117884 KB Output is correct
5 Correct 135 ms 117880 KB Output is correct
6 Correct 32 ms 39544 KB Output is correct
7 Correct 34 ms 41592 KB Output is correct
8 Correct 44 ms 46584 KB Output is correct
9 Correct 234 ms 117752 KB Output is correct
10 Correct 239 ms 117752 KB Output is correct
11 Correct 205 ms 117752 KB Output is correct
12 Correct 94 ms 117752 KB Output is correct
13 Correct 301 ms 117728 KB Output is correct
14 Correct 310 ms 117880 KB Output is correct
15 Correct 182 ms 117788 KB Output is correct
16 Correct 162 ms 117752 KB Output is correct
17 Correct 134 ms 117880 KB Output is correct
18 Correct 101 ms 117884 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 118008 KB Output is correct
2 Correct 218 ms 119160 KB Output is correct
3 Correct 508 ms 118904 KB Output is correct
4 Correct 183 ms 117792 KB Output is correct
5 Correct 398 ms 118520 KB Output is correct
6 Correct 160 ms 117752 KB Output is correct
7 Correct 197 ms 117880 KB Output is correct
8 Correct 163 ms 117752 KB Output is correct
9 Correct 420 ms 118856 KB Output is correct
10 Correct 447 ms 118752 KB Output is correct
11 Correct 441 ms 118300 KB Output is correct
12 Correct 238 ms 117700 KB Output is correct
13 Correct 171 ms 117784 KB Output is correct
14 Correct 184 ms 117828 KB Output is correct
15 Correct 435 ms 118368 KB Output is correct
16 Correct 216 ms 119136 KB Output is correct
17 Correct 313 ms 117872 KB Output is correct
18 Correct 427 ms 119280 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 119108 KB Output is correct
2 Correct 508 ms 118904 KB Output is correct
3 Correct 492 ms 119492 KB Output is correct
4 Correct 310 ms 119168 KB Output is correct
5 Correct 298 ms 120672 KB Output is correct
6 Correct 369 ms 119160 KB Output is correct
7 Correct 379 ms 120036 KB Output is correct
8 Correct 450 ms 119036 KB Output is correct
9 Correct 493 ms 119032 KB Output is correct
10 Correct 252 ms 118096 KB Output is correct
11 Correct 216 ms 118140 KB Output is correct
12 Correct 317 ms 118112 KB Output is correct
13 Correct 435 ms 119544 KB Output is correct
14 Correct 281 ms 119544 KB Output is correct
15 Correct 337 ms 118196 KB Output is correct
16 Correct 342 ms 118136 KB Output is correct
17 Correct 302 ms 118648 KB Output is correct
18 Correct 511 ms 118904 KB Output is correct
19 Correct 202 ms 118136 KB Output is correct
20 Correct 517 ms 119344 KB Output is correct
21 Correct 299 ms 119612 KB Output is correct
22 Correct 555 ms 120636 KB Output is correct
23 Correct 259 ms 119772 KB Output is correct
24 Correct 155 ms 119160 KB Output is correct
25 Correct 306 ms 119216 KB Output is correct
26 Correct 272 ms 119032 KB Output is correct
27 Correct 466 ms 120020 KB Output is correct
28 Correct 177 ms 119288 KB Output is correct
29 Correct 413 ms 120692 KB Output is correct
30 Correct 446 ms 120184 KB Output is correct
31 Correct 230 ms 119136 KB Output is correct
32 Correct 244 ms 119160 KB Output is correct
33 Correct 181 ms 119032 KB Output is correct
34 Correct 334 ms 119960 KB Output is correct
35 Correct 178 ms 119288 KB Output is correct
36 Correct 531 ms 120440 KB Output is correct
37 Correct 294 ms 120568 KB Output is correct
38 Correct 343 ms 119288 KB Output is correct
39 Correct 196 ms 119224 KB Output is correct
40 Correct 313 ms 119288 KB Output is correct
41 Correct 380 ms 120056 KB Output is correct
42 Correct 346 ms 119544 KB Output is correct