oj.uz

Submission #553873

# Submission time Handle Problem Language Result Execution time Memory
553873 2022-04-27T08:27:52 Z pavement Lamps (JOI19_lamps) C++17
4 / 100
 928 ms 207840 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, mem[1000005][16];
bool A[1000005], B[1000005];
char C;

// 0: 
// 1: 0
// 2: 1
// 3: T
// 4: 01
// 5: 10
// 6: 0T
// 7: T0
// 8: 1T
// 9: T1
// 10: 01T
// 11: 0T1
// 12: 10T
// 13: 1T0
// 14: T01
// 15: T10

string S[] = {"", "0", "1", "T", "01", "10", "0T", "T0", "1T", "T1", "01T", "0T1", "10T", "1T0", "T01", "T10"};

bool apply(bool x, int b) {
	if (b == 0) return x;
	else if (b == 1 || b == 5 || b == 7 || b == 8 || b == 10 || b == 13 || b == 15) return 0;
	else if (b == 2 || b == 4 || b == 6 || b == 9 || b == 11 || b == 12 || b == 14) return 1;
	else return !x;
}

int cst(int a, int b) {
	int lcp = 0;
	for (int i = 0; i < min(S[a].size(), S[b].size()); i++)
		if (S[a][i] == S[b][i]) lcp = i + 1;
		else break;
	return S[b].size() - lcp;
}

int dp(int n, int b) {
	if (n == N + 1) return 0;
	if (mem[n][b] != -1) return mem[n][b];
	int ret = LLONG_MAX;
	for (int nb = 0; nb < 16; nb++)
		if (apply(A[n], nb) == B[n]) ret = min(ret, dp(n + 1, nb) + cst(b, nb));
	return mem[n][b] = ret;
}

main() {
	memset(mem, -1, sizeof mem);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> C;
		A[i] = C == '1';
	}
	for (int i = 1; i <= N; i++) {
		cin >> C;
		B[i] = C == '1';
	}
	cout << dp(1, 0) << '\n';
}

Compilation message

lamp.cpp: In function 'long long int cst(long long int, long long int)':
lamp.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
   61 |  for (int i = 0; i < min(S[a].size(), S[b].size()); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp: At global scope:
lamp.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main() {
      | ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125560 KB Output is correct
2 Correct 48 ms 125556 KB Output is correct
3 Correct 47 ms 125536 KB Output is correct
4 Correct 49 ms 125532 KB Output is correct
5 Correct 47 ms 125516 KB Output is correct
6 Correct 50 ms 125480 KB Output is correct
7 Correct 47 ms 125500 KB Output is correct
8 Correct 49 ms 125508 KB Output is correct
9 Correct 49 ms 125524 KB Output is correct
10 Correct 47 ms 125444 KB Output is correct
11 Correct 47 ms 125556 KB Output is correct
12 Correct 48 ms 125500 KB Output is correct
13 Correct 49 ms 125512 KB Output is correct
14 Correct 51 ms 125460 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 51 ms 125552 KB Output is correct
17 Correct 48 ms 125488 KB Output is correct
18 Correct 53 ms 125488 KB Output is correct
19 Correct 53 ms 125520 KB Output is correct
20 Correct 49 ms 125564 KB Output is correct
21 Correct 49 ms 125468 KB Output is correct
22 Correct 47 ms 125548 KB Output is correct
23 Correct 50 ms 125528 KB Output is correct
24 Correct 50 ms 125644 KB Output is correct
25 Correct 49 ms 125528 KB Output is correct
26 Incorrect 48 ms 125464 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125560 KB Output is correct
2 Correct 48 ms 125556 KB Output is correct
3 Correct 47 ms 125536 KB Output is correct
4 Correct 49 ms 125532 KB Output is correct
5 Correct 47 ms 125516 KB Output is correct
6 Correct 50 ms 125480 KB Output is correct
7 Correct 47 ms 125500 KB Output is correct
8 Correct 49 ms 125508 KB Output is correct
9 Correct 49 ms 125524 KB Output is correct
10 Correct 47 ms 125444 KB Output is correct
11 Correct 47 ms 125556 KB Output is correct
12 Correct 48 ms 125500 KB Output is correct
13 Correct 49 ms 125512 KB Output is correct
14 Correct 51 ms 125460 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 51 ms 125552 KB Output is correct
17 Correct 48 ms 125488 KB Output is correct
18 Correct 53 ms 125488 KB Output is correct
19 Correct 53 ms 125520 KB Output is correct
20 Correct 49 ms 125564 KB Output is correct
21 Correct 49 ms 125468 KB Output is correct
22 Correct 47 ms 125548 KB Output is correct
23 Correct 50 ms 125528 KB Output is correct
24 Correct 50 ms 125644 KB Output is correct
25 Correct 49 ms 125528 KB Output is correct
26 Incorrect 48 ms 125464 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125456 KB Output is correct
2 Correct 50 ms 125488 KB Output is correct
3 Correct 49 ms 125444 KB Output is correct
4 Correct 49 ms 125536 KB Output is correct
5 Correct 48 ms 125488 KB Output is correct
6 Correct 48 ms 125448 KB Output is correct
7 Correct 928 ms 207828 KB Output is correct
8 Correct 909 ms 207752 KB Output is correct
9 Correct 925 ms 207732 KB Output is correct
10 Correct 916 ms 207840 KB Output is correct
11 Correct 916 ms 207812 KB Output is correct
12 Correct 898 ms 207824 KB Output is correct
13 Correct 899 ms 207772 KB Output is correct
14 Correct 916 ms 207820 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125560 KB Output is correct
2 Correct 48 ms 125556 KB Output is correct
3 Correct 47 ms 125536 KB Output is correct
4 Correct 49 ms 125532 KB Output is correct
5 Correct 47 ms 125516 KB Output is correct
6 Correct 50 ms 125480 KB Output is correct
7 Correct 47 ms 125500 KB Output is correct
8 Correct 49 ms 125508 KB Output is correct
9 Correct 49 ms 125524 KB Output is correct
10 Correct 47 ms 125444 KB Output is correct
11 Correct 47 ms 125556 KB Output is correct
12 Correct 48 ms 125500 KB Output is correct
13 Correct 49 ms 125512 KB Output is correct
14 Correct 51 ms 125460 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 51 ms 125552 KB Output is correct
17 Correct 48 ms 125488 KB Output is correct
18 Correct 53 ms 125488 KB Output is correct
19 Correct 53 ms 125520 KB Output is correct
20 Correct 49 ms 125564 KB Output is correct
21 Correct 49 ms 125468 KB Output is correct
22 Correct 47 ms 125548 KB Output is correct
23 Correct 50 ms 125528 KB Output is correct
24 Correct 50 ms 125644 KB Output is correct
25 Correct 49 ms 125528 KB Output is correct
26 Incorrect 48 ms 125464 KB Output isn't correct
27 Halted 0 ms 0 KB -