oj.uz

Submission #59518

# Submission time Handle Problem Language Result Execution time Memory
59518 2018-07-22T08:23:02 Z aloomya Skyscraper (JOI16_skyscraper) C++14
15 / 100
 1079 ms 188412 KB 
//in the name of Allah
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define req(i,s,e) for(int i=s;i<e;i++)
#define reqd(i,s,e,d) for(int i=s;i<e;i+=d)
#define Init ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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>;
const int MX = 20*1000 + 100,mod = 1000 * 1000 * 1000 + 7;
int dp[MX][200][20];
int inp[MX];
int d(int a, int b){
	return abs(inp[a]-inp[b]);
}
int32_t main(){
	int n,l;
	cin>>n>>l;
	req(i,0,n){
		cin>>inp[i];
	}
	int r = 1<<n;
	req(i,1,r){
		if(__builtin_popcount(i)==1){
			req(j,0,n){
				if( i  && (1<<j))
					dp[i][0][j]=1;
			}
		}else{
			req(j,1,l+1){
				req(k,0,n){
					if(i & (1<<k)){
						req(h,0,n){
							if(h!=k && i&(1<<h) && j-d(k,h)>-1){
								dp[i][j][k]= (dp[i][j][k]+ dp[i^(1<<k)][j-d(k,h)][h])%mod;
							}
						}
					}
				}
			}
		}
	}
	int ans= 0;
	req(i,0,n){
		req(j,0,l+1){
			ans =(ans+ dp[(1<<n)-1][j][i])%mod;
		}
	}
	cout<<ans<<endl;
}

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:34:17: warning: '<<' in boolean context, did you mean '<' ? [-Wint-in-bool-context]
     if( i  && (1<<j))
               ~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 4 ms 1084 KB Output is correct
5 Incorrect 32 ms 4476 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 36964 KB Output is correct
2 Correct 883 ms 185440 KB Output is correct
3 Correct 625 ms 185440 KB Output is correct
4 Correct 903 ms 186152 KB Output is correct
5 Correct 890 ms 188412 KB Output is correct
6 Correct 863 ms 188412 KB Output is correct
7 Correct 422 ms 188412 KB Output is correct
8 Correct 492 ms 188412 KB Output is correct
9 Correct 1079 ms 188412 KB Output is correct
10 Correct 798 ms 188412 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 4 ms 1084 KB Output is correct
5 Incorrect 32 ms 4476 KB Output isn't correct
6 Halted 0 ms 0 KB -