当前位置 : 主页 > 网页制作 > HTTP/TCP >

贪心(change)

来源:互联网 收集:自由互联 发布时间:2021-06-16
http://codeforces.com/gym/100989/problem/H After the data structures exam, students lined up in the cafeteria to have a drink and chat about how much they have enjoyed the exam and how good their professors are. Since it was late in the eve

http://codeforces.com/gym/100989/problem/H

After the data structures exam, students lined up in the cafeteria to have a drink and chat about how much they have enjoyed the exam and how good their professors are. Since it was late in the evening, the cashier has already closed the cash register and does not have any change with him.

The students are going to pay using Jordanian money notes, which are of the following types: 1, 5, 10, 20, 50.

Given how much each student has to pay, the set of notes he’s going to pay with, and the order in which the students arrive at the cashier, your task is to find out if the cashier will have enough change to return to each of the student when they arrive at the cashier.


Input

The first line of input contains a single integer N (1 ≤ N ≤ 105), the number of students in the queue.

Each of the following N lines describes a student and contains 6 integers, K, F1, F2, F3, F4, and F5, where K represents the amount of money the student has to pay, and Fi (0 ≤ Fi ≤ 100) represents the amount of the ith type of money this student is going to give to the cashier.

The students are given in order; the first student is in front of the cashier.

It is guaranteed that no student will pay any extra notes. In other words, after removing any note from the set the student is going to give to the cashier, the amount of money will be less than what is required to buy the drink.

Output

Print yes if the cashier will have enough change to return to each of the students when they arrive in the given order, otherwise print no.

Examples Input
3
4 0 1 0 0 0
9 4 1 0 0 0
8 0 0 1 0 0
Output
no
Input
3
9 4 1 0 0 0
4 0 1 0 0 0
8 0 0 1 0 0
Output
yes

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdio.h>
#include <queue>
#include <stack>;
#include <map>
#include <set>
#include <ctype.h>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 10
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int sum , sum1 , sum5 , sum10 , sum20 , sum50 ;

int main()
{
    int n ;
    scanf("%d" , &n);
    int flag = 0 ;
    for(int i = 0 ; i < n ; i++)
    {
        int x , n1 , n5 , n10 , n20 , n50;
        scanf("%d%d%d%d%d%d" , &x , &n1 , &n5 , &n10 , &n20 , &n50);
        sum = 1* n1 + 5*n5 + 10*n10 + 20*n20 + 50*n50 - x;
        while(sum >= 50 && sum50)
        {
            sum -= 50 ;
            sum50 -- ;
        }
        while(sum >= 20 && sum20)
        {
            sum -= 20 ;
            sum20 -- ;
        }
        while(sum >= 10 && sum10)
        {
            sum -= 10 ;
            sum10 -- ;
        }
        while(sum >= 5 && sum5)
        {
            sum -= 5 ;
            sum5 -- ;
        }
        while(sum >= 1 && sum1)
        {
            sum -= 1 ;
            sum1 -- ;
        }
        if(sum == 0)
        {
            sum1 += n1 ;
            sum5 += n5 ;
            sum10 += n10;
            sum20 += n20;
            sum50 += n50;
        }
        else
        {
            flag = 1 ;
        }
    }
    if(flag)
    {
        printf("no\n");
    }
    else
    {
        printf("yes\n");
    }


    return 0;
}
网友评论