Codeforces Hot News!

Wow! Coder sean0613 competed in Codeforces Round 937 (Div. 4) and gained +198 rating points taking place 142

Share it!

click here

Problem a

First,sort.

for every ai,find the biggest j that ai+bj<=k,then ans+=j

code:

// 1<=t<=100 1<=n,m<=100 1<=k<=2000 1<=bi<=1000 1<=ci<=1000
#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;

int a[MAXN],b[MAXN];

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		int n,m,k;
		scanf("%d %d %d",&n,&m,&k);
		for (int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for (int i=1;i<=m;i++)
			scanf("%d",&b[i]);
		sort(a+1,a+1+n);
		sort(b+1,b+1+m);
		int ans=0;
		for (int i=1;i<=n;i++)
			ans+=upper_bound(b+1,b+1+m,k-a[i])-b-1;
		printf("%d\n",ans);
	}

	return 0;
}

Problem b

Obviously,if you want to make a1 turn into 0,you make changes on a2 for a1 times.

So you make changes on ai for a(i-1) times.

code:

// 1<=t<=1e4 3<=n<=2e5 0<=aj<=1e9
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;

int a[MAXN];

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		int n;
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			scanf("%d",&a[i]);

		bool fg=1;
		for (int i=2;i<n;i++){
			if (a[i-1]<0){
				fg=0;
				break;
			}
			a[i]-=2*a[i-1];
			a[i+1]-=a[i-1];
			a[i-1]=0;
		}
		for (int i=1;i<=n;i++)
			if (a[i]!=0){
				fg=0;
				break;
			}
		if (fg) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}

Problem c

Obviously if there is a "map",you delete the 'a'.Then,there won't be a new 'map'.Same as "pie".And if there is "mapie",delete the 'p'

code:

// 1<=t<=1e4 1<=n<=1e6
#include<bits/stdc++.h>
using namespace std;

int main(){
	int t;
	cin >> t;
	while (t--){
		int n;
		string s;
		cin >> n >> s;
		int ans=0;
		for (int i=2;i<n;i++)
			if (s[i-2]=='m' and s[i-1]=='a' and s[i]=='p' or s[i-2]=='p' and s[i-1]=='i' and s[i]=='e')
				ans++;
		for (int i=4;i<n;i++)
			if (s[i-4]=='m' and s[i-3]=='a' and s[i-2]=='p' and s[i-1]=='i' and s[i]=='e')
				ans--;
		cout << ans << endl;
	}

	return 0;
}

Problem d

Just throw ball.

You can reach i after j throw if you can reach i-x or i+x after j-1 throw.

Something you should know:You can't use "long long"(that's how I'm wrong answer in the contest),cause it's very big.

code:

// 1<=t<=1e4 2<=n<=1000 1<=m<=1000 1<=x<=n 1<=ri<=n-1 sum(n*m)<=2e5
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int MAXN=1005;

bool dp[MAXN][MAXN];

signed main(){
	int t;
	scanf("%d",&t);
	getchar();
	while (t--){
		memset(dp,0,sizeof(dp));
		int n,m,x;
		scanf("%d %d %d",&n,&m,&x);
		getchar();
		dp[0][x]=1;
		for (int i=1;i<=m;i++){
			int a;
			char b;
			scanf("%d %c",&a,&b);
			getchar();
			if (b=='0'){
				for (int j=1;j<=n;j++){
					int tmp=(j-a+n)%n;
					if (tmp==0) tmp=n;
					dp[i][j]=dp[i-1][tmp];
				}
			}
			else if (b=='1'){
				for (int j=1;j<=n;j++){
					int tmp=(j+a)%n;
					if (tmp==0) tmp=n;
					dp[i][j]=dp[i-1][tmp];
				}
			}
			else{
				for (int j=1;j<=n;j++){
					int tmp=(j+a)%n;
					if (tmp==0) tmp=n;
					int tmp1=(j-a+n)%n;
					if (tmp1==0) tmp1=n;
					dp[i][j]=dp[i-1][tmp]+dp[i-1][tmp1];
				}
			}
		}
		int ans=0;
		for (int i=1;i<=n;i++)
			if (dp[m][i])
				ans++;
		printf("%d\n",ans);
		for (int i=1;i<=n;i++)
			if (dp[m][i])
				printf("%d ",i);
		printf("\n");
	}

	return 0;
}

Problem e

Just calculate the cost of every row with dp like "LIS"(Longest Increasing Subsequence).

Then,you will get a "TLE".

Cause you been O($$$n^2m$$$).

So you can use a map for the minimum(If you don't understand,look at the code).

code:

// 1<=t<=1e3 1<=k<=n<=100 3<=m<=2e5 1<=d<=m 0<=ai,j<=1e6 ai,1=ai,m=0 sum(n,m)<=2e5
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=105;

int dp[200001],a[MAXN],hei[200001];
map<int,int> mp;

signed main(){
	int t;
	scanf("%lld",&t);
	while (t--){
		int n,m,k,d;
		scanf("%lld %lld %lld %lld",&n,&m,&k,&d);
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++)
				scanf("%lld",&hei[j]);
			for (int j=0;j<=m;j++) dp[j]=1e17;
			mp.clear();
			dp[1]=1;
			mp[1]++;
			for (int j=2;j<=m;j++){
				dp[j]=mp.begin()->first+hei[j]+1; // for the minimum
				mp[dp[j]]++;
				if (j-d-1>=1){ // maintenance for it
					mp[dp[j-d-1]]--;
					if (mp[dp[j-d-1]]==0)
						mp.erase(mp.lower_bound(dp[j-d-1]));
				}
			}
			// for (int j=2;j<=m;j++)
			// 	printf("%lld ",dp[j]);
			// printf("\n");
			a[i]=dp[m];
		}
		int ans=0,sum=0;
		for (int i=1;i<=k;i++)
			sum+=a[i];
		ans=sum;
		for (int i=2;i+k-1<=n;i++){
			sum-=a[i-1];
			sum+=a[i+k-1];
			ans=min(ans,sum);
		}
		printf("%lld\n",ans);
	}

	return 0;
}

(I'm not good at use $$$Latex$$$,but can you give me a + for I've written a lot?)

I've ac 5 in the competition.But my code for D had been hacked.Then,5->4,1500->5300,+100(and more)->+1.NO GOD PLEASE NOOOOOOOOOOO!My code for D had been hacked just because a place which should be 'bool' and I've code 'long long'.GODDDDDDDDDDDDDDDDD!I could have uped to 1400! (Next will be edi for a to e)