Join Us
AlgoPath
Events
Is this correct answer?
Entering edit mode
Kevin' small talk
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[215][215];
ll DP[215][215];
ll get_idx_continious_substring(string &prefix, string &s, int idx)
{
ll cnt = 0;
int verify = 1;
while (cnt != prefix.size())
{
if (idx + cnt >= s.size())
{
verify = 0;
break;
}
if (prefix[cnt] != s[idx + cnt])
{
verify = 0;
}
cnt++;
}
if (verify == 0)
{
return 0;
}
else
{
return cnt + get_idx_continious_substring(prefix, s, idx + cnt);
}
}
ll func(ll idx, ll j, string &s)
{
if (idx == j)
{
return 1;
}
if (idx > j)
{
return 0 * 1ll;
}
if (dp[idx][j] != -1)
{
return dp[idx][j];
}
ll ans = 1ll * (s.size() - idx);
string prefix;
for (ll i = idx; i < j; i++)
{
prefix.push_back(s[i]);
ll sz = prefix.size();
ll cnt = DP[idx][i];
ll len = i - idx + 1;
ll total_size = j - idx + 1;
ll q = total_size / len;
ll nxt_idx = min(idx + cnt, idx + len * q);
// cout << idx << " " << prefix << " " << nxt_idx << endl;
ans = min(ans, min((nxt_idx - idx), 3ll + func(idx, idx + sz - 1, s)) + func(nxt_idx, j, s));
}
return dp[idx][j] = ans;
}
int main()
{
string s;
cin >> s;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < 215; i++)
{
for (int j = 0; j < 215; j++)
{
DP[i][j] = 0;
}
}
for (int i = 0; i < s.size(); i++)
{
string prefix;
for (int j = i; j < s.size(); j++)
{
prefix.push_back(s[j]);
DP[i][j] = get_idx_continious_substring(prefix, s, i);
// cout<<i<<" "<<j<<" "<<prefix<<" "<<DP[i][j]<<endl;
}
}
cout << func(0, s.size() - 1, s) << endl;
}
// string a="kjdnvdfvkddvjb"
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
long long ans[100005];
int val[100005];
long long dfs(int curr, int par){
long long res = 1;
for(auto it : adj[curr]){
if(it!=par){
res *= dfs(it,curr);
}
}
res *= val[curr];
return ans[curr] = res;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>val[i];
}
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1,-1);
int sprinklr = 0;
for(int i = 2;i<=n;i++){
// cout<<ans[i]<<endl;
if((ans[i]%6)!=0 && (ans[1]/ans[i])%6!=0){
sprinklr++;
}
}
cout<<sprinklr<<endl;
return 0;
}
Entering edit mode
0
I don't think so; Suppose the graph has 100000 nodes having value equal to 3 each. As per his dfs function he is computing product of all nodes in the subtree of a node; So node 1 will contain product of all nodes in the graph which will be equal to (3 to the power of 100000) which can't be stored in even long long.
Entering edit mode
Profit
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
long long k;
cin>>k;
long long temp = k;
int cost[n];
int sell[n];
for(int i=0;i<n;i++){
cin>>cost[i];
}
for(int i=0;i<n;i++){
cin>>sell[i];
}
vector<pair<int,int>> V;
for(int i=0;i<n;i++){
V.push_back({cost[i],sell[i]});
}
sort(V.begin(),V.end());
for(auto x : V){
if(x.first>x.second){
continue;
}
else{
if(k>= x.first){
k += (x.second - x.first);
}
else{
break;
}
}
}
cout<<k - temp<<endl;
return 0;
}
Entering edit mode
Q3.Answer
#include <bits/stdc++.h>
using namespace std;
int
main ()
{
int noOfItems;
long long initalAmnt;
cin>>noOfItems>>initalAmnt;
int cost[noOfItems];
int sell[noOfItems];
for(int i=0;i<noOfItems;i++){
cin>>cost[i]>>sell[i];
}
vector<pair<int,int>> vec;
for(int i=0;i<noOfItems;i++){
vec.push_back(make_pair(sell[i]-cost[i],i));
}
sort(vec.begin(),vec.end());
int maxProfit=0;
for(int i=0;i<vec.size();i++){
if(vec[i].first > 0 && initalAmnt >= cost[vec[i].second]){
maxProfit += vec[i].first;
initalAmnt += maxProfit;
}
}
cout<<maxProfit;
return 0;
}
Loading Similar Posts
Splitting Edges:
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> adj;
vector<int> a;
const int M = 1e5;
void dfs(int node, int par, vector<vector<int>>& dp) {
dp[node][a[node]]++;
for (int child : adj[node]) {
if (child != par) {
dfs(child, node, dp);
for (int i = 1; i <= 3; i++) {
dp[node][i] += dp[child][i];
}
}
}
}
int solve(int n) {
vector<vector<int>> dp(1e5+1, vector<int>(4, 0));
dfs(1, 0, dp);
int count = 0;
for (int i = 2; i <= n; i++) {
int c11 = dp[i][1], c12 = dp[i][2], c13 = dp[i][3];
int c21 = dp[1][1] - c11, c22 = dp[1][2] - c12, c23 = dp[1][3] - c13;
if ((c12 > 0 and c13 > 0) or (c22 > 0 and c23 > 0)) {
continue;
}
count++;
}
return count;
}
signed main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
a.resize(1e5+1);
adj.resize(1e5+1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int tmp = n;
tmp--;
while (tmp--) {
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
cout << solve(n) << endl;
}
return 0;
}
Profits:
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,k;
cin>>n>>k;
vector<int>buy(n),sell(n);
for(int i=0;i<n;i++){
cin>>buy[i];
}
for(int i=0;i<n;i++){
cin>>sell[i];
}
vector<pair<int,int>>v;
for(int i=0;i<n;i++){
v.push_back({buy[i],sell[i]});
}
int tmp=k;
for(int i=0;i<n;i++){
if(v[i].first > v[i].second)
continue;
else if(k >= v[i].first){
k += v[i].second-v[i].first;
}
}
cout<<k-tmp<<endl;
}