#include #include #include #include #include #include #include using namespace std; typedef unsigned int uint; typedef unsigned long long LL; typedef pair PDBL; #define FOR(k,a,b) for(uint k(a); k < (b); ++k) #define REP(k,a) for(uint k=0; k < (a); ++k) #define EPS 1e-9 #define INF 1e9 struct EDGE { int from; int to; int capacity; int flow; EDGE(int _from, int _to, int _capacity): from(_from), to(_to), capacity(_capacity), flow(0){} int res(bool rev) const {return rev? flow : capacity - flow; } }; bool bfs(int N, const vector& edges, const vector >& nodesEdges, vector& dist) { vector q(1); dist.resize(N,-1); dist[0] = 0; REP(i,q.size()) { if(dist[1]!=-1) break; int act = q[i]; const vector& acte = nodesEdges[act]; REP(i, acte.size()) { int id = acte[i]; bool rev = id < 0; if(rev) id = - id -1; else --id; int to = rev ? edges[id].from : edges[id].to; if(dist[to] == -1 && edges[id].res(rev)) { q.push_back(to); dist[to] = dist[act]+1; } } } return dist[1]!=-1; } int dfs(int node, int flow, vector& checkEdges, vector& edges, const vector >& nodesEdges,const vector& dist) { if( !flow ) return 0; if( node == 1 ) return flow; while( checkEdges[node] < nodesEdges[node].size()) { int id = nodesEdges[node][checkEdges[node]]; bool rev = id < 0; if(rev) id = - id -1; else --id; int to = rev ? edges[id].from : edges[id].to; if(dist[to] == dist[node] +1) { int pushed = dfs(to, min(flow, edges[id].res(rev)), checkEdges, edges, nodesEdges, dist); if(pushed) { edges[id].flow += pushed; return pushed; } } ++checkEdges[node]; } return 0; } int main (int argc, char** argv) { #ifdef HOME freopen("in.txt","rb",stdin); freopen("out.txt","wb",stdout); #endif int P, D, N, H, LTb, LTe; // P - Person, D - days, N workinghours / day, H hour // LT lunching time scanf("%d %d %d %d",&P, &D, &N, &H); vector L(P); // L working hours / week REP(i,P) scanf("%d",&L[i]); scanf("%d %d",<b, <e); --LTb;--LTe; vector > R(D,vector (N)); //number of clients / hour vector > > F(P,vector > (D,vector (N))); // 0 - meeting, 1 - available int sumr = 0; REP(i,D) { REP(j,N) { scanf("%d",&R[i][j]); sumr+=R[i][j]; } } vector > WN(P,vector (D)); REP(p,P) { REP(i,D) { REP(j,N) { scanf("%d",&F[p][i][j]); WN[p][i]+=F[p][i][j]; } } } //S->(Lp)P->D -> (N-Lunch) // -> (Lunch) //start - 0 //end - 1 const int start = 0; const int end = 1; int nodectr = 2 + D*N; vector edges; REP(i, P) { if(L[i] < 0) { printf("No\n"); return 0; } edges.push_back(EDGE(start, nodectr, L[i])); int actL = nodectr; ++nodectr; REP(d, D) { int actD = nodectr++; edges.push_back(EDGE(actL,actD, WN[i][d])); int lunchN = nodectr++; int notLunchN = nodectr++; int lunchTime = 0; REP(h,N) if(F[i][d][h]) { if( h>= LTb && h <=LTe) { ++lunchTime; } } if(lunchTime == 0) { printf("No\n"); return 0; } edges.push_back(EDGE(actD,lunchN, lunchTime - 1)); edges.push_back(EDGE(actD,notLunchN, N - LTe + LTb + 1)); REP(h,N) if(F[i][d][h]) { if( h>= LTb && h <=LTe) { edges.push_back(EDGE(lunchN, 2 +d*N+h, 1)); } else { edges.push_back(EDGE(notLunchN, 2 +d*N+h, 1)); } } } } REP(d, D) REP(h,N) { edges.push_back(EDGE(2+d*N+h, 1, R[d][h])); } N = nodectr; int M = edges.size(); vector > nodesEdges(N)/*, nodesEdgesRev(N)*/; REP(i,M) { nodesEdges[edges[i].from].push_back(i+1); nodesEdges[edges[i].to].push_back(-(i+1)); } //dinitz int total = 0; while(1) { vector dist; if(!bfs(N, edges, nodesEdges,dist)) break; vector checkEdges(N); while(1) { int pushed = dfs(0, INF, checkEdges, edges, nodesEdges,dist); if(pushed) total += pushed; else break; } } if(total == sumr) printf("Yes\n"); else printf("No\n"); return 0; }