oj.uz

Submission #963273

# Submission time Handle Problem Language Result Execution time Memory
963273 2024-04-14T19:58:02 Z noobcodur Skyscraper (JOI16_skyscraper) C++14
20 / 100
 231 ms 186036 KB 
#include<bits/stdc++.h>
using namespace std;

using ld = long double;

#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;

void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}

int a[14];
vector<vector<vi>> dp;

signed main(){
	setIO("");
	int n,L;
	cin >> n >> L;

	dp = vector<vector<vi>>((1 << n),vector<vi>(n,vi(L+1))); 

	forn(i,n){
		cin >> a[i];
	}

	int res = 0;

	forrange(mask,1,1 << n){
		forn(i,n){
			if(!(mask & (1 << i))) continue;

			if(__builtin_popcount(mask) == 1){
				dp[mask][i][0] = 1;

				continue;
			}

			forn(j,n){
				if(!(mask & (1 << j)) || j == i) continue;

				int dist = abs(a[i]-a[j]);
				forn(l,L-dist+1){
					int mask2 = mask - (1 << i);

					dp[mask][i][l+dist] += dp[mask2][j][l];
					dp[mask][i][l+dist] %= MOD;
				}
			}
		}
	}

	forn(i,n){
		forn(l,L+1){
			res += dp[(1 << n)-1][i][l];
			res %= MOD;
		}
	}

	cout << res << endl;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 9 ms 15708 KB Output is correct
6 Correct 8 ms 13912 KB Output is correct
7 Correct 2 ms 2904 KB Output is correct
8 Correct 1 ms 1624 KB Output is correct
9 Correct 9 ms 14952 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 27148 KB Output is correct
2 Correct 223 ms 182440 KB Output is correct
3 Correct 138 ms 92660 KB Output is correct
4 Correct 231 ms 186036 KB Output is correct
5 Correct 229 ms 185952 KB Output is correct
6 Correct 226 ms 175184 KB Output is correct
7 Correct 90 ms 64080 KB Output is correct
8 Correct 117 ms 88916 KB Output is correct
9 Correct 186 ms 139348 KB Output is correct
10 Correct 205 ms 160900 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 9 ms 15708 KB Output is correct
6 Correct 8 ms 13912 KB Output is correct
7 Correct 2 ms 2904 KB Output is correct
8 Correct 1 ms 1624 KB Output is correct
9 Correct 9 ms 14952 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 31 ms 27148 KB Output is correct
12 Correct 223 ms 182440 KB Output is correct
13 Correct 138 ms 92660 KB Output is correct
14 Correct 231 ms 186036 KB Output is correct
15 Correct 229 ms 185952 KB Output is correct
16 Correct 226 ms 175184 KB Output is correct
17 Correct 90 ms 64080 KB Output is correct
18 Correct 117 ms 88916 KB Output is correct
19 Correct 186 ms 139348 KB Output is correct
20 Correct 205 ms 160900 KB Output is correct
21 Runtime error 3 ms 3932 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -