oj.uz

답안 #369412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369412 2021-02-21T15:21:29 Z Sparky_09 Skyscraper (JOI16_skyscraper) C++14
15 / 100
 1 ms 748 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

int rd() {
	int result = 0;
	char ch;
	ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	return result;
}

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}

int a[102];
ll dp[102][102][1002][3];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
  const ll mod = 1e9+7;
  int n, l; cin>>n>>l;
  rep(i, 1, n+1) cin >> a[i];
  sort(a+1, a+n+1);
  a[n+1] = 10000; 
  dp[0][0][0][0] = 1;
  rep(i,1,n+1)
  	rep(j,1,i+1)
  		rep(k,0,l+1)
  			rep(m,0,3){
  				int cd =(2*j-m)*(a[i+1]-a[i]); if(cd>k or i+j+1-m>n) continue;
  			  dp[i][j][k][m] += dp[i-1][j-1][k-cd][m];
  			  dp[i][j][k][m] +=(2 * j - m) * dp[i - 1][j][k - cd][m];
  			  if(m) dp[i][j][k][m] +=(3 - m) * dp[i - 1][j - 1][k - cd][m - 1];
					if(m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - cd][m - 1];
					if(m == 2){
						if(i == n) dp[i][j][k][m] += dp[i - 1][j][k - cd][m - 1];
						else if(j > 1) dp[i][j][k][m] +=(j - 1) * dp[i - 1][j][k - cd][m - 1];
					}
					if(m == 2) {
						if(i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - cd][m];
						else dp[i][j][k][m] += j *(j - 1) * dp[i - 1][j + 1][k - cd][m];
					} 
					else if(m == 1) dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - cd][m]; 
					else dp[i][j][k][m] += j *(j + 1) * dp[i - 1][j + 1][k - cd][m];
					dp[i][j][k][m] %= mod;
				}
	ll ans = 0;
	for(int i = 0; i <= l; i++) ans += dp[n][1][i][2];
	cout << ans % mod;
}

Compilation message

skyscraper.cpp: In function 'void usaco(std::string)':
skyscraper.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -