oj.uz

Submission #41511

# Submission time Handle Problem Language Result Execution time Memory
41511 2018-02-17T15:37:20 Z fest Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 1000 ms 12396 KB 
// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 30500, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};

int dp[N];

vector<int> have[N];

map< pair<int, int>, bool> was;

int main() {
  
	int n, m;
	scanf("%d %d", &n, &m);
	int start = 0, finish = 0;
	for (int i = 0; i < m; i++) {
		int b, p;
		scanf("%d %d", &b, &p);
		have[b].pb(p);
		was[make_pair(b, p)] = 1;
		if (i == 0) start = b;
		if (i == 1) finish = b;
	}
	for (int i = 0; i < n; i++) dp[i] = inf;
	dp[start] = 0;
	set<pair<int, int> > s;
	s.insert({0, start});
	while (!s.empty()) {
		int v = s.begin() -> S;
		s.erase(s.begin());
		for (auto p : have[v]) {
			for (int mul = 1; v + mul * p < n; mul++) {
				int u = v + mul * p;
				if (dp[u] > dp[v] + mul) {
					s.erase({dp[u], u});
					dp[u] = dp[v] + mul;
					s.insert({dp[u], u});
				}
				if (was[make_pair(u, p)]) break;
			}
			for (int mul = 1; v - mul * p >= 0; mul++) {
				int u = v - mul * p;
				if (dp[u] > dp[v] + mul) {
					s.erase({dp[u], u});
					dp[u] = dp[v] + mul;
					s.insert({dp[u], u});
				}
        if (was[make_pair(u, p)]) break;
			} 	
		}
	}
	if (dp[finish] == inf) dp[finish] = -1;
	cout << dp[finish];
	return 0;	
}

Compilation message

skyscraper.cpp: In function 'void FREOPEN()':
skyscraper.cpp:25:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".in", "r", stdin);
                                     ^
skyscraper.cpp:26:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(FILENAME".out", "w", stdout);
                                       ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
skyscraper.cpp:54:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &b, &p);
                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 2 ms 1120 KB Output is correct
