PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming
PROBLEM
There are N chapters and only K minutes are left before the exam. Chapter i will be worth M_i marks in the paper, and shall take T_i minutes to prepare. Chef can study the chapters in any order but need to study them completely and atmost once. He knows that he will forget the first chapter that he will prepare (due to lack of sleep) and won’t be able to score any marks in it. Find the maximum marks that Chef can score in the exam.
EXPLANATION:
Since our goal is to maximize the Chef score, and we know that the Chef will forget the first chapter he prepares due to lack of sleep. So whatever the set of chapters Chef plans to prepare in given time, he will always prepare the chapter first which has minimum marks among the set of chapters he chooses.
We can use Dynamic Programming to find the maximum marks Chef can score in the given exam. Let’s move towards it:
-
DP[0][j] denotes the maximum marks that Chef can prepare in j minutes such that he doesn’t forgot any chapter.
-
DP[1][j] denotes the maximum marks that Chef can prepare in j minutes such that he will forgot exactly one chapter.
Suppose Chef wants to prepare the i^{th} chapter which takes t time to completely prepare it. So the maximum time Chef can start preparing this chapter such that he can prepare this chapter within the time is (k-t). Hence Chef can start preparing i^{th} chapter from any time in [0, k-t] endpoints inclusive.
Let j be the time Chef starts preparing for the i^{th} chapter which takes t time to prepare and carries m marks. Hence the transition will be as follows:
and
Here DP[0][j] is the maximum marks which Chef can score in j time when i^{th} chapter is not included yet and Chef doesn’t forgets any chapter he prepares.
And, DP[1][j] is the maximum marks which Chef can score in j time when i^{th} chapter is not included yet and Chef forgets the first chapter he prepares.
We need to carefully set the initial state of the DP's.
Finally, DP[1][K] will be the maximum score that Chef can score in K minutes when he forgot the first chapter he prepares.
TIME COMPLEXITY:
O(N*K) per test case
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pii pair<int, int>
using namespace std;
const int maxn = 1e3;
const int maxt = 1e4;
const int maxp = 1e9;
ll dp[2][2][maxt + 10];
int main()
{
int t; cin >> t;
int n, time;
while(t--){
cin >> n >> time;
int t = 0;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < maxt + 10; k++){
if(i + j == 2)dp[i][j][k] = -maxp - 100;
else dp[i][j][k] = 0;
}
}
}
for(int i = 0; i < n; i++){
int marks, rtime; cin >> marks >> rtime;
for(int j = 0; j <= time; j++){
dp[t][0][j] = max(dp[1 - t][0][j], j >= rtime ? dp[1 - t][0][j - rtime] + marks : 0);
dp[t][1][j] = max(dp[1 - t][1][j], j >= rtime ? max(dp[1 - t][1][j - rtime] + marks, dp[1 - t][0][j - rtime]) : -maxp - 100);
}
t = 1 - t;
}
ll ans = dp[1 - t][1][time];
cout << ans << endl;
}
}
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll,ll> pll;
#define double long double
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b>0) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sum_nk=0;
void solve() {
int n=readIntSp(1,1000),k=readIntLn(1,10000);
sum_nk+=n*k;
assert(sum_nk<=10'000'000);
vector<vector<int>> dp(2,vi(k+1,-infl));
dp[0][0]=0;
fr(i,1,n) {
int m=readIntSp(1,1000'000'000),t=readIntLn(1,k);
for(int j=k-t; j>=0; j--) {
dp[1][j+t]=max(dp[1][j+t],dp[1][j]+m);
dp[0][j+t]=max(dp[0][j+t],dp[0][j]+m);
dp[1][j+t]=max(dp[1][j+t],dp[0][j]);
}
}
cout<<*max_element(all(dp[1]))<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(1);
int t=readIntLn(1,10);
// cin>>t;
fr(i,1,t)
solve();
// assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialsit
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n,k;
cin>>n>>k;
int weight[n],time[n];
for(int i=0;i<n;i++)
cin>>weight[i]>>time[i];
int dp[2][k+1];
for(int i=0;i<2;i++)
{
for(int j=0;j<=k;j++)
{
if(i==0)
dp[i][j]=0;
else
dp[i][j]=INT_MIN;
}
}
for(int i=0;i<n;i++)
{
int temp=time[i];
for(int j=k-temp;j>=0;j--)
{
dp[0][j+temp]=max(dp[0][j+temp],weight[i]+dp[0][j]);
dp[1][j+temp]=max({dp[1][j+temp],weight[i]+dp[1][j],dp[0][j]});
}
}
cout<<dp[1][k]<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}