Submission #1207727

#TimeUsernameProblemLanguageResultExecution timeMemory
1207727AmirElarbiSkyscraper (JOI16_skyscraper)C++20
15 / 100
162 ms101308 KiB
#include <bits/stdc++.h> #include <random> #define vi vector<int> #define ve vector #define ll long long #define vf vector<float> #define vll vector<pair<ll,ll>> #define ii pair<int,int> #define pll pair<ll,ll> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 2e9+5 #define eps 1e-7 #define eps1 1e-25 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 1e5+5 #define V 450 using namespace std; const int MOD = 1e9; const int MAXK = 1e9; const int lg = 20; const int N = 15; const int L = 105; const string SUBTASK = "6"; int sol1(int n, int l){ vi a; for(int i = 1; i <= n; i++) a.pb(i); int res = 0; sort(a.begin(), a.end()); do{ int sm = 0; for(int i = 0; i < n-1; i++){ sm += abs(a[i] - a[i+1]); } if(sm <= l) res++; } while(next_permutation(a.begin(), a.end())); return res; } const int mod = 1e9+7; int dp[(1 << N)][N][L]; int sol2(vi A, int n, int l){ // initialiser les cas de bases for(int i = 0; i < n; i++) dp[1 << i][i][0] = 1; for(int i = 0; i < 1<<n; i++){ // i représente les éléments déjà utilisés for(int lst = 0; lst < n; lst++){ // lst est le dernier élément qu'on a choisi pour le moment // vérifier que l'élément séléctionné est present dans le bitmask if(i & (1 << lst)) for(int cur = 0; cur < n; cur++){ // cur est l'élément qu'on va choisir pour la position suivante // vérifier qu'il n'existe pas déjà dans le bitmask if(!(i & (1 << cur))){ int cout_act = abs(A[cur]-A[lst]); for(int cst = 0; cst <= l; cst++) // cst est la somme des différences consécutifs des éléments déja présents if(cst+cout_act <= l) dp[i|(1 << cur)][cur][cst+cout_act] = (dp[i|(1 << cur)][cur][cst+cout_act] + dp[i][lst][cst])%mod; } } } } long long rep = 0; // la réponse finale est la somme des états qui ont une somme inférieur à l tels que tous les éléments sont utilisés // On ne s'intéresse pas donc au dernier élément choisi -> on somme tout les cas possibles for(int cst = 0; cst <= l; cst++) for(int lst = 0; lst < n; lst ++){ rep += dp[(1 << n)-1][lst][cst]; rep %= mod; } return rep; } int main() { int N,L; cin >> N >> L; vi A; for(int i = 0; i < N; i++){ int a; cin >> a; A.pb(a); } cout << sol2(A,N,L) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...