2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
typedef long long ll;
const int maxn=110;
ll dp[maxn][2],l,k;
int main(){
    while(cin>>l>>k)
    {
        clr(dp,0);
        dp[0][0]=1;
        for(int i=1;i<=l;i++)
        {
            dp[i][0]+=dp[i-1][1];
            dp[i][1]+=dp[i-1][0];
            if(i-k>=0){
                dp[i][1]+=dp[i-k][0];
            }
        }
        ll ans=0;
        for(int i=1;i<=l;i++)
        {
            ans+=dp[i][1];
        }
        printf("%lld\n",ans);
    }
}

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
typedef long long ll;
const int maxn=110;
int m;
struct node{
    int x,y;
}z[110];
pair<int,int>pa;
map<pair<int,int>, int>mp;
int ans,n;
bool vis[110];
inline int gcd(int n,int m)
{
    int r;
    if(n < m)
    {
        r = n;
        n = m;
        m = r;
    }
    while(n % m)
    {
        r = n % m;
        n = m;
        m = r;
    }
    return m;
}
inline void dfs(int cnt,int num)
{
    if(cnt == n / 2)
    {
        ans = max(ans,num);
        return;
    }
    int i,j;
    for(i=1;i<=n;i++) if(vis[i]==0) {vis[i]=1;break;}
    
    for(j = i + 1;j <= n;j++)
    {
        if(vis[j])
        {
            continue;
        }
        vis[j] = true;
        int r,a,b;
        if(z[i].x == z[j].x)
        {
            a = 400001;
            b = 400002;
        }
        else if(z[i].y == z[j].y)
        {
            a = 0;
            b = 0;
        }
        else
        {
            r = gcd(abs(z[i].x - z[j].x),abs(z[i].y - z[j].y));
            if((z[i].x - z[j].x) / r < 0)
            {
                r = -r;
            }
            a = (z[i].x - z[j].x) / r;
            b = (z[i].y - z[j].y) / r;
        }
        pa.first = a;
        pa.second = b;
        int sum = mp[pa] + num;
        ans = max(ans,sum);
        mp[pa]++;
        dfs(cnt + 1,sum);
        pa.first = a;
        pa.second = b;
        mp[pa]--;
        vis[j] = false;
    }
    vis[i] = false;
}
inline void init(void)
{
    memset(vis,false,sizeof(vis));
    mp.clear();
    ans = 0;
}
int main(){
    int i,j;
    while(~scanf("%d",&n))
    {
        init();
        for(i = 1;i <= n;i++)
        {
            scanf("%d %d",&z[i].x,&z[i].y);
        }
        dfs(0,0);
        printf("%d\n",ans);
    }
}

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,a[maxn],ans[maxn],t;
void init()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}
void work()
{
    int q=a[1];
    ll sum=a[1];
    ans[1]=t/a[1]+1;
    for(int i=2;i<=n;i++)
    {
        sum+=a[i];
        if(a[i]>q) q=a[i];
        //printf("%d %d\n",sum,q); 
        if(t>=sum) ans[i]=(t-sum)/q+2;
        else ans[i]=1;
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
int main()
{
    init();
    work();
}

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
typedef long long ll;
const int maxn=200010;
struct node {
    int a,b;
    friend bool operator <(const node &x,const node &y) {
        return x.a<y.a;
    }
} p[maxn];
int n;
multiset<int >s;
multiset<int >::iterator it;
int ans2=0,ans1=0,a[maxn],b[maxn];

void anss2() {
    sort(p+1,p+1+n);
    s.insert(0);
    for(int i=1; i<=n; i++) {
        it=lower_bound(s.begin(),s.end(),p[i].a);
        
        if(it==s.begin()) {
            s.insert(p[i].b-1);
        } else {
            it--;
            s.erase(it);
            s.insert(p[i].b-1);
        }
    }
}
void anss3(){
    int i;
    sort(p+1,p+1+n);
    priority_queue<int>q;
    q.push(-p[1].b + 1);
    ans2 = 1;
    for(i = 2;i <= n;i++)
    {
        //printf(" %d %d\n",p[i].a,-q.top());
        int pos = q.top();
        pos = -pos;
        if(p[i].a > pos)
        {
            q.pop();
            q.push(-p[i].b + 1);
        }
        else
        {
            ans2++;
            q.push(-p[i].b + 1);
        }
    }
}
void anss1()
{
    for(int i=1;i<=n;i++)
    {
        a[p[i].a]++;
        b[p[i].b]++;
    }    
    for(int i=1;i<=100000;i++) a[i]=a[i-1]+a[i],b[i]=b[i-1]+b[i];
    for(int i=1;i<=n;i++)
    {
        ans1=max(ans1,a[p[i].b-1]-b[p[i].a]);
    }
}
int main() {
    while(cin>>n) {
        s.clear();
        for(int i=1; i<=n; i++) {
            scanf("%d%d",&p[i].a,&p[i].b);
        }
        //anss2();
        anss3();
        anss1();
        //ans2=s.size();
        printf("%d %d\n",ans1,ans2);
    }
}