#include<stdio.h> typedef long long ll; ll min(ll a,ll b) { if(a<=b) return a; else return b; } int main() { ll t,n,k; scanf("%lld",&t); ll dp[102]; ll ar[102]; while(t--) { scanf("%lld%lld",&n,&k); for(ll i=1;i<=k;i++) scanf("%lld",&ar[i]); for(ll i=1;i<=k;i++) dp[i]=-1; dp[0]=0; for(ll i=1;i<=k;i++) { for(ll j=1;j<=k;j++) { if(i>=j) { if(dp[i]==-1 && dp[i-j]!=-1 && ar[j]!=-1) dp[i]=ar[j]+dp[i-j]; else if(dp[i-j]!=-1 && ar[j]!=-1) dp[i]=min(dp[i],ar[j]+dp[i-j]); } } } if(dp[k]!=-1) printf("%lld\n",dp[k]); else printf("-1\n"); } return 0; }
Author: vsanjayvyas
SPOJ – ABA12C – Buying Apples!
#include<stdio.h> #define INF 1000000000000 typedef long long ll; ll min(ll a,ll b) { if(a>=b) return b; else return a; } ll dp[103][103]; int main() { ll t,n,k; ll p[103]; scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&k); for(ll i=1;i<=k;i++) scanf("%lld",&p[i]); for(ll i=0;i<=k;i++) dp[i][0]=INF; for(ll i=1;i<=k;i++) { for(ll j=1;j<=k;j++) dp[i][j]=INF; } for(ll i=0;i<=k;i++) dp[0][i]=0; dp[0][0]=0; for(ll i=1;i<=k;i++) { for(ll j=1;j<=k;j++) { dp[i][j]=-1; if(j>i || p[j]==-1) dp[i][j]=dp[i][j-1]; else { if(dp[i-j][j]!=INF) dp[i][j]=min(dp[i][j-1],p[j]+dp[i-j][j]); } } } if(dp[k][k]!=-1) printf("%lld\n",dp[k][k]); else printf("-1\n"); } return 0; }
SPOJ -PIGBANK – Piggy-Bank
#include<stdio.h> typedef long long ll; ll min(ll a,ll b) { if(a<=b) return a; else return b; } int main() { ll t,a,b; ll v[505],w[505]; scanf("%lld",&t); ll dp[10002]; while(t--) { scanf("%lld%lld",&a,&b); ll n; ll k=b-a; scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld%lld",&v[i],&w[i]); for(ll i=1;i<=k;i++) dp[i]=-1; for(ll i=1;i<=k;i++) { for(ll j=1;j<=n;j++) { if(i>=w[j]) { if(dp[i]==-1 && dp[i-w[j]]!=-1) dp[i]=v[j]+dp[i-w[j]]; else if(dp[i-w[j]]!=-1) dp[i]=min(dp[i],v[j]+dp[i-w[j]]); } } } if(dp[k]==-1) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[k]); } return 0; }
SPOJ – RPLC – Coke madness
#include<stdio.h> typedef long long ll; ll ar[1000002]; int main() { ll t,n,i,f=1; scanf("%lld",&t); while(t--) { scanf("%lld",&n); for(i=0;i<n;i++) scanf("%lld",&ar[i]); ll ans=0; ll sum=0; for(i=0;i<n;i++) { sum=sum+ar[i]; if(sum<=0) { ans=ans+((-1)*sum)+1; sum=1; } } if(ans==0) ans++; printf("Scenario #%lld: %lld\n",f++,ans); } return 0; }
SPOJ – RPLB – Blueberries
#include<stdio.h> typedef int ll; ll max(ll a,ll b) { if(a>b) return a; else return b; } ll bb[1002]; ll dp[1002][1002]; int main() { ll t,n,k,f=1; scanf("%lld",&t); while(t--) { scanf("%d%d",&n,&k); for(ll i=2;i<=n+1;i++) scanf("%d",&bb[i]); for(ll i=2;i<=n+1;i++) { for(ll j=0;j<=k;j++) { if(j==0) dp[i][j]=0; else { if(bb[i]<=j) dp[i][j]=max(bb[i]+dp[i-2][j-bb[i]],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } } printf("Scenario #%d: %d\n",f++,dp[n+1][k]); } return 0; }
SPOJ – LKS – Large Knapsack
#include<stdio.h> typedef int ll; ll max(ll a,ll b) { if(a>b) return a; else return b; } ll ts,n; ll w[505],v[505]; ll dp[2][2000002]; int main() { scanf("%d%d",&ts,&n); ll i; for(i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); ll j; ll cur=1,prev=0; for(i=1;i<=n;i++) { for(j=0;j<=ts;j++) { if(j==0) dp[cur][j]=0; else { if(w[i]<=j) dp[cur][j]=max(v[i]+dp[prev][j-w[i]],dp[prev][j]); else dp[cur][j]=dp[prev][j]; } } cur=1-cur; prev=1-prev; } printf("%d\n",dp[n&1][ts]); }
SPOJ – KNAPSACK – The Knapsack Problem
-
#include<stdio.h>
#include<iostream>#include<string>#define sci(x) scanf(“%d”,&x)#define scll(x) scanf(“%lld”,&x)#define pfi(x) printf(“%d”,x)#define pfll(x) printf(“%lld”,x)#define ch(x) scanf(“%c”,&x)using namespace std;typedef long long ll;/*float stof(const string& str, size_t *idx = 0);double stod(const string& str, size_t *idx = 0);long double stold(const string& str, size_t *idx = 0);int stoi(const string& str, size_t *idx = 0, int base = 10);long stol(const string& str, size_t *idx = 0, int base = 10);unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);long long stoll(const string& str, size_t *idx = 0, int base = 10);unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */ll max(ll a,ll b){if(a>b)return a;elsereturn b;}ll n;ll dp[2002][2002];ll s[2003];ll v[2003];ll ks(ll idx,ll rs){if(idx==n || rs==0)return 0;if(dp[idx][rs]!=-1)return dp[idx][rs];if(s[idx]<=rs)return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));if(s[idx]>rs)return dp[idx][rs]=ks(idx+1,rs);}int main(){ll si;scll(si);scll(n);ll i,j;for(i=0;i<=2000;i++){for(j=0;j<=2000;j++)dp[i][j]=-1;}for(i=0;i<n;i++){scll(s[i]);scll(v[i]);}ll k=ks(0,si);pfll(k);return 0;}
SPOJ – WACHOVIA – Wachovia Bank
-
#include<stdio.h>
-
#include<iostream>
-
#include<string>
-
#define sci(x) scanf(“%d”,&x)
-
#define scll(x) scanf(“%lld”,&x)
-
#define pfi(x) printf(“%d”,x)
-
#define pfll(x) printf(“%lld”,x)
-
#define ch(x) scanf(“%c”,&x)
-
using namespace std;
-
typedef long long ll;
-
/*float stof(const string& str, size_t *idx = 0);
-
double stod(const string& str, size_t *idx = 0);
-
long double stold(const string& str, size_t *idx = 0);
-
int stoi(const string& str, size_t *idx = 0, int base = 10);
-
long stol(const string& str, size_t *idx = 0, int base = 10);
-
unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
-
long long stoll(const string& str, size_t *idx = 0, int base = 10);
-
unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
-
ll max(ll a,ll b)
-
{
-
if(a>b)
-
return a;
-
else
-
return b;
-
}
-
ll n;
-
ll dp[52][1002];
-
ll s[2003];
-
ll v[2003];
-
ll ks(ll idx,ll rs)
-
{
-
if(idx==n || rs==0)
-
return 0;
-
if(dp[idx][rs]!=-1)
-
return dp[idx][rs];
-
if(s[idx]<=rs)
-
return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
-
if(s[idx]>rs)
-
return dp[idx][rs]=ks(idx+1,rs);
-
}
-
int main()
-
{
-
ll si;ll t;
-
scll(t);
-
while(t–)
-
{
-
scll(si);
-
scll(n);
-
ll i,j;
-
for(i=0;i<=50;i++)
-
{
-
for(j=0;j<=1000;j++)
-
dp[i][j]=-1;
-
}
-
for(i=0;i<n;i++)
-
{
-
scll(s[i]);scll(v[i]);
-
}
-
ll k=ks(0,si);
-
}
-
return 0;
-
}
SPOJ – PARTY – Party Schedule
-
#include<stdio.h>
-
#include<iostream>
-
#include<string>
-
#define sci(x) scanf(“%d”,&x)
-
#define scll(x) scanf(“%lld”,&x)
-
#define pfi(x) printf(“%d”,x)
-
#define pfll(x) printf(“%lld”,x)
-
#define ch(x) scanf(“%c”,&x)
-
using namespace std;
-
typedef long long ll;
-
/*float stof(const string& str, size_t *idx = 0);
-
double stod(const string& str, size_t *idx = 0);
-
long double stold(const string& str, size_t *idx = 0);
-
int stoi(const string& str, size_t *idx = 0, int base = 10);
-
long stol(const string& str, size_t *idx = 0, int base = 10);
-
unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
-
long long stoll(const string& str, size_t *idx = 0, int base = 10);
-
unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
-
ll max(ll a,ll b)
-
{
-
if(a>b)
-
return a;
-
else
-
return b;
-
}
-
ll n;
-
ll dp[101][502];
-
ll s[2003];
-
ll v[2003];
-
ll ks(ll idx,ll rs)
-
{
-
if(idx==n || rs==0)
-
return 0;
-
if(dp[idx][rs]!=-1)
-
return dp[idx][rs];
-
if(s[idx]<=rs)
-
return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
-
if(s[idx]>rs)
-
return dp[idx][rs]=ks(idx+1,rs);
-
}
-
int main()
-
{
-
ll si;
-
{
-
ll i,j;
-
for(i=0;i<=100;i++)
-
{
-
for(j=0;j<=500;j++)
-
dp[i][j]=-1;
-
}
-
for(i=0;i<n;i++)
-
{
-
scll(s[i]);scll(v[i]);
-
}
-
ll k=ks(0,si);
-
ll low=0,high=si,mid;
-
while(low<high)
-
{
-
mid=(low+high)/2;
-
if(ks(0,mid)<k)
-
low=mid+1;
-
else
-
high=mid;
-
}
-
}
-
return 0;
-
}
SPOJ – ABSYS- Anti-Blot System
#include<stdio.h> #include<iostream> #include<string> using namespace std; typedef long long ll; /*float stof(const string& str, size_t *idx = 0); double stod(const string& str, size_t *idx = 0); long double stold(const string& str, size_t *idx = 0); int stoi(const string& str, size_t *idx = 0, int base = 10); long stol(const string& str, size_t *idx = 0, int base = 10); unsigned long stoul(const string& str, size_t *idx = 0, int base = 10); long long stoll(const string& str, size_t *idx = 0, int base = 10); unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */ int main() { string a,b,c; char a1,b1; ll t; cin >>t; while(t--) { cin >>a>>a1>>b>>b1>>c; ll k,i; for(i=0;i<a.size();i++) { if(a[i]=='m') { k=0; break; } } for(i=0;i<b.size();i++) { if(b[i]=='m') { k=1; break; } } for(i=0;i<c.size();i++) { if(c[i]=='m') { k=2; break; } } if(k==0) cout << stoll(c)-stoll(b)<< " + "<<b<< " = "<< c << endl; else if(k==1) cout << a<< " + "<<stoll(c)-stoll(a)<< " = "<<c<< endl; else cout << a<< " + "<<b<< " = "<<stoll(a)+stoll(b)<< endl; } return 0; }