CodeForce Round 579 Div 3

2019-08-14

这里是关于CodeForce Round 579 Div 3的一些题解

A. Circle of Students

Problem

There are $n$ students standing in a circle in some order. The index of the $i^{th}$ student is $p_i$. It is guaranteed that all indices of students are distinct integers from $1$ to $n$ (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student $2$ comes right after the student $1$ in clockwise order (there are no students between them), the student $3$ comes right after the student $2$ in clockwise order, and so on, and the student $n$ comes right after the student $n−1$ in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student $i$ should be right after the student $i−1$ in counterclockwise order (this condition should be met for every $i$ from $2$ to $n$).

For example, if the indices of students listed in clockwise order are $ \left[ 2,3,4,5,1 \right]$, then they can start a clockwise round dance. If the students have indices $ \left[3,2,1,4\right]$ in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle.

You have to answer $q$ independent queries.

Input

The first line of the input contains one integer $q (1 \leq q \leq 200)$ — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n (1 \leq n \leq 200)$ — the number of students.

The second line of the query contains a permutation of indices $p_1,p_2,…,p_n (1 \leq p_i \leq n)$, where $p_i$ is the index of the $i^{th}$ student (in clockwise order). It is guaranteed that all pi are distinct integers from $1$ to $n$ (i. e. they form a permutation).

Output

For each query, print the answer on it. If a round dance can be started with the given order of students, print “YES”. Otherwise print “NO”.

Example

input

5
4
1 2 3 4
3
1 3 2
5
1 2 3 5 4
1
1
5
3 2 1 5 4

output

YES
YES
NO
YES
YES

想法

暴力出奇迹，预处理一下复制一遍编号，然后暴力找有没有连续1 ~ n的数列。

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream> 
#include<iomanip>
#include<numeric>
#include<cctype> 
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
 
//#define DEBUG
#define RI register int
#define endl "\n"
 
using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
 
inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
 
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    ll t=read() ; 
    
    while(t--){
    
    int n=read();
    int num [1000]={0},flag=0;
    for(int i=0;i<n;i++)num[i]=num[i+n]=read();
    for(int i=0;i<=2*n-1;i++){
    	if(num[i]==1){
    		int j=1;
			for(;j==num[i]&&(i>=0&&i<=2*n-1);i++,j++){
				if(j==n)flag=1;
			}
    	}
    }
    for(int i=2*n-1;i>=0;i--){
    	if(num[i]==1){
    		int k=1;
			for(;k==num[i]&&(i>=0&&i<=2*n-1);i--,k++){
				if(k==n)flag=1;
			}
    	}
    }
    if(flag){
    	printf("YES\n");
    	continue;
    }
    else {
    	printf("NO\n");
    	continue;
    }
}
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

B. Equal Rectangles

Problem

You are given $4 \times n$ sticks, the length of the $i^{th}$ stick is $a_i$.

You have to create $n$ rectangles, each rectangle will consist of exactly $4$ sticks from the given set. The rectangle consists of four sides, opposite sides should have equal length and all angles in it should be right. Note that each stick can be used in only one rectangle. Each stick should be used as a side, you cannot break the stick or use it not to the full length.

You want to all rectangles to have equal area. The area of the rectangle with sides $a$ and $b$ is $a \times b$.

Your task is to say if it is possible to create exactly $n$ rectangles of equal area or not.

You have to answer $q$ independent queries.

Input

The first line of the input contains one integer $q (1 \leq q \leq 500)$ — the number of queries. Then $q$ queries follow.

The first line of the query contains one integer $n (1 \leq n \leq 100)$ — the number of rectangles.

The second line of the query contains $4 \times n$ integers $a_1,a_2,…,a_{4n} (1 \leq a_i \leq 10^4)$, where $a_i$ is the length of the $i^{th}$ stick.

Output

For each query print the answer to it. If it is impossible to create exactly $n$ rectangles of equal area using given sticks, print “NO”. Otherwise print “YES”.

Example

input

5
1
1 1 10 10
2
10 5 2 10 1 1 2 5
2
10 5 1 10 5 1 1 1
2
1 1 1 1 1 1 1 1
1
10000 10000 10000 10000

output

YES
YES
NO
YES
YES

想法

因为要求所有矩形的面积一样，那么想到假设$S_1=a_1 \times b_1 , S_2=a_2 \times b_2 , S_3=a_3 \times b_3$，如果$a_1 < a_2 < a_3$，则必有$ b_1 < b_2 < b_3 $

那么就是稍微预处理边，求首尾相乘的面积是否相等。

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream> 
#include<iomanip>
#include<numeric>
#include<cctype> 
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
 
//#define DEBUG
#define RI register int
#define endl "\n"
 
using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
 
inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar(); 
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
 
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    ll t ; 
    scanf("%lld",&t);
    while(t--){
    //}
    int stick[10003]={0},n=read(),bian[500]={0},flag=1;
    for(int i=0;i<4*n;i++){
    	stick[read()]++;
    }
    for(int i=0;i<10003;i++){
    	if(stick[i]%2){
    		flag=0;
    	}
    	else if(stick[i])stick[i]/=2;
    }
    if(!flag){
    	printf("NO\n");
    	continue;
    }
    int bs=0;
    for(int i=0;i<10003;i++){
    	while(stick[i]--){
    		bian[bs++]=i;
    	}
    }
    int s=bian[0]*bian[n*2-1];
    for(int i=0,j=n*2-1;i<j;i++,j--){
    	if(bian[i]*bian[j]!=s){
    		flag=0;
    		break;
    	}
    }
    if(flag){
    	printf("YES\n");
    	continue;
    }
    else {
    	printf("NO\n");
    	continue;
    }
}
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

C. Common Divisors

Problem

You are given an array $a$ consisting of $n$ integers.

Your task is to say the number of such positive integers $x$ such that $x$ divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array $a$ will be $\left[2,4,6,2,10\right]$, then $1$ and $2$ divide each number from the array (so the answer for this test is $2$).

Input

The first line of the input contains one integer $n (1 \leq n \leq 4 \times 10^5)$ — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1,a_2,…,a_n (1 \leq a_i \leq 10^{12})$, where $a_i$ is the $i^{th}$ element of $a$.

Output

Print one integer — the number of such positive integers $x$ such that $x$ divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).

