oj.uz

Submission #54120

# Submission time Handle Problem Language Result Execution time Memory
54120 2018-07-02T12:02:57 Z 0^0(#1448) Linear Garden (IOI08_linear_garden) C++11
0 / 100
 301 ms 146284 KB 
#include <bits/stdc++.h>
using namespace std;
int n, mod;
char str[1000005];
int cache[1000005][5][5];
int solve(int idx, int mins,int maxs) {
	if (mins < -2 || maxs > 2)return 0;
	if (idx == n)return 1;
	int &ret = cache[idx][mins + 2][maxs + 2];
	if (ret != -1)return ret;
	ret = solve(idx + 1, min(-1, mins - 1), max(-1, maxs - 1));
	ret += solve(idx + 1, min(1, mins + 1), max(1, maxs + 1));
	ret %= mod;
	return ret;
}
int get_ans(int idx, int mins, int maxs) {
	if (idx == n)return 1;
	if (str[idx] == 'L')return get_ans(idx + 1, min(-1, mins - 1), max(-1, maxs - 1));
	return (get_ans(idx + 1, min(1, mins + 1), max(1, maxs + 1)) + solve(idx + 1, min(-1, mins - 1), max(-1, maxs - 1))) % mod;
}
int main() {
	scanf("%d%d%s", &n, &mod, str);
	memset(cache, -1, sizeof(cache));
	solve(1, 1, 1);
	solve(1, -1, -1);
	int ans = 0;
	if (str[0] == 'L')ans = get_ans(1, -1, -1);
	else ans = (get_ans(1, 1, 1) + solve(1, -1, -1)) % mod;
	printf("%d\n", ans);
	return 0;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%s", &n, &mod, str);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 71 ms 98168 KB

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 71 ms 98280 KB

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 92 ms 98280 KB

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 74 ms 98280 KB

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 72 ms 98288 KB

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 72 ms 98476 KB

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 76 ms 98480 KB

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 73 ms 98480 KB

Subtask #9
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 72 ms 98480 KB

Subtask #10
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 84 ms 98480 KB

Subtask #11
0 / 4.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 81 ms 98480 KB

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 73 ms 98480 KB
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 81 ms 98480 KB
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 74 ms 98524 KB
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 77 ms 99304 KB

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 78 ms 99596 KB

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 86 ms 101352 KB

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 88 ms 101864 KB

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 141 ms 113324 KB

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 164 ms 117612 KB

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 198 ms 122968 KB

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 218 ms 128240 KB

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 301 ms 146284 KB
2 Halted 0 ms 0 KB -