The problem 44E has a DP tag. I tried to find a solution using DP for it but was hitting a dead end and no one seems to have done it with that approach.
It would be a great help if someone could try and solve through this approach.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
The problem 44E has a DP tag. I tried to find a solution using DP for it but was hitting a dead end and no one seems to have done it with that approach.
It would be a great help if someone could try and solve through this approach.
My DP code for the question https://mirror.codeforces.com/problemset/problem/1189/C is given below. The answer for the first test case is giving 3 1 0 on my pc and ideone but 1 1 0 on codeforces. Im unable to find how the index is going out of bounds which might be causing the error. otherwise it's something totally new.
Please Help.
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_pbds;
using namespace std::chrono;
#define int long long
#define ld long double
#define mod1 1000000007
#define mod2 998244353
#define pi 3.14159265358979323846
//#define hs 100006
#define inf 1e18
#define ninf -1*(1e18)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vc vector
#define pii pair<int,int>
#define msi map<string,int>
#define mii map<int,int>
#define psi pair<string,int>
#define pis pair<int,string>
#define endl "\n"
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define bac(i,a,b) for(int i=a;i>b;i--)
#define bace(i,a,b) for(int i=a;i>=b;i--)
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n) std::cout << std::fixed << std::setprecision(n)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define REVERSE(v) reverse(ALL(v))
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define init(x,a) memset(x,a,sizeof(x))
#define trav(a, x) for(auto& a : x)
#define display(x) trav(a,x) cout<<a<<" "; cout<<endl
#define pow(i,n) (int)pow((int)i,n)
#define pow2(n) ((int)1<<n)
void solve()
{
int n;
cin>>n;
vc<int> v(n);
rep(i,0,n) cin>>v[i];
int maxseg = n,maxtimes = (log(n))/(log(2))+1;
pii dp[maxtimes][maxseg];
rep(i,0,maxtimes){
rep(j,0,maxseg)
dp[i][j].fi=0,dp[i][j].se=0;
}
rep(i,0,n) dp[0][i].fi=0, dp[0][i].se = v[i];
rep(i,1,maxtimes){
int t = pow2(i);
int lol = t/2;
repe(j,0,n-t){
dp[i][j].fi = dp[i-1][j].fi + dp[i-1][j+lol].fi;
dp[i][j].fi+=((dp[i-1][j].se+dp[i-1][j+lol].se)/10);
dp[i][j].se = (dp[i-1][j].se+dp[i-1][j+lol].se)%10;
}
}
int q;
cin>>q;
int l,r;
rep(i,0,q){
cin>>l>>r;
int huh = r-l+1;
int sz = log(huh)/log(2);
cout<<dp[sz][l-1].fi<<endl;
}
}
signed main(){
ios
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int q=1;
//cin>>q;
while(q--){
solve();
}
return 0;
}
Name |
---|