gky

1704

patrie
SeiunSky
itdef

jendolkk

Egbert-Lannister.
Elaina_24
hbq

Hamming

gky
12天前
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;
const int N=1010;
struct Point{
double l,r;
}point[N];
bool cmp(Point a,Point b){
return a.r<b.r;
}
int n,d;
int main(){
scanf("%d%d",&n,&d);

for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(abs(y)>d) {
puts("-1");
return 0;
}
double distance=sqrt(d*d-y*y);
point[i]={x-distance,x+distance};

}

sort(point+1,point+1+n,cmp);
double res=0,ed=-1e20;
for(int i=1;i<=n;i++){
if(point[i].l>ed){
res++;
ed=point[i].r;
}
}

cout<<res<<endl;

return 0;
}

gky
12天前
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef pair<int,int> PII;
const int N=50010;

struct Range{
int l,r,idx;
}range[N];
bool cmp(Range a,Range b){
return a.l<b.l;
}
int ids[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int start,end;
scanf("%d%d",&start,&end);
range[i]={start,end,i};
}

sort(range+1,range+1+n,cmp);
int id=1;
priority_queue<PII,vector<PII>,greater<PII>> heap;
for(int i=1;i<=n;i++){
auto point=range[i];
if(heap.empty()||heap.top().first>=point.l){
heap.push({point.r,point.idx});
ids[point.idx]=id;
id++;
}
else{
auto t=heap.top();
heap.pop();
ids[point.idx]=ids[t.second];
heap.push({point.r,point.idx});
}

}
cout<<heap.size()<<endl;
for(int i=1;i<=n;i++) cout<<ids[i]<<endl;
return 0;
}

gky
12天前
#include <iostream>
#include<algorithm>
using namespace std;
const int N=3500;
int n,m,i,j,k;
struct node
{
int spf,cover;
} a[N];
struct node2
{
int min_spf,max_spf;
} b[N];

int cmp(node a,node b)
{
if (a.spf==b.spf)
return a.cover>b.cover;
return a.spf>b.spf;
}
int cmp2(node2 a,node2 b)
{
if (a.min_spf==b.min_spf)
return a.max_spf>b.max_spf;
return a.min_spf>b.min_spf;
}
int main()
{
cin>>n>>m;
for (i=1;i<=n;i++)
cin>>b[i].min_spf>>b[i].max_spf;
sort(b+1,b+1+n,cmp2);
for (i=1;i<=m;i++)
cin>>a[i].spf>>a[i].cover;
sort(a+1,a+1+m,cmp);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[j].cover>=1&&b[i].min_spf<=a[j].spf&&b[i].max_spf>=a[j].spf){
a[j].cover--;
ans++;
break;
}
}
}

cout<<ans<<endl;
return 0;
}

gky
12天前
#include<iostream>

using namespace std;
const int N=1e5+10;
int price[N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&price[i]);
int res=0;
for(int i=1;i<n;i++){
if(price[i]<price[i+1]){
res+=price[i+1]-price[i];
}
}

cout<<res<<endl;
return 0;
}

gky
13天前
#include<iostream>

using namespace std;
typedef long long LL;
int n,m;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
LL C(int a){
return (LL)(a)*(a-1)*(a-2)/6;
}

int main(){
cin>>n>>m;
n++,m++;
LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
res-=2ll*((n-i)*(m-j))*(gcd(i, j) - 1);

}
}
cout<<res<<endl;
return 0;
}

gky
13天前
#include<iostream>
using namespace std;
const int N = 100010, mod = 5000011;
int f[N],s[N];
int main(){
int n,k;
cin>>n>>k;

f[0]=s[0]=1;
for(int i=1;i<=n;i++){
f[i]+=s[max(0,i-k-1)];
s[i]=(s[i-1]+f[i])%mod;
}
cout<<s[n];

return 0;
}

gky
13天前
#include <iostream>
#include <cmath>

using namespace std;

int w[25],c[25];
const int MOD=1e9;
const int N=1e6;
int n;
int f[N+10];
void qui(long long a,int b){
int cnt=1;
int res=1;
while(b){
w[cnt++]=res;
b--;
res=(res*a);
}
}

int main(){
scanf("%d",&n);
cin>>n;
qui(2,21);

f[0]=1;
for(int i=1;i<=21;i++){
for(int j=w[i];j<=n;j++){
f[j]=(f[j]+f[j-w[i]])%MOD;
}
}
cout<<f[n];
return 0;
}

gky
15天前
#include<iostream>

using namespace std;
const int N=2020;
long long f[N][N];
const int MOD=998244353;
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);

for(int i=1;i<=n;i++) f[i][0]=m;

for(int i=2;i<=n;i++){
for(int j=1;j<=k;j++){
f[i][j]=(f[i-1][j-1]*(m-1)+f[i-1][j])%MOD;
}
}

cout<<f[n][k];
return 0;
}

gky
15天前
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int fact[N], infact[N];

int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}

int main()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}

int n;
scanf("%d", &n);
while (n -- )
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}

return 0;
}

gky
15天前
#include<iostream>

using namespace std;
const int MOD=1e9+7;
int c[2005][2005];
void init(){
for(int i=0;i<=2001;i++){
for(int j=0;j<=i;j++){
if(!j) c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}
}
}

int main(){

init();
int n;
scanf("%d",&n);
while(n--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",c[a][b]);
}

return 0;
}