Examples

input

5
1 2 3 4 5

output

1

input

6
6 90 12 18 30 18

output

4

想法

这题题意是找出这些树的公共的因子的数目

那么这里很容易想到求这些数的gcd然后求gcd的因子数就是这些数的公共因子数

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream> 
#include<iomanip>
#include<numeric>
#include<cctype> 
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
 
//#define DEBUG
#define RI register int
#define endl "\n"
 
using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
 
inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar(); 
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
 
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //ll t ; 
    //scanf("%lld",&t);
    //while(t--){
    //}
    ll n=read(),gc=read();n--;
    while(n--){
    	gc=__gcd(gc,read());
    	if(gc==1){
    		printf("1");
    		return 0;
    	}
    }
    ll ans=0;
    for(ll i=1;i*i<=gc;i++){
    	if(gc%i==0){
    		ans++;
    		if(i*i!=gc)ans++;
    	}
    }
    printf("%lld",ans);
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

D. Remove the Substring

Problem

You are given a string $s$ and a string $t$, both consisting only of lowercase Latin letters. It is guaranteed that $t$ can be obtained from $s$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $s$ without changing order of remaining characters (in other words, it is guaranteed that $t$ is a subsequence of $s$).

For example, the strings “test”, “tst”, “tt”, “et” and “” are subsequences of the string “test”. But the strings “tset”, “se”, “contest” are not subsequences of the string “test”.

You want to remove some substring (contiguous subsequence) from $s$ of maximum possible length such that after removing this substring t will remain a subsequence of $s$.

If you want to remove the substring $s[l;r]$ then the string $s$ will be transformed to $s_1 \; s_2 \; … \; s_{l−1} \; s_{r+1} \; s_{r+2} \; … \; s_{|s|−1} \; s_{|s|}$ (where $|s|$ is the length of $s$).

