oj.uz

Submission #96510

# Submission time Handle Problem Language Result Execution time Memory
96510 2019-02-10T02:48:20 Z Retro3014 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 3 ms 508 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
#define MAX_N 100
#define MAX_L 1000
#define DIV 1000000007
typedef long long ll;

int N, L;
ll dp1[MAX_N+1][MAX_L+1][4], dp2[MAX_N+1][MAX_L+1][4];
vector<ll> v;

int main(){
	scanf("%d%d", &N, &L);
	for(int i=0; i<N; i++){
		ll x;
		scanf("%lld", &x); v.push_back(x);
	}
	dp1[0][0][0] = 1;
	sort(v.begin(), v.end());
	for(int i=0; i<N; i++){
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp1[j][k][t]==0)	continue;
					//1-1.
					ll cnt = j+1;
					if(t==1 || t==2)	cnt--;
					if(t==3)	cnt-=2;
					dp2[j+1][k][t] += (cnt * dp1[j][k][t])%DIV;
					dp2[j+1][k][t] = dp2[j+1][k][t] % DIV;
					//1-2.
					if(t==0 || t==2){
						dp2[j+1][k][t+1] += dp1[j][k][t];
						dp2[j+1][k][t+1] = dp2[j+1][k][t+1] % DIV;
					}
					//1-3.
					if(t==0 || t==1){
						dp2[j+1][k][t+2] = (dp2[j+1][k][t+2] + dp1[j][k][t]) %DIV;
					}
					//2-1.
					if(j!=0){
						cnt = j*2;
						if(t==1 || t==2)	cnt--;
						if(t==3)	cnt -= 2;
						dp2[j][k][t] = (dp2[j][k][t] + (cnt * dp1[j][k][t])%DIV)%DIV;
					}
					//2-2.
					if(j!=0 && t!=3 && t!=1){
						dp2[j][k][t+1] = (dp2[j][k][t+1] + dp1[j][k][t])%DIV;
					}
					//2-3.
					if(j!=0 && t!=2 && t!=3){
						dp2[j][k][t+2] = (dp2[j][k][t+2] + dp1[j][k][t])%DIV;
					}
					//3.
					if(j>=2){
						dp2[j-1][k][t] = (dp2[j-1][k][t] + ((ll)j-1) * dp1[j][k][t])%DIV;
					}
				}
			}
		}
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++)	dp1[j][k][t] = 0;
			}
		}
		for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp2[j][k][t]==0)	continue;
					ll K = 0;
					if(i==N-1){
						K = k;
					}else{
						ll cnt = j*2;
						if(t==1 || t==2)	cnt--;
						if(t==3)	cnt-=2;
						K = (ll)k + cnt*(v[i+1]-v[i]);
					}
					if(K>L){
						dp2[j][k][t] = 0;
					}else{
						dp1[j][K][t] = (dp1[j][K][t]+dp2[j][k][t])%DIV;
						dp2[j][k][t] = 0;
					}
				}
			}
		}
		/*for(int j=0; j<=N; j++){
			for(int k=0; k<=L; k++){
				for(int t=0; t<4; t++){
					if(dp1[j][k][t]!=0)	cout<<i<<' '<<j<<' '<<k<<' '<<t<<' '<<dp1[j][k][t]<<endl;
				}
			}
		}*/
	}
	ll ans = 0;
	for(int k=0; k<=L; k++){
		ans=(ans+dp1[1][k][3])%DIV;
	}
	printf("%lld", ans);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x); v.push_back(x);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 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 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 80.0

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