oj.uz

Submission #217602

# Submission time Handle Problem Language Result Execution time Memory
217602 2020-03-30T10:35:50 Z BThero Ruins 3 (JOI20_ruins3) C++17
6 / 100
 2490 ms 19224 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define __DBG 1
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;

const int MOD = (int)1e9 + 7;

int cnt[15];
int pw[15];
bool my[26];
int n;

int addMod(int a, int b, int m = MOD) {
	a += b;
	
	if (m <= a) {
		a -= m;
	}
	
	return a;
}

int bit(int x, int p) {
	return (x / pw[p]) % 3;
}

void solve() {
	scanf("%d", &n);
	
	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		my[x - 1] = 1;
	}
	
	pw[0] = 1;
	
	for (int i = 1; i < 15; ++i) {
		pw[i] = pw[i - 1] * 3;
	}
	
	vector<int> dp(pw[n], 0);
	vector<int> mem(pw[n], 0);
	dp[0] = 1;
	// 2 3 3 1
	
	for (int mask = 0; mask < pw[n]; ++mask) {
		fill(cnt, cnt + n, 0);
			
		for (int j = n - 1; j >= 0; --j) {
			int c = bit(mask, j);
			cnt[j] += c;
			
			if (cnt[j] > 1) {
				if (j > 0) {
					cnt[j - 1] += cnt[j] - 1;
				}
				
				cnt[j] = 1;
			}
		}
	
		int p = 0;
		
		while (cnt[p]) {
			++p;
		}
		
		mem[mask] = p;
	}
	
	for (int i = 2 * n - 1; i >= 0; --i) {
		vector<int> ndp(pw[n], 0);
		
		for (int mask = 0; mask < pw[n]; ++mask) {
			int p = mem[mask];
			
			if (my[i]) {
				for (int j = p; j < n; ++j) {
					int c = bit(mask, j);
					
					if (c != 2) {
						int nmask = mask + pw[j];
						ndp[nmask] = addMod(ndp[nmask], dp[mask]);
					}
				}
			}
			else {
				for (int j = 0; j < p; ++j) {
					int c = bit(mask, j);
					
					if (c != 2) {
						int nmask = mask + pw[j];
						ndp[nmask] = addMod(ndp[nmask], dp[mask]);
					}
				}
			}
		}
		
		dp = ndp;
	}
	
	printf("%d\n", dp[pw[n] - 1]);
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

Compilation message

ruins3.cpp: In function 'void solve()':
ruins3.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
ruins3.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2473 ms 19096 KB Output is correct
3 Correct 2475 ms 19224 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 2462 ms 19108 KB Output is correct
6 Correct 2466 ms 19096 KB Output is correct
7 Correct 2475 ms 19096 KB Output is correct
8 Correct 2474 ms 19096 KB Output is correct
9 Correct 2477 ms 19092 KB Output is correct
10 Correct 2490 ms 19112 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2473 ms 19096 KB Output is correct
3 Correct 2475 ms 19224 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 2462 ms 19108 KB Output is correct
6 Correct 2466 ms 19096 KB Output is correct
7 Correct 2475 ms 19096 KB Output is correct
8 Correct 2474 ms 19096 KB Output is correct
9 Correct 2477 ms 19092 KB Output is correct
10 Correct 2490 ms 19112 KB Output is correct
11 Runtime error 5 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 2473 ms 19096 KB Output is correct
3 Correct 2475 ms 19224 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 2462 ms 19108 KB Output is correct
6 Correct 2466 ms 19096 KB Output is correct
7 Correct 2475 ms 19096 KB Output is correct
8 Correct 2474 ms 19096 KB Output is correct
9 Correct 2477 ms 19092 KB Output is correct
10 Correct 2490 ms 19112 KB Output is correct
11 Runtime error 5 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -