Join Us
Loading Similar Posts
Entering edit mode
Infection Sequences
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
long long factorial(int n) {
long long result = 1;
for (int i = 1; i <= n; i++) {
result = (result * i) % MOD;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> infec(m);
for (int i = 0; i < m; i++) {
cin >> infec[i];
}
vector<bool> vis(n+1, false);
queue<int> q;
for (int x : infec) {
vis[x] = true;
q.push(x);
}
int ans = 1;
while (!q.empty()) {
int sz = q.size();
int cnt = 0;
for (int i = 0; i < sz; i++) {
int x = q.front();
q.pop();
int back = x - 1;
int front = x + 1;
if (back > 0 && back <= n && !vis[back]) {
vis[back] = true;
q.push(back);
cnt++;
}
if (front > 0 && front <= n && !vis[front]) {
vis[front] = true;
q.push(front);
cnt++;
}
}
ans = (1LL * ans * factorial(cnt)) % MOD;
}
cout << ans << endl;
}
Entering edit mode
unequal elements (tle on larger test cases)
3D dp approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int dp[205][205][205];
int f(int i, int prev, int n, int k, vector<int> &skills) {
if (i == n) {
return (k > 0);
}
if(dp[i][prev][k]!=-1)return dp[i][prev][k];
int take = 0;
if (k > 0) {
if (skills[i] == prev) {
take = 1 + f(i + 1, skills[i], n, k, skills);
} else {
take = 1 + f(i + 1, skills[i], n, k - 1, skills);
}
}
int not_take = f(i + 1, prev, n, k, skills);
return dp[i][prev][k] = max(take, not_take);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
memset(dp,-1,sizeof(dp));
int n, k;
cin >> n >> k;
vector<int> skills(n);
for (int i = 0; i < n; i++) {
cin >> skills[i];
}
if (n == 0) {
cout << 0 << endl;
} else {
cout << f(0, skills[0], n, k, skills) << endl;
}
}
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define endl "\n"
int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
int mminvprime(int a, int b) {return expo(a, b - 2, b);}
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}
bool check_composite(int a, int n){int s=0,d=n-1;while(d%2==0){s++;d/=2;}int exp=expo(a,d,n);if(exp==1||exp==n-1)return false;while(s--){exp=mod_mul(exp,exp,n);if(exp==n-1)return false;}return true;}
bool isPrime(int n){if(n<4)return n==2||n==3;if(n%2==0)return false;for(auto x:{2,3,5,7,11,13,17,19,23,29,31,37})if(x<n&&check_composite(x,n))return false;return true;}
int f(int a , int c , int n){return (mod_mul(a , a ,n) % n + c % n) % n;}
int rho(int n , int x0 , int c){if(n % 2 == 0){return (int)2;}int x = x0;int y = x0;int g = 1;while(g == 1){x = f(x , c , n);y = f(y , c , n);y = f(y , c , n);int num = (x >= y ? x - y : y - x);g = __gcd( num , n);}if(g == n) return rho(n , x0 + 1 , c + 1);return g;}
void readBigInt(int &x) {string s; cin >> s;x = 0;for(char c : s) x = x * 10 + (c - '0');}
void printBigInt(int x) {if (x == 0) { cout << "0"; return; }string s = "";while (x > 0) {s += (char)('0' + x % 10);x /= 10;}reverse(s.begin(), s.end());cout << s;}
const int M1 = 1e9 + 7;
const int M2 = 998244353;
const int inf = 1e9;
#ifndef ONLINE_JUDGE
#include "template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
// ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//
int32_t main(){
fastio;
int t;
t=1;
while(t--){
int n;
cin >> n ;
int k;
cin >> k;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
}
//dp[i][x] -> me esa subseq ending at ith pos aur atmost x adj unequal max length of such subsequence
//ans -> dp[n][k]
//pref[j] -> abhi tak iteration usme agar atmost j adj unequal usme length kitni ho skti hai
// 5 index pref[j] -> max(dp[1][j],dp[2][j],....,dp[5][j]);
vector<vector<int>> dp(n+1,vector<int> (k+1,0));
map<int,int>prev_pos;
vector<int>pref(k+1,0);
int ans =0 ;
//pref[j-1] -> max(dp[1][j-1], ..... dp[i-1][j-1])
for(int i=1;i<=n;i++) {
for(int j=0;j<=k;j++){
//case 1 : me ith index le raha hu ki isse pehle wo a[i] ke barabar nhi ho
dp[i][j] = 1 +( (j==0)?0:pref[j-1] );
//case 2 : me ith index par a[i] ke barabar hoga
if(prev_pos.find(a[i]) != prev_pos.end()){
dp[i][j] = max(dp[i][j] , 1 + dp[prev_pos[a[i]]][j]);
}
else dp[i][j] = max(dp[i][j] , 1);
ans = max(ans, dp[i][j]);
}
prev_pos[a[i]] = i;
for(int j=0;j<=k;j++){
pref[j] = max(pref[j],dp[i][j]);
}
// cout<<pref[0]<<endl;
}
cout<<ans<<endl;
}
// 5 6 7 5 8 9 5
}
