oj.uz

Submission #217598

# Submission time Handle Problem Language Result Execution time Memory
217598 2020-03-30T10:31:37 Z BThero Ruins 3 (JOI20_ruins3) C++17
0 / 100
 6000 ms 12836 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);
	dp[0] = 1;
	// 2 3 3 1
	
	for (int i = 2 * n - 1; i >= 0; --i) {
		vector<int> ndp(pw[n], 0);
		
		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;
			}
			
			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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 6092 ms 12836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 6092 ms 12836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 6092 ms 12836 KB Time limit exceeded
3 Halted 0 ms 0 KB -