oj.uz

Submission #101166

# Submission time Handle Problem Language Result Execution time Memory
101166 2019-03-17T07:25:47 Z autumn_eel Skyscraper (JOI16_skyscraper) C++14
20 / 100
 321 ms 91128 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int dp[1<<14][14][101];
int a[14];

int main(){
	int n,L;cin>>n>>L;
	if(n>14)abort();
	rep(i,n)scanf("%d",&a[i]);
	if(n<=8){
		vector<int>v;
		rep(i,n)v.push_back(i);
		int ans=0;
		do{
			int cnt=0;
			rep(i,v.size()-1){
				(cnt+=abs(a[v[i]]-a[v[i+1]]));
			}
			if(cnt<=L)ans++;
		}while(next_permutation(v.begin(),v.end()));
		cout<<ans<<endl;
		return 0;
	}
	rep(i,n)dp[1<<i][i][0]=1;
	rep(i,1<<n)rep(j,n){
		if(!(i>>j&1))continue;
		rep(k,L+1){
			if(dp[i][j][k]==0)continue;
			rep(t,n){
				if(i>>t&1)continue;
				if(abs(a[t]-a[j])+k<=L){
					(dp[i|1<<t][t][abs(a[t]-a[j])+k]+=dp[i][j][k])%=MOD;
				}
			}
		}
	}
	int ans=0;
	rep(i,n)rep(j,L+1)(ans+=dp[(1<<n)-1][i][j])%=MOD;
	cout<<ans<<endl;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
skyscraper.cpp:22:4: note: in expansion of macro 'rep'
    rep(i,v.size()-1){
    ^~~
skyscraper.cpp:15:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)scanf("%d",&a[i]);
          ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22904 KB Output is correct
2 Correct 142 ms 89988 KB Output is correct
3 Correct 270 ms 90908 KB Output is correct
4 Correct 148 ms 89720 KB Output is correct
5 Correct 128 ms 89840 KB Output is correct
6 Correct 280 ms 91128 KB Output is correct
7 Correct 136 ms 89544 KB Output is correct
8 Correct 262 ms 90848 KB Output is correct
9 Correct 321 ms 90932 KB Output is correct
10 Correct 141 ms 88568 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 51 ms 22904 KB Output is correct
12 Correct 142 ms 89988 KB Output is correct
13 Correct 270 ms 90908 KB Output is correct
14 Correct 148 ms 89720 KB Output is correct
15 Correct 128 ms 89840 KB Output is correct
16 Correct 280 ms 91128 KB Output is correct
17 Correct 136 ms 89544 KB Output is correct
18 Correct 262 ms 90848 KB Output is correct
19 Correct 321 ms 90932 KB Output is correct
20 Correct 141 ms 88568 KB Output is correct
21 Runtime error 4 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -