http://www.usaco.org/index.php?page=viewproblem2&cpid=569&lang=en
i was trying to solve this problem, what i did is storing in a long long variable all the possible milk types that can be bad starting from every milk type, then i iterate trough all the people that got sick and at each iteration i remove from the variable all the bit representing a milk that the person didn’t drink before getting sick, this is the code:
#ifdef LOCAL
//#include "librerie locali/debugging.h"
#else
#pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < x; i++)
#define reps(i,j,x) for(int i=j;i<x;i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define maxint numeric_limits<int>::max()
#define minint numeric_limits<int>::min()
#define maxll numeric_limits<ll>::max()
#define minll numeric_limits<ll>::min()
#define f first
#define s second
#define MAXN 100001
#define mod 1000000007
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
ifstream in("badmilk.in");
ofstream out("badmilk.out");
int main() {
int n,m,d,si;
in>>n>>m>>d>>si;
ll bad = 0;
rep(i,m)bad|=(1<<i);
vector<vpi> per(n); //vector<vector<pair<int,int>>>
vpi when(si); //vector<pair<int,int>>
rep(i,d){
int a,b,c;
in>>a>>b>>c;
a--;
b--;
per[a].push_back({c,b});
}
rep(i,si){
int a,b;
in>>a>>b;
a--;
when[i]={b,a};
}
//sort(all(when));
rep(i,n)sort(all(per[i]));
rep(i,si){
int tem = 0;
int who = when[i].s;
int time = when[i].f;
rep(j,per[who].size()){
if(per[who][j].f>=time)break;
tem|=(1<<per[who][j].s);
}
bad &= tem;
}
vi ans(m);
rep(i,n){
vector<bool> add(m);
for(auto x:per[i]){
if((1<<x.s)&bad)add[x.s]=true;
}
rep(j,m)if(add[j])ans[j]++;
}
int maxi = 0;
rep(i,m)maxi=max(maxi,ans[i]);
out<<maxi;
}
i stress tested it against the official solution but it worked just right