Your task is to find the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.

Input

The first line of the input contains one string $s$ consisting of at least $1$ and at most $2 \times 10^5$ lowercase Latin letters.

The second line of the input contains one string $t$ consisting of at least $1$ and at most 2⋅105 lowercase Latin letters.

It is guaranteed that t is a subsequence of s.

Output

Print one integer — the maximum possible length of the substring you can remove so that t is still a subsequence of s.

Examples

input

bbaba
bb

output

3

input

baaba
ab

output

2

input

abcde
abcde

output

0

input

asdfasdf
fasd

output

3

想法

题目大意是从S串中删除一些串使得剩下的串首尾相连构成T串，并且求最长的删除串的长度。题目保证T串可由S串任意删除字母而构成。

总的来说分三种情况

1.最长删除串在左端

2.最长删除穿在右端

3.最长删除串在中间

假设现在有S串和T串，那么为了使得删除串的长度最大，情况1就必须要使得第一个T串字母在S串的位置往后靠；情况2必须要往两端靠；情况3需要往前靠这样就可以使得删除串尽可能长

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	string s, t;
	cin >> s >> t;
	vector<int> rg(t.size());
	
	for (int i = int(t.size()) - 1; i >= 0; --i) {
		int pos = int(s.size()) - 1;
		if (i + 1 < int(t.size())) pos = rg[i + 1] - 1;
		while (s[pos] != t[i]) --pos;
		rg[i] = pos;
	}
	
	int ans = 0;
	int pos = 0;
	for (int i = 0; i < int(s.size()); ++i) {
		int rpos = int(s.size()) - 1;
		if (pos < int(t.size())) rpos = rg[pos] - 1;
		ans = max(ans, rpos - i + 1);
		if (pos < int(t.size()) && t[pos] == s[i]) ++pos;
	}
	
	cout << ans << endl;
	
	return 0;
}

E. Boxers

Problem

There are $n$ boxers, the weight of the $i^{th}$ boxer is $a_i$. Each of them can change the weight by no more than 1 before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers’ weights in the team are different (i.e. unique).

Write a program that for given current values $a_i$ will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is $150001$ (but no more).

Input

The first line contains an integer $n (1 \leq n \leq 150000)$ — the number of boxers. The next line contains $n$ integers $a_1,a_2,…,a_n$, where $a_i (1 \leq a_i \leq 150000)$ is the weight of the $i^{th}$ boxer.

Output

Print a single integer — the maximum possible number of people in a team.

Examples

input

4
3 2 4 1

output

4

input

6
1 1 1 4 4 4

output

5

Note

In the first example, boxers should not change their weights — you can just make a team out of all of them.

In the second example, one boxer with a weight of $1$ can be increased by one (get the weight of $2$), one boxer with a weight of $4$ can be reduced by one, and the other can be increased by one (resulting the boxers with a weight of $3$ and $5$, respectively). Thus, you can get a team consisting of boxers with weights of $5,4,3,2,1$.

想法

小小的贪心

这题言外之意就是要把集中的数分散开来，比如我有3个5,0个4,0个6，也就是5,5,5，那么我可以变成4,5,6

因为每个数只能加一或者减一，那么只要贪心即可

如果当前这个数有0个且下一个数的数目大于0，那么就可以从下一个数变过来一个，即使下一个数的数目因此变成了0也没事，因为大小不同的数的数目没变，也就是说没有恶化答案。

当然还要反向贪心一下

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h> 
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream> 
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
 
//#define DEBUG
#define RI register int
#define endl "\n"
 
using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
 
inline ll read(){
    long long x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f; 
}
 
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //ll t ; 
    //scanf("%lld",&t);
    //while(t--){
    //}
    int n;
    n=read();
    int num[150002]={0},sum=0;
    for(int i=0;i<n;i++){
    	int tem=read();
    	num[tem]++;
    }
    for(int i=1;i<150001;i++){
    	if(num[i]==0&&num[i+1]>0)num[i]++,num[i+1]--;
    }
    for(int i=150001;i>=1;i--){
    	if(num[i]==0&&num[i-1]>0)num[i]++,num[i-1]--;
    }
    for(int i=150001;i>=1;i--){
    	if(num[i]>0)sum++;
    }
    printf("%d",sum);
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}

