Waiting for the dawn

daily codeforces

daily codeforces

daily codeforces

daily codeforces

CF 1036C

ll dp[MAXN][MAXB];
ll a[MAXN];
ll dfs(int pos,int st,bool flag){
    if(pos==-1)return 1;
    if(dp[pos][st]!=-1&&!flag)return dp[pos][st];
    int lim=flag?a[pos]:9;
    ll ans=0;
    for(int i=0;i<=lim;++i){
        if(i==0){
            ans+=dfs(pos-1,st,flag&&a[pos]==i);
        }else if(st!=3){
            ans+=dfs(pos-1,st+1,flag&&a[pos]==i);
        }
    }
    if(!flag)dp[pos][st]=ans;
    return ans;
}
ll cal(ll x){
    int len=0;
    while(x){
        a[len++]=x%10;
        x/=10;
    }
    return dfs(len-1,0,true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    int T;
    cin>>T;
    while(T--){
        ll l,r;
        cin>>l>>r;
        cout<<cal(r)-cal(l-1)<<'\n';
    }
}

CF 1092F

int main(){
    int n;cin>>n;
    vector<ll>a(n+1),dp(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<vector<int>>E(n+1);
    for(int i=1;i<=n-1;++i){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    vector<ll>s(n+1);
    function<void(int,int)>dfs1=[&](int x,int f){
        s[x]=a[x];
        dp[x]=0;
        for(int v:E[x]){
            if(v==f)continue;
            dfs1(v,x);
            s[x]+=s[v];
            dp[x]+=dp[v]+s[v];
        }
    };
    function<void(int,int,ll)>dfs2=[&](int x,int f,ll extra){
        for(int v:E[x]){
            if(v==f)continue;
            dp[v]=(extra+s[x]-s[v])+dp[x]-s[v];//the subtree node of v would be subtraceted s[v] and other nodes would be adding s[x]-s[v];
            dfs2(v,x,extra+s[x]-s[v]);
        }
    };
    dfs1(1,0);
    dfs2(1,0,0);
    ll ans=-1;
    for(int i=1;i<=n;++i){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<'\n';
}

daily codeforces

daily codeforces

CF 1038D

int main(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    bool pos_flag=false,neg_flag=false;
    int minimal=INT_MAX;
    long long ans=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(n==1){
            cout<<a[1]<<'\n';
            return 0;
        }
        pos_flag|=(a[i]>=0);
        neg_flag|=(a[i]<=0);
        minimal=min(minimal,abs(a[i]));
        ans+=abs(a[i]);
    }
    if(pos_flag&&neg_flag){
        cout<<ans<<'\n';
    }else{
        cout<<ans-2*minimal<<'\n';
    }
    return 0;
}

CF 1133E

daily codeforces

CF 12A

for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin>>a[i][j];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(a[i][j]!=a[3-i-1][3-j-1])
            {
                cout<<"NO";
                return 0;
            }
    cout<<"YES";
    return 0;