### sean0613's blog

By sean0613, history, 2 months ago,

Codeforces Hot News!

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

Share it!

• -19

By sean0613, history, 2 months ago,

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?)

• -12

By sean0613, history, 3 months ago,

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)

• -22