F1. Complete the Projects (easy version)

Problem

Polycarp is a very famous freelancer. His current rating is $r$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $i^{th}$ project, Polycarp needs to have at least $a_i$ units of rating; after he completes this project, his rating will change by $b_i$ (his rating will increase or decrease by $b_i$) ($b_i$ can be positive or negative). Polycarp’s rating should not fall below zero because then people won’t trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Input

The first line of the input contains two integers $n$ and $r (1 \leq n \leq 100,1 \leq r \leq 30000)$ — the number of projects and the initial rating of Polycarp, respectively.

The next $n$ lines contain projects, one per line. The $i^{th}$ project is represented as a pair of integers $a_i$ and $b_i$ $(1 \leq ai \leq 30000, −300 \leq bi \leq 300)$ — the rating required to complete the $i^{th}$ project and the rating change after the project completion.

Output

Print “YES” or “NO”.

Examples

input

3 4
4 6
10 -2
8 -1

output

YES

input

3 5
4 -5
4 -2
1 3

output

YES

input

4 4
5 2
5 -3
2 1
4 -2

output

YES

input

3 10
10 0
10 -10
30 0

output

NO

Note

In the first example, the possible order is: $1,2,3$.

In the second example, the possible order is: $2,3,1$.

In the third example, the possible order is: $3,1,4,2$.

想法

Firstly, let’s divide all projects into two sets: all projects giving us non-negative rating changes (let this set be pos) and all projects giving up negative rating changes (let this set be neg). Firstly let’s take all projects from the set pos. How do we do that? Let’s sort them by $a_i$ in non-decreasing order because each project we take cannot make our rating less and we need to consider them in order of their requirements. If we can take the current project $i (r \leq a_i)$, set $r:=r+b_i$ and go further, otherwise print “NO” and terminate the program.

Okay, what do we do with the projects that has negative $b_i$? Firstly, let’s set $a_i:=max(a_i,−b_i)$. This means the tighter requirement of this project, obviously. Then let’s sort all projects in order of $a_i+b_i$ in non-increasing order and go from left to right and take all of them. If we cannot take at least one project, the answer is “NO”. Otherwise the answer is “YES”.

AC Program

#include <bits/stdc++.h>

using namespace std;

bool comp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first + a.second > b.first + b.second;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, r;
	cin >> n >> r;
	vector<pair<int, int>> pos, neg;
	for (int i = 0; i < n; ++i) {
		pair<int, int> cur;
		cin >> cur.first >> cur.second;
		if (cur.second >= 0) pos.push_back(cur);
		else {
		    cur.first = max(cur.first, abs(cur.second));
		    neg.push_back(cur);
		}
	}
	
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end(), comp);
	
	int taken = 0;
	for (int i = 0; i < int(pos.size()); ++i) {
		if (r >= pos[i].first) {
			r += pos[i].second;
			++taken;
		}
	}
	
	vector<vector<int>> dp(neg.size() + 1, vector<int>(r + 1, 0));
	dp[0][r] = taken;
	for (int i = 0; i < int(neg.size()); ++i) {
		for (int cr = 0; cr <= r; ++cr) {
			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
			}
			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
		}
	}
	
	int ans = 0;
	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
	cout << (ans == n ? "YES" : "NO") << endl;
	
	return 0;
}

F2. Complete the Projects (hard version)

Problem

Polycarp is a very famous freelancer. His current rating is $r$ units.

Polycarp can choose the order in which he completes projects. Furthermore, he can even skip some projects altogether.

To gain more experience (and money, of course) Polycarp wants to choose the subset of projects having maximum possible size and the order in which he will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Your task is to calculate the maximum possible size of such subset of projects.

Input

The first line of the input contains two integers $n$ and $r (1 \leq n \leq 100,1 \leq r \leq 30000)$ — the number of projects and the initial rating of Polycarp, respectively.

