oj.uz

Submission #728590

# Submission time Handle Problem Language Result Execution time Memory
728590 2023-04-22T16:31:15 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 2 ms 1620 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const ll MOD=1e9+7;
ll N,M,a[105],dp[105][105][1005][3];
int main(){
	cin>>N>>M;
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	sort(a+1,a+N+1);
	a[0]=0;
	dp[0][0][0][0]=1;
	for(int i=0;i<=N-1;i++){
		for(int cc=0;cc<=N;cc++){
			for(int k=0;k<=M;k++){
				for(int e=0;e<=2;e++){
					if(2*cc-e<0){
						continue;
					}
					ll cost=(a[i+1]-a[i])*(2*cc-e);
					if(k+cost>M){
						continue;
					}
					ll cur=dp[i][cc][k][e];
					//new
					dp[i+1][cc+1][k+cost][e]+=cur;
					if(e<=1){
						dp[i+1][cc+1][k+cost][e+1]+=(2-e)*cur;
					}
					//stick
					dp[i+1][cc][k+cost][e]+=(2*cc-e)*cur;
					dp[i+1][cc][k+cost][e+1]+=(2-e)*(cc-e)*cur;
					if(i==N-1){
						dp[i+1][cc][k+cost][e+1]+=cur;
					}
					//merge
					if(cc-e>=2){
						dp[i+1][cc-1][k+cost][e]+=(cc-e)*(cc-e-1)*cur;
					}
					if(cc-e>0&&e>0){
						dp[i+1][cc-1][k+cost][e]+=(cc-e)*e*cur;
					}
					if(e==2&&i==N-1){
						dp[i+1][cc-1][k+cost][e]+=cur;
					}
					dp[i+1][cc+1][k+cost][e]%=MOD;
					dp[i+1][cc+1][k+cost][e+1]%=MOD;
					dp[i+1][cc][k+cost][e]%=MOD;
					dp[i+1][cc][k+cost][e+1]%=MOD;
					dp[i+1][cc-1][k+cost][e]%=MOD;
				}
			}
		}
	}
	ll sum=0;
	for(int i=0;i<=M;i++){
		sum+=dp[N][1][i][2];
		sum%=MOD;
	}
	cout<<sum<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 2 ms 1364 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 1 ms 1076 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -