Problem:


Score : 1300 points

Problem Statement

A museum exhibits N jewels, Jewel 1, 2, ..., N.
The coordinates of Jewel i are (x_i, y_i) (the museum can be regarded as a two-dimensional plane), and the value of that jewel is v_i.

Snuke the thief will steal some of these jewels.

There are M conditions, Condition 1, 2, ..., M, that must be met when stealing jewels, or he will be caught by the detective.
Each condition has one of the following four forms:

(t_i =L, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or smaller.

(t_i =R, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or larger.

(t_i =D, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or smaller.

(t_i =U, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or larger.

Find the maximum sum of values of jewels that Snuke the thief can steal.

Constraints

1 \leq N \leq 80

1 \leq x_i, y_i \leq 100

1 \leq v_i \leq 10^{15}

1 \leq M \leq 320

t_i is L, R, U or D.

1 \leq a_i \leq 100

0 \leq b_i \leq N - 1

(x_i, y_i) are pairwise distinct.

(t_i, a_i) are pairwise distinct.

(t_i, b_i) are pairwise distinct.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1 v_1
x_2 y_2 v_2
:
x_N y_N v_N
M
t_1 a_1 b_1
t_2 a_2 b_2
:
t_M a_M b_M

Output

Print the maximum sum of values of jewels that Snuke the thief can steal.

Sample Input 1

7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2

Sample Output 1

36

Stealing Jewel 1, 5, 6 and 7 results in the total value of 36.

Sample Input 2

3
1 2 3
4 5 6
7 8 9
1
L 100 0

Sample Output 2

0

Sample Input 3

4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1

Sample Output 3

13

Sample Input 4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5

Sample Output 4

305223377000



Sample input:
7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2


Sample output:
36

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from bisect import bisect_left,bisect_right

class MinCostFlow:
    def __init__(self,n):
        self.n=n
        self.edges=[[] for i in range(n)]
    def add_edge(self,fr,to,cap,cost):
        self.edges[fr].append([to,cap,cost,len(self.edges[to])])
        self.edges[to].append([fr,0,-cost,len(self.edges[fr])-1])
    def MinCost(self,source,sink,flow):
        inf=10**15+1
        n,E=self.n,self.edges
        prev_v,prev_e=[0]*n,[0]*n
        mincost=0
        while flow:
            dist=[inf]*n
            dist[source]=0
            flag=True
            while flag:
                flag=False
                for v in range(n):
                    if dist[v]==inf:
                        continue
                    Ev=E[v]
                    for i in range(len(Ev)):
                        to,cap,cost,rev=Ev[i]
                        if cap>0 and dist[v]+cost<dist[to]:
                            dist[to]=dist[v]+cost
                            prev_v[to],prev_e[to]=v,i
                            flag=True
            if dist[sink]==inf:
                return -1
            f=flow
            v=sink
            while v!=source:
                f=min(f,E[prev_v[v]][prev_e[v]][1])
                v=prev_v[v]
            flow-=f
            mincost+=f*dist[sink]
            v=sink
            while v!=source:
                E[prev_v[v]][prev_e[v]][1]-=f
                rev=E[prev_v[v]][prev_e[v]][3]
                E[v][rev][1]+=f
                v=prev_v[v]
        return mincost

n=int(input())
J=[]
L_org,D_org=[1]*n,[1]*n
for _ in range(n):
    x,y,v=map(int,input().split())
    J.append((x,y,v))
m=int(input())
T=[]
for _ in range(m):
    t,a,b=input().split()
    a,b=int(a),int(b)
    T.append((t,a,b))
    if t=='L':
        L_org[b]=a+1
    elif t=='D':
        D_org[b]=a+1
for i in range(1,n):
    L_org[i]=max(L_org[i-1],L_org[i])
    D_org[i]=max(D_org[i-1],D_org[i])

def solve(k):
    L,D=L_org[:k],D_org[:k]
    R,U=[100]*k,[100]*k
    for t,a,b in T:
        if k-b-1>=0:
            if t=='R':
                R[k-b-1]=a-1
            elif t=='U':
                U[k-b-1]=a-1
    for i in range(k-2,-1,-1):
        R[i]=min(R[i],R[i+1])
        U[i]=min(U[i],U[i+1])
    solver=MinCostFlow(2*n+2*k+2)
    for i in range(1,k+1):
        solver.add_edge(0,i,1,0)
        solver.add_edge(2*n+k+i,2*n+2*k+1,1,0)
    for i in range(n):
        v=J[i][2]
        solver.add_edge(k+i+1,n+k+i+1,1,-v)
    for i in range(n):
        x,y=J[i][0],J[i][1]
        l=bisect_right(L,x)
        r=bisect_left(R,x)+1
        d=bisect_right(D,y)
        u=bisect_left(U,y)+1
        for j in range(r,l+1):
            solver.add_edge(j,k+i+1,1,0)
        for j in range(u,d+1):
            solver.add_edge(n+k+i+1,2*n+k+j,1,0)    
    return -solver.MinCost(0,2*n+2*k+1,k)

ans=0
k=1
while True:
    tmp=solve(k)
    ans=max(ans,tmp)
    if tmp==-1 or k==n:
        break
    k+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from bisect import bisect_left,bisect_right

class MinCostFlow:
    def __init__(self,n):
        self.n=n
        self.edges=[[] for i in range(n)]
    def add_edge(self,fr,to,cap,cost):
        self.edges[fr].append([to,cap,cost,len(self.edges[to])])
        self.edges[to].append([fr,0,-cost,len(self.edges[fr])-1])
    def MinCost(self,source,sink,flow):
        inf=10**15+1
        n=self.n; E=self.edges
        mincost=0
        prev_v=[0]*n; prev_e=[0]*n
        while flow:
            dist=[inf]*n
            dist[source]=0
            q=deque([source])
            Flag=[False]*n
            Flag[source]=True
            while q:
                v=q.popleft()
                if not Flag[v]:
                    continue
                Flag[v]=False
                for i,(to,cap,cost,_) in enumerate(E[v]):
                    if cap>0 and dist[to]>dist[v]+cost:
                        dist[to]=dist[v]+cost
                        prev_v[to],prev_e[to]=v,i
                        q.append(to)
                        Flag[to]=True
            if dist[sink]==inf:
                return 1
            f,v=flow,sink
            while v!=source:
                f=min(f,E[prev_v[v]][prev_e[v]][1])
                v=prev_v[v]
            flow-=f
            mincost+=f*dist[sink]
            v=sink
            while v!=source:
                E[prev_v[v]][prev_e[v]][1]-=f
                rev=E[prev_v[v]][prev_e[v]][3]
                E[v][rev][1]+=f
                v=prev_v[v]
        return mincost

n=int(input())
J=[]
L_org,D_org=[1]*n,[1]*n
for _ in range(n):
    x,y,v=map(int,input().split())
    J.append((x,y,v))
m=int(input())
T=[]
for _ in range(m):
    t,a,b=input().split()
    a,b=int(a),int(b)
    T.append((t,a,b))
    if t=='L':
        L_org[b]=a+1
    elif t=='D':
        D_org[b]=a+1
for i in range(1,n):
    L_org[i]=max(L_org[i-1],L_org[i])
    D_org[i]=max(D_org[i-1],D_org[i])

def solve(k):
    L,D=L_org[:k],D_org[:k]
    R,U=[100]*k,[100]*k
    for t,a,b in T:
        if k-b-1>=0:
            if t=='R':
                R[k-b-1]=a-1
            elif t=='U':
                U[k-b-1]=a-1
    for i in range(k-2,-1,-1):
        R[i]=min(R[i],R[i+1])
        U[i]=min(U[i],U[i+1])
    solver=MinCostFlow(2*n+2*k+2)
    for i in range(1,k+1):
        solver.add_edge(0,i,1,0)
        solver.add_edge(2*n+k+i,2*n+2*k+1,1,0)
    for i in range(n):
        v=J[i][2]
        solver.add_edge(k+i+1,n+k+i+1,1,-v)
    for i in range(n):
        x,y=J[i][0],J[i][1]
        l=bisect_right(L,x)
        r=bisect_left(R,x)+1
        d=bisect_right(D,y)
        u=bisect_left(U,y)+1
        for j in range(r,l+1):
            solver.add_edge(j,k+i+1,1,0)
        for j in range(u,d+1):
            solver.add_edge(n+k+i+1,2*n+k+j,1,0)    
    return -solver.MinCost(0,2*n+2*k+1,k)

ans=0
k=1
while True:
    tmp=solve(k)
    ans=max(ans,tmp)
    if tmp==-1 or k==n:
        break
    k+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from bisect import bisect_left,bisect_right

class MinCostFlow:
    def __init__(self,n):
        self.n=n
        self.edges=[[] for i in range(n)]
    def add_edge(self,fr,to,cap,cost):
        self.edges[fr].append([to,cap,cost,len(self.edges[to])])
        self.edges[to].append([fr,0,-cost,len(self.edges[fr])-1])
    def MinCost(self,source,sink,flow):
        inf=10**15+1
        n,E=self.n,self.edges
        prev_v,prev_e=[0]*n,[0]*n
        mincost=0
        while flow:
            dist=[inf]*n
            dist[source]=0
            flag=True
            while flag:
                flag=False
                for v in range(n):
                    if dist[v]==inf:
                        continue
                    Ev=E[v]
                    for i in range(len(Ev)):
                        to,cap,cost,rev=Ev[i]
                        if cap>0 and dist[v]+cost<dist[to]:
                            dist[to]=dist[v]+cost
                            prev_v[to],prev_e[to]=v,i
                            flag=True
            if dist[sink]==inf:
                return 1
            f=flow
            v=sink
            while v!=source:
                f=min(f,E[prev_v[v]][prev_e[v]][1])
                v=prev_v[v]
            flow-=f
            mincost+=f*dist[sink]
            v=sink
            while v!=source:
                E[prev_v[v]][prev_e[v]][1]-=f
                rev=E[prev_v[v]][prev_e[v]][3]
                E[v][rev][1]+=f
                v=prev_v[v]
        return mincost

n=int(input())
J=[]
L_org,D_org=[1]*n,[1]*n
for _ in range(n):
    x,y,v=map(int,input().split())
    J.append((x,y,v))
m=int(input())
T=[]
for _ in range(m):
    t,a,b=input().split()
    a,b=int(a),int(b)
    T.append((t,a,b))
    if t=='L':
        L_org[b]=a+1
    elif t=='D':
        D_org[b]=a+1
for i in range(1,n):
    L_org[i]=max(L_org[i-1],L_org[i])
    D_org[i]=max(D_org[i-1],D_org[i])

def solve(k):
    L,D=L_org[:k],D_org[:k]
    R,U=[100]*k,[100]*k
    for t,a,b in T:
        if k-b-1>=0:
            if t=='R':
                R[k-b-1]=a-1
            elif t=='U':
                U[k-b-1]=a-1
    for i in range(k-2,-1,-1):
        R[i]=min(R[i],R[i+1])
        U[i]=min(U[i],U[i+1])
    solver=MinCostFlow(2*n+2*k+2)
    for i in range(1,k+1):
        solver.add_edge(0,i,1,0)
        solver.add_edge(2*n+k+i,2*n+2*k+1,1,0)
    for i in range(n):
        v=J[i][2]
        solver.add_edge(k+i+1,n+k+i+1,1,-v)
    for i in range(n):
        x,y=J[i][0],J[i][1]
        l=bisect_right(L,x)
        r=bisect_left(R,x)+1
        d=bisect_right(D,y)
        u=bisect_left(U,y)+1
        for j in range(r,l+1):
            solver.add_edge(j,k+i+1,1,0)
        for j in range(u,d+1):
            solver.add_edge(n+k+i+1,2*n+k+j,1,0)    
    return -solver.MinCost(0,2*n+2*k+1,k)

ans=0
k=1
while True:
    tmp=solve(k)
    ans=max(ans,tmp)
    if tmp==-1 or k==n:
        break
    k+=1
print(ans)