Output

Print one integer — the size of the maximum possible subset (possibly, empty) of projects Polycarp can choose.

Examples

input

3 4
4 6
10 -2
8 -1

output

3

input

5 20
45 -6
34 -15
10 34
1 27
40 -45

output

5

input

3 2
300 -300
1 299
1 123

output

3

想法

To view the main idea of the problem, read the editorial of easy version. The only difference is that for non-negative $b_i$ we don’t need to print “NO” if we cannot take the project, we just need to skip it because we cannot take it at all. And for negative $b_i$ we need to write the knapsack dynamic programming to take the maximum possible number of projects (we need to consider them in order of their sorting). Dynamic programming is pretty easy: $dp \left[ i \right] \left[ j \right] $ means that we consider $i$ projects and our current rating is $j$ and the value of $dp \left[ \; \right] \left[ \; \right] $ is the maximum number of negative projects we can take. If the current project is the $i_{th}$ negative project in order of sorting, we can do two transitions: $dp \left[ i+1 \right] \left[ j \right] =max(dp \left[ i+1 \right] \left[ j \right] ,dp \left[ i \right] \left[ j \right] )$ and if $r+b_i≥0$ then we can make the transition $dp \left[ i+1 \right] \left[ j \right] +b_i=max(dp \left[ i+1 \right] \left[ j \right] +b_i,dp \left[ i \right] \left[ j \right] +1)$. And then we just need to find the maximum value among all values of $dp \left[ \; \right] \left[ \; \right] $ and add the number of positive projects we take to find the answer.

AC Program

#include <bits/stdc++.h>

using namespace std;

bool comp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first + a.second > b.first + b.second;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, r;
	cin >> n >> r;
	vector<pair<int, int> > pos, neg;
	for (int i = 0; i < n; ++i) {
		pair<int, int> cur;
		cin >> cur.first >> cur.second;
		if (cur.second >= 0) pos.push_back(cur);
		else {
		    cur.first = max(cur.first, abs(cur.second));
		    neg.push_back(cur);
		}
	}
	
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end(), comp);
	
	int taken = 0;
	for (int i = 0; i < int(pos.size()); ++i) {
		if (r >= pos[i].first) {
			r += pos[i].second;
			++taken;
		}
	}
	
	vector<vector<int> > dp(neg.size() + 1, vector<int>(r + 1, 0));
	dp[0][r] = taken;
	for (int i = 0; i < int(neg.size()); ++i) {
		for (int cr = 0; cr <= r; ++cr) {
			if (cr >= neg[i].first && cr + neg[i].second >= 0) {
				dp[i + 1][cr + neg[i].second] = max(dp[i + 1][cr + neg[i].second], dp[i][cr] + 1);
			}
			dp[i + 1][cr] = max(dp[i + 1][cr], dp[i][cr]);
		}
	}
	
	int ans = 0;
	for (int cr = 0; cr <= r; ++cr) ans = max(ans, dp[int(neg.size())][cr]);
	cout << ans << endl;
	
	return 0;
}

int m=3, n=5;
vector< vector > vvi(m, vector(n) );
　定义了一个vector容器，元素类型为vector，初始化为包含m个vector对象，每个对象都是一个新创立的vector对象的拷贝，而这个新创立的vector对象被初始化为包含n个0。

　　每部分解析：
　　构造函数vector(size_type n, const allocator_type& alloc = allocator_type())表示构造一个使用alloc分配内存（如果是初学，不用管这个，使用默认的就好）的含n个元素的vector，其中每个元素执行值初始化（对于内置类型即初始化为0）。因此vector(n)表示构造一个无名且含n个0的vector对象。

　　构造函数vector(size_type n, const value_type& val, const allocator_type& alloc = allocator_type())表示构造一个使用alloc分配内存的含n个元素的vector，其中每个元素是val的一个拷贝。因此整条语句的含义如第一段所说。
　　
　　从结果上看，类似于创建了一个m×n的二维数组，而且可以通过v[i][j]的方式来访问元素（vector支持下标访问元素）。