3 Correct 2 ms 1192 KB Output is correct
4 Correct 2 ms 1192 KB Output is correct
5 Correct 2 ms 1192 KB Output is correct
6 Correct 2 ms 1192 KB Output is correct
7 Correct 2 ms 1296 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1296 KB Output is correct
2 Correct 2 ms 1296 KB Output is correct
3 Correct 2 ms 1296 KB Output is correct
4 Correct 2 ms 1296 KB Output is correct
5 Correct 2 ms 1296 KB Output is correct
6 Correct 2 ms 1296 KB Output is correct
7 Correct 2 ms 1296 KB Output is correct
8 Correct 3 ms 1296 KB Output is correct
9 Correct 2 ms 1296 KB Output is correct
10 Correct 2 ms 1500 KB Output is correct
11 Correct 4 ms 1520 KB Output is correct
12 Correct 5 ms 1520 KB Output is correct
13 Correct 2 ms 1520 KB Output is correct
14 Correct 4 ms 1644 KB Output is correct
15 Correct 6 ms 1644 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1644 KB Output is correct
2 Correct 2 ms 1644 KB Output is correct
3 Correct 2 ms 1644 KB Output is correct
4 Correct 2 ms 1644 KB Output is correct
5 Correct 2 ms 1644 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 2 ms 1644 KB Output is correct
8 Correct 2 ms 1644 KB Output is correct
9 Correct 2 ms 1644 KB Output is correct
10 Correct 2 ms 1644 KB Output is correct
11 Correct 4 ms 1644 KB Output is correct
12 Correct 6 ms 1644 KB Output is correct
13 Correct 2 ms 1644 KB Output is correct
14 Correct 4 ms 1644 KB Output is correct
15 Correct 4 ms 1688 KB Output is correct
16 Correct 2 ms 1688 KB Output is correct
17 Correct 9 ms 2284 KB Output is correct
18 Correct 2 ms 2284 KB Output is correct
19 Correct 2 ms 2284 KB Output is correct
20 Correct 3 ms 2284 KB Output is correct
21 Correct 3 ms 2284 KB Output is correct
22 Correct 2 ms 2284 KB Output is correct
23 Correct 5 ms 2284 KB Output is correct
24 Correct 8 ms 2284 KB Output is correct
25 Correct 9 ms 2284 KB Output is correct
26 Correct 355 ms 2284 KB Output is correct
27 Correct 296 ms 2284 KB Output is correct
28 Correct 12 ms 2796 KB Output is correct
29 Correct 41 ms 5228 KB Output is correct
30 Correct 12 ms 5228 KB Output is correct
31 Correct 18 ms 5228 KB Output is correct
32 Correct 12 ms 5228 KB Output is correct
33 Correct 78 ms 8940 KB Output is correct
34 Correct 73 ms 8940 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8940 KB Output is correct
2 Correct 2 ms 8940 KB Output is correct
3 Correct 2 ms 8940 KB Output is correct
4 Correct 2 ms 8940 KB Output is correct
5 Correct 2 ms 8940 KB Output is correct
6 Correct 2 ms 8940 KB Output is correct
7 Correct 2 ms 8940 KB Output is correct
8 Correct 3 ms 8940 KB Output is correct
9 Correct 3 ms 8940 KB Output is correct
10 Correct 3 ms 8940 KB Output is correct
11 Correct 4 ms 8940 KB Output is correct
12 Correct 5 ms 8940 KB Output is correct
13 Correct 2 ms 8940 KB Output is correct
14 Correct 4 ms 8940 KB Output is correct
15 Correct 4 ms 8940 KB Output is correct
16 Correct 2 ms 8940 KB Output is correct
17 Correct 8 ms 8940 KB Output is correct
18 Correct 3 ms 8940 KB Output is correct
19 Correct 2 ms 8940 KB Output is correct
20 Correct 3 ms 8940 KB Output is correct
21 Correct 3 ms 8940 KB Output is correct
22 Correct 2 ms 8940 KB Output is correct
23 Correct 7 ms 8940 KB Output is correct
24 Correct 11 ms 8940 KB Output is correct
25 Correct 6 ms 8940 KB Output is correct
26 Correct 329 ms 8940 KB Output is correct
27 Correct 279 ms 8940 KB Output is correct
28 Correct 10 ms 8940 KB Output is correct
29 Correct 30 ms 8940 KB Output is correct
30 Correct 9 ms 8940 KB Output is correct
31 Correct 16 ms 8940 KB Output is correct
32 Correct 12 ms 8940 KB Output is correct
33 Correct 70 ms 8940 KB Output is correct
34 Correct 80 ms 8940 KB Output is correct
35 Correct 68 ms 8940 KB Output is correct
36 Correct 11 ms 8940 KB Output is correct
37 Correct 136 ms 12396 KB Output is correct
38 Correct 121 ms 12396 KB Output is correct
39 Correct 124 ms 12396 KB Output is correct
40 Correct 125 ms 12396 KB Output is correct
41 Correct 141 ms 12396 KB Output is correct
42 Execution timed out 1077 ms 12396 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12396 KB Output is correct
2 Correct 2 ms 12396 KB Output is correct
3 Correct 2 ms 12396 KB Output is correct
4 Correct 2 ms 12396 KB Output is correct
5 Correct 3 ms 12396 KB Output is correct
6 Correct 2 ms 12396 KB Output is correct
7 Correct 2 ms 12396 KB Output is correct
8 Correct 2 ms 12396 KB Output is correct
9 Correct 2 ms 12396 KB Output is correct
10 Correct 2 ms 12396 KB Output is correct
11 Correct 4 ms 12396 KB Output is correct
12 Correct 5 ms 12396 KB Output is correct
13 Correct 3 ms 12396 KB Output is correct
14 Correct 4 ms 12396 KB Output is correct
15 Correct 4 ms 12396 KB Output is correct
16 Correct 2 ms 12396 KB Output is correct
17 Correct 8 ms 12396 KB Output is correct
18 Correct 2 ms 12396 KB Output is correct
19 Correct 2 ms 12396 KB Output is correct
20 Correct 3 ms 12396 KB Output is correct
21 Correct 3 ms 12396 KB Output is correct
22 Correct 2 ms 12396 KB Output is correct
23 Correct 5 ms 12396 KB Output is correct
24 Correct 8 ms 12396 KB Output is correct
25 Correct 6 ms 12396 KB Output is correct
26 Correct 332 ms 12396 KB Output is correct
27 Correct 284 ms 12396 KB Output is correct
28 Correct 11 ms 12396 KB Output is correct
29 Correct 34 ms 12396 KB Output is correct
30 Correct 9 ms 12396 KB Output is correct
31 Correct 17 ms 12396 KB Output is correct
32 Correct 11 ms 12396 KB Output is correct
33 Correct 72 ms 12396 KB Output is correct
34 Correct 77 ms 12396 KB Output is correct
35 Correct 70 ms 12396 KB Output is correct
36 Correct 11 ms 12396 KB Output is correct
37 Correct 145 ms 12396 KB Output is correct
38 Correct 138 ms 12396 KB Output is correct
39 Correct 127 ms 12396 KB Output is correct
40 Correct 114 ms 12396 KB Output is correct
41 Correct 144 ms 12396 KB Output is correct
42 Execution timed out 1047 ms 12396 KB Time limit exceeded
43 Halted 0 ms 0 KB -