akhauriyash/Code-Regression huggingface dataset:
//https://atcoder.jp/contests/dp/tasks/dp_f
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;

#define f(i,a,b) for(int i = a;i<b;i++)
#define rep(i,a,b) for(int i = a;i<=b;i++)
#define fd(i,a,b) for(int i = a;i>b;i--)
#define repd(i,a,b) for(int i = a;i>=b;i--)

#define pii pair<int,int>
#define pll pair<ll,ll>

#define fi first
#define se second
#define pb push_back
#define sz(x) (int) (x).size()
#define all(x) x.begin(),x.end()
using namespace std;
const int mod = 1000000007;
const int maxn = 200000;
int main(){
    string s,t;
    cin>>s>>t;
    int n = sz(s),m = sz(t);
    int dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    f(i,0,n){
        f(j,0,m){
            if(s[i]==t[j])
                dp[i+1][j+1] = 1 + dp[i][j];
            else
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
        }
    }
    int len = dp[n][m];
    string ans(len,'?');
    int i = n,j = m;
    while(len>0){
        if(s[i-1]==t[j-1]){
            ans[len-1] = s[i-1];
            len--;i--;j--;
        }
        else{
            if(dp[i][j-1]==len)
                j--;
            else
                i--;
        }
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 38816
import numpy as np

N = int(input())
F = [list(map(int, input().strip().split())) for i in range(N)]
P = [list(map(int, input().strip().split())) for i in range(N)]
maxProfit = -1000000000



for i in range(1,1024):
    openTime = list(map(int, list("{:0>10}".format(bin(i)[2:]))))
    thisProfit = 0
    for n in range(N):
        shopOpneTime = F[n]
        shopProfit = P[n]
        counter = 0
        for j in range(10):
            if((shopOpneTime[j])and(openTime[j])):
                 counter += 1
        thisProfit += shopProfit[counter]
    maxProfit = max(thisProfit, maxProfit)

print(maxProfit)


Measured memory_bytes: 12508
#include <bits/stdc++.h>

#define f(i,a,b) for( ll i = a; i < b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inter ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
 
const ll MAX = 1e5+10;
ll mod = 1e9+7;

ll dp[MAX],dp2[MAX];
vi adj[MAX];

ll pre[MAX],suf[MAX];

void dfs(ll u,ll f){
	dp[u] = 1;
	for(ll v:adj[u]){
		if(v == f) continue;
		dfs(v,u);
		(dp[u] *= (dp[v]+1))%=mod;
	}
}
void dfs1(ll u,ll f){
	pre[0] = pre[sz(adj[u])] = suf[0] = suf[sz(adj[u])] = 1;
	ll cont = 1;
	for(ll v:adj[u]){
		if(v == f) continue;
		pre[cont] = (pre[cont-1]*(dp[v]+1))%mod; 
		cont++;
	}
//	cout << cont << " "<< adj[u].size()<< endl;
	cont = adj[u].size()-1;
	af(i,adj[u].size()-1,0){
		ll v = adj[u][i]; 
		if(v == f) continue;
		suf[cont] = (suf[cont+1]*(dp[v]+1))%mod; 
		cont--;
	}
	cont = 1;
	
	for(ll v:adj[u]){
		if(v == f) continue;
		(dp2[v] = ( ((pre[cont-1] * suf[cont+1]) )%mod ) * (dp2[u] +1 ) )%=mod;
		(dp[v] *= ( dp2[v] +1)%mod )%=mod;
		cont++;
	}
	for(ll v: adj[u]){
		if (v==f) continue;
		dfs1(v,u);
	}
}


int main(){
	fastio;
	ll n,u,v;
	cin >> n >> mod;
	f(i,1,n){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	adj[1].push_back(0);
	dfs(1,0);
	dfs1(1,0);
	f(i,1,n+1) cout << dp[i] << endl;

}


Measured memory_bytes: 15320
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, A: "List[int]"):
    A = [0] + A + [0]

    forward = [0]
    curr = 0
    for i in range(N+1):
        forward.append(forward[-1] + abs(curr-A[i+1]))
        curr = A[i+1]

    for i in range(N):
        print(forward[-1]
              + (abs(A[i+2]-A[i]) -
                 (abs(A[i]-A[i+1]) + abs(A[i+1]-A[i+2]))))

    # backward = [0]
    # curr = 0
    # for i in range(N+1):
    #     backward.append(backward[-1] + abs(curr-A[N-i]))
    #     curr = A[N-i]

    # print(forward)
    # print(backward)

    # trip = [forward[i] + backward[N-i-1] for i in range(N)]
    # print(*trip, sep="\n")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 19644
/*
 * @Description: 
 * @Autor: G_Rampart
 * @Date: 2020-08-18 14:33:25
 * @LastEditTime: 2020-08-18 14:48:47
 */
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long n, d, cnt = 0;
  	cin >> n >> d;
  	unsigned long long dd = d*d;
    while(n--)
    {
      	long long x, y;
    	cin >> x >> y;
        unsigned long long xx = x*x;
        unsigned long long yy = y*y;
        // cout << x << y << endl;
      	if(xx + yy > dd)
          continue;
        // cout << "x^2+y^2 ="<< xx + yy << ":Yes" << endl;
      	cnt ++;
    }
  	cout << cnt << endl;
  	return 0;
}

Measured memory_bytes: 3596
// A - Lucky 7
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	string s;
	cin >> s;
	bool ok = false;
	for (int i = 0; i < s.size(); i++)
		if (s[i] == '7') ok = true;
	cout << (ok ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 3624
class Program
{
    static void Main(string[] args)
    {
        string[] temp = System.Console.ReadLine().Split(' ');
        int A = int.Parse(temp[0]);
        int B = int.Parse(temp[1]);
        int C = int.Parse(temp[2]);
        if (B / A > C) { System.Console.WriteLine(C); }
        else { System.Console.WriteLine(B/A); }
    }
}

Measured memory_bytes: 13140
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;

int main() {
	int a, b, c,r(0);
	cin >> a >> b >> c;
	if (a == b) {
		++r;
	}
	if (a == c) {
		++r;
	}
	if (b == c) {
		++r;
	}
	if (r == 1) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int l, i = 0, a[100000],N,M,sum,answer; 
  while (cin >> l) {
        a[i] = l;
        i++;
  }
  for (int j = 2; j < i; j++) {
  	sum += a[j];
  }
  N = a[0];
  M = a[1];
  if (N < sum) {
    cout << -1 << endl;    
  }else{
    answer = N - sum;  
    cout << answer << endl;
  }
}


Measured memory_bytes: 3644
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n;
	R[] rs;

	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			rs=new R[n];
			for(int i=0; i<n; i++){
				rs[i]=new R();
				rs[i].c=sc.nextInt();
				for(int k=0; k<4; k++){
					rs[i].sec+=sc.nextInt()*60;
					rs[i].sec+=sc.nextInt();
				}
			}
			Arrays.sort(rs);
			println(""+rs[0].c);
			println(""+rs[1].c);
			println(""+rs[n-2].c);
		}
	}

	class R implements Comparable<R>{
		int c, sec;

		@Override
		public int compareTo(R r){
			return sec-r.sec;
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long 

int main(int argc, char const *argv[]){
	int cnt[257] = { 0 };
	char str[100];
	scanf("%s",str);
	for (int i = 0; i < strlen(str); ++i)	++cnt[(int)str[i]];
	for (int i = 0; i < 255; ++i)
	{
		if(cnt[i] % 2){
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 1 << 29
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

ll N, C;

ll solve(vector<ll> x, vector<ll> v) {
    vector<ll> f(N), g(N), l(N);
    ll acc = 0;
    REP(i, N) {
        acc += v[i];
        f[i] = acc - 2 * x[i];
    }

    ll ma = 0;
    REP(i, N) {
        ma = max(f[i], ma);
        g[i] = ma;
    }
    acc = 0;
    DOWN(i, N-1, 0) {
        acc += v[i];
        l[i] = acc - (C - x[i]);
    }
    ll ans = l[0];
    FOR(i, 0, N-2) {
        ans = max(ans, l[i+1] + g[i]);
    }
    return ans;
}

int main() {
    cin >> N >> C;
    vector<ll> x(N), v(N);
    REP(i, N) {
        cin >> x[i] >> v[i];
    }
    ll ans = 0;
    ans = max(ans, solve(x, v));
    reverse(ALL(x));
    reverse(ALL(v));
    REP(i, N) x[i] = C - x[i];
    ans = max(ans, solve(x, v));
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{

    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

//----------------------------------------------------------------

int main()
{
    ll n;
    cin >> n;
    vector<ll> x(n);
    vector<ll> xmemo(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
        xmemo[i] = x[i];
    }
    sort(x.begin(), x.end());
    ll cent1 = x[n / 2 - 1] + x[n / 2];
    for (int i = 0; i < n; i++)
    {
        if (xmemo[i] * 2 < cent1)
        {
            cout << x[n / 2] << endl;
        }
        else
        {
            cout << x[n / 2 - 1] << endl;
        }
    }
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define rs resize
using namespace std;
struct ch{
ll x;
ll y;
ll z;
};
main (){
ll n,t;
cin>>n;
vector<ch>a;
a.resize(n+1);
for (int i=1;i<=n;i++)
    cin>>a[i].x>>a[i].y>>a[i].z;
vector<ch>d;
d.resize(n+1);
d[1].x=a[1].x;
d[1].y=a[1].y;
d[1].z=a[1].z;
for (int i=2;i<=n;i++){
    d[i].x=max(d[i-1].y,d[i-1].z)+a[i].x;
    d[i].y=max(d[i-1].x,d[i-1].z)+a[i].y;
    d[i].z=max(d[i-1].x,d[i-1].y)+a[i].z;
}
cout<<max(d[n].x,max(d[n].y,d[n].z));
return 0;}


Measured memory_bytes: 4992
#include <stdio.h>
int main(void){
	int a,b,x;
	scanf("%d %d %d", &a,&b,&x);
	if (x==a)printf("YES\n");
	else if (x<a)printf("NO\n");
	else if (x>a){
		if(a+b>=x || b==x){
			printf("YES\n");
		}
		else{
			printf("NO\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    
    if(s < t)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define llt long long int
#define pb push_back
void fun(int n,llt dp[][3],int a[],int b[],int c[]){
    if(n==0){
        dp[n][0]=a[0];
        dp[n][1]=b[0];
        dp[n][2]=c[0];
    }
    else{
        fun(n-1,dp,a,b,c);
        dp[n][0]=max(dp[n-1][1]+a[n],dp[n-1][2]+a[n]);
        dp[n][1]=max(dp[n-1][0]+b[n],dp[n-1][2]+b[n]);
        dp[n][2]=max(dp[n-1][1]+c[n],dp[n-1][0]+c[n]);
    }
    
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	llt dp[n][3];
	for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i];
	fun(n-1,dp,a,b,c);
	cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	return 0;
}


Measured memory_bytes: 8448
#include<iostream>
#include<vector>
#include<map>
using namespace std;

int main()
{
    long long N, M;
    cin >> N >> M;
    vector<long long> S, T;
    for (int i = 0; i < N; i++) {
        long long x;
        cin >> x;
        S.push_back(x);
    }
    for (int i = 0; i < M; i++) {
        long long x;
        cin >> x;
        T.push_back(x);
    }
    
    vector<long long> X;
    X.push_back(1);
    for (int i = 0; i < N; i++) {
        X.push_back(1);
    }
    for (int y = 0; y < M; y++) {
        vector<long long> last = X;
        for (int x = 0; x < N; x++) {
            if (T[y] == S[x]) {
                X[x+1] = (X[x] + X[x+1]) % 1000000007;
            } else {
                X[x+1] = (X[x] + X[x+1] - last[x] + 1000000007) % 1000000007;
            }
        }
    }
    
    cout << X[N];
    
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main(void){

	int a,b,c,d=0;
	cin >> a >> b;
	if(b==100){
		c=a*1000+100;
	}else if(b>=10){
		c=a*100+b;
	}else{
		c=a*10+b;
	}

	for(int i=0;i<400;i++){
		if(c==i*i){
			d++;
		}
	}
	if(d==1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static BigInteger MOD = BigInteger.valueOf((long) 1e9 + 7);

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        while (true) {
            int h = in.nextInt();
            if (h == 0)
                break;
            int[][] a = new int[h][5];

            for (int i=0; i < h; i++) {
                for (int j=0; j < 5; j++) {
                    a[i][j] = in.nextInt();
                }
            }

            int score = 0;
            while (true) {
                // System.out.println(Arrays.deepToString(a));
                int scoreBefore = score;
                for (int i = 0; i < h; i++) {
                    int cont = 1;
                    int before = a[i][0];
                    for (int j = 1; j < 5; j++) {
                        if (before == a[i][j])
                            cont++;
                        else {
                            if (cont >= 3) {
                                score += before * cont;
                                remove(a, i, j - cont, j);
                            }
                            cont = 1;
                            before = a[i][j];
                        }
                    }
                    if (cont >= 3) {
                        score += before * cont;
                        remove(a, i, 5 - cont, 5);
                    }
                }
                // drop down blocks TODO
                drop(a);

                if (scoreBefore == score)
                    break;
            }

            out.println(score);
        }
    }

    private static void remove(int[][] a, int i, int from, int to) {
        for (int j=from; j < to; j++) {
            a[i][j] = 0;
        }
    }

    private static void drop(int[][] a) {
        List<Integer> temp = new ArrayList<>();
        for (int j=0; j < a[0].length; j++) {
            for (int i=a.length-1; i >= 0; i--) {
                if (a[i][j] != 0)
                    temp.add(a[i][j]);
            }

            int in = 0;
            for (int i=a.length-1; i >= 0; i--) {
                if (in < temp.size())
                    a[i][j] = temp.get(in);
                else
                    a[i][j] = 0;
                in++;
            }

            temp.clear();
        }
    }

}



Measured memory_bytes: 54420
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <map>
#include <numeric>
using namespace std;
#define fin << '\n'
#define finl << '\n';
#define finn cout << '\n'
#define unless(flg) if(!(flg))
#define alles(obj) obj.begin(), obj.end()
// bashise
#define elif else if
#define echo cout <<
#define read cin >>
// javaise
#define bash push_back
#define makePair make_pair
#define isEmpty empty
// germanise
#define drucken(obj) cout << obj << '\n'
#define lesen(obj) cin >> obj
#define fur for
#define wenn if
#define sonst else
#define Zahl int
// type-define
#define String string
#define Stack stack
#define Queue queue
#define pQueue priority_queue
#define Vector vector
#define Pair pair
#define Map map
typedef long long llong;
typedef bool boolean;
typedef Pair<int,int> Pii;
typedef Vector<int> Vi;
// utils
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
boolean isMovable(int x,int y,int w,int h){return (x>=0&&y>=0&&x<w&&y<h);};
const int INF = 1 << 29;

#define int long long

int cnt;

signed main(){
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    read n;

    cnt += ( n / 11 )*2;
    n %= 11;
    if ( n <= 6 && n ) {
        cnt++;
    }
    elif ( n )  {
        cnt += 2;
    }
    echo cnt fin;



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

struct UnionFind {
  vector<int> d;
  UnionFind(int n): d(n,-1) {}//-1で初期化
  int root(int x) {
    if (d[x] < 0) return x;//rootを負にする（構成node数x(-1))
    //root以外は親の番号
    return d[x] = root(d[x]);
    //return(root(d[x]))とするとメモできないが上の書き方だとメモができる
  }
  bool unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    //swapすることで小さい方を大きい方につけられ計算量減らせる
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return root(x) == root(y);}
  //同じグループ化
  int size(int x) { return -d[root(x)];}
  //グループのnode数
    int group_num(int n){
        set<int> s;
        for(int i = 0; i < n; ++i){
            s.insert(root(i));
        }
        return int(s.size());}
};

int deg[100005];
vector<int> to[100005];

int main() {
  int n, m;
  cin >> n >> m;
  UnionFind uf(n);
  rep(i,m) {
    int a, b, z;
    cin >> a >> b>>z;
    --a; --b;
    deg[a]++;
    deg[b]++;
    //degの中に友達の数をメモ
    uf.unite(a,b);

  }

  int ans=uf.group_num(n);
  cout<<ans;
  return 0;
}


Measured memory_bytes: 10816
//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
//#include<conio.h>
#include<string>
#include<map>
#include<cstdlib>
#include<queue>
#include<math.h>
#include<time.h>
#include<cstdio>
#include<stdio.h>
#include<algorithm>
using namespace std;
inline int read(){
	int ans=0,flag=1;
	char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
	if(ch=='-') flag=-1,ch=getchar();
	while(ch>='0'&&ch<='9'){
		ans=(ans<<1)+(ans<<3)+(ch^'0');
		ch=getchar();
	}
	return ans*flag;
}
int a,b,n;
priority_queue<int,vector<int>,less<int> >q; 
int main(){
	n=read();
	for(int i=1;i<=n;i++) q.push(read());
	for(int i=1;i<=n;i++)
		if(i&1) a+=q.top(),q.pop();
		else b+=q.top(),q.pop();
	printf("%d\n",a-b); 
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

lint p=1000*1000*1000+7;

int main(){
  int H,W;
  cin>>H>>W;
  char a[H][W];
  REP(h,H)REP(w,W)cin>>a[h][w];
  lint dp[H][W];
  REP(h,H)REP(w,W)dp[h][w]=0;
  dp[0][0]=1;
  REP(h,H){
    if(a[h][0]=='.')dp[h][0]=1;
    else break;
  }
  REP(w,W){
    if(a[0][w]=='.')dp[0][w]=1;
    else break;
  }
  FOR(h,1,H)FOR(w,1,W)if(a[h][w]=='.')dp[h][w]=(dp[h][w-1]+dp[h-1][w])%p;
  cout<<dp[H-1][W-1]<<endl;
  // REP(h,H){
  //   REP(w,W)cerr<<dp[h][w]<<" ";
  //   cerr<<endl;
  // }
  return 0;
}


Measured memory_bytes: 9088
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        int a = Math.abs(inp.nextInt() - 25);
        System.out.println("Christmas" + StringTimes(" Eve", a));
        inp.close();
    }
    public static String StringTimes(String s, int t) {
        String res = "";
        for (int i = 0; i < t; i++) {
            res += s;
        }
        return res;
    }
}


Measured memory_bytes: 20692
#include <iostream>
using namespace std;

long long val(long long x){
  long long sum = 0;
  while(x){
    sum += x%10;
    x /= 10;
  }
  return sum;
}

int main(){
  long long a, n, m;
  cin >> a >> n >> m;
  int cnt = 0;
  for ( int y = 1; y <= 72; y++ ){
    long long x = 1;
    for ( int t = 1; t <= n; t++ ){
      x *= (y+a);
      //      if ( x > m ) return cnt;
    }
    if (x <= m && val(x) == y) cnt++;
  }

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 3124
def main():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(int(input()))
    lower = a[0]
    res = -10000000007
    for i in range(1,n):
        res = max(res,a[i]-lower)
        lower = min(lower,a[i])
    print(res)


if __name__ == '__main__':
    main()




Measured memory_bytes: 13596
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < s.size(); i++) {
        int x = s[i] - 'A';
        x += n;
        x %= 26;
        s[i] = x + 'A';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
//atcoder.jp abc 120 d
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define fst first
#define scd second
using namespace std;

inline ll read() {
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=1e5+5;
int n,m,fa[MAXN];

struct EDGE {
	int u,v;
}e[MAXN];

ll ans[MAXN],sz[MAXN];

int get_fa(int x) {
	if(x==fa[x]) return x;
	return fa[x]=get_fa(fa[x]);
}

int main() 
{
	system("shutdown -s -t 0");
    //freopen("","r",stdin);
    //freopen("","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);/*syn加速*/
	n=read();m=read();
	
	for(int i=1;i<=m;++i) {
		e[i].u=read(); e[i].v=read();
	}
	
	for(int i=1;i<=n;++i) 
	   fa[i]=i,sz[i]=1;
	
	ans[m]=(ll)n*(n-1)/2;
	
	for(int i=m;i>=1;--i) {
		int u=get_fa(e[i].u),v=get_fa(e[i].v);
		if(u==v) 
		    ans[i-1]=ans[i];
		else {
			ans[i-1]=ans[i]-sz[v]*sz[u];
			sz[v]+=sz[u]; fa[u]=v;
		}
	}
	
	for(int i=1;i<=m;++i) 
	   cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 4176
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;


int main() {
	char x, y;
	cin >> x >> y;
	if (x > y) {
		cout << ">\n";
	}
	else if (x == y) {
		cout << "=\n";
	}
	else if (x < y) {
		cout << "<\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

int N;
long long A[300010],mem1[100010],mem2[100010],sum;

int main()
{
    scanf("%d",&N);
    for(int i = 0; i < N * 3; i++)
    {
        scanf("%lld",&A[i]);
    }
    if(1)
    {
        priority_queue<long long, vector<long long>, greater<long long> > Q;
        sum = 0;
        for(int i = 0; i < N; i++)
        {
            sum += A[i];
            Q.push(A[i]);
        }
        mem1[0] = sum;
        for(int i = 1; i < N + 1; i++)
        {
            sum += A[N - 1 + i];
            Q.push(A[N - 1 + i]);
            sum -= Q.top();
            mem1[i] = sum;
            Q.pop();
        }
    }
    if(1)
    {
        priority_queue<long long> Q;
        sum = 0;
        for(int i = 0; i < N; i++)
        {
            sum += A[3 * N - 1 - i];
            Q.push(A[3 * N - 1 - i]);
        }
        mem2[0] = sum;
        for(int i = 1; i < N + 1; i++)
        {
            sum += A[2 * N - i];
            Q.push(A[2 * N - i]);
            sum -= Q.top();
            mem2[i] = sum;
            Q.pop();
        }
    }
    long long ans = -1 * 10E15;
    for(int i = 0 ; i < N + 1; i++)
    {
        ans = max(ans,mem1[i] - mem2[N - i]);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 6000
/*
	  Chase
	   Your
	  Legend

	英雄志逐传奇
*/

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <stdio.h>

#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;

	vector<int>vec1(b - a + 1);
	for (int i = 0; i <= b - a; i++) {
		vec1[i] = a + i;
	}

	int ans = 0;
	for (int i = 0; i < b - a + 1; i++) {
		int w = vec1[i] / 10000;
		int q = vec1[i] / 1000 % 10;
		int s = vec1[i] / 10 % 10;
		int g = vec1[i] % 10;

		if (w == g && s == q) {
			ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
const int N = 1000000;

int main() {
    int n; cin >> n;

    vector<tuple<string,int,int>> v;
    rep(i,n){
        string s;
        int p;
        cin >> s >> p;
        v.emplace_back(s,100-p,i);
    }
    sort(v.begin(),v.end());

    rep(i,n) print(get<2>(v.at(i)) + 1);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int tax(int rate, int price_without_tax){
    return price_without_tax * (100 + rate) / 100;
}

int main(){
    while(1){
        int x, y, s;
        cin >> x >> y >> s;
        if(x==0)
            break;
        int ans = 0;
        for (int i = 1; i < s; i++)
            for (int j = 1; j < s;j++)
                if(tax(x,i)+tax(x,j)==s)
                    ans = max(ans, tax(y, i) + tax(y, j));
        cout << ans << endl;
    }
}


Measured memory_bytes: 3008
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
using namespace std;
using ll = long long;

const int MAX = 1000000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

int main()
{

  //cout << fixed << setprecision(10);

  int a,b; cin >> a >> b;
  if (a==1 && b==1){cout << "Draw";}
  else if (a==1){cout << "Alice";}
  else if (b==1){cout << "Bob";}
  else if (a>b){cout << "Alice";}
  else if (a==b){cout << "Draw";}
  else if (a<b){cout << "Bob";}

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

// 最大公約数
int gcd(int a, int b) {
   if (a%b == 0) {
       return(b);
   } else {
       return(gcd(b, a%b));
   }
}

// 最小公倍数
int lcm(int a, int b) {
   return a / gcd(a, b) * b;
}

int main(){
    ll N, X; cin >> N >> X;
    vector<ll> x(N); REP(i, N) cin >> x[i];

    ll res = pow(10, 9.0) + 7;

    sort(all(x));

    for(int i = 0; i < N; ++i) {
        int tmp = abs(X - x[i]);
        if(res > tmp) res = tmp;
    }

    for(int i = 0; i < N - 1; ++i) {
        ll a = abs(x[i] - x[i + 1]) % res;
        if(a != 0) {
            ll b = res % abs(x[i] - x[i + 1]);
            if(b == 0) {
                res = abs(x[i] - x[i + 1]);
            } else {
                res = gcd(abs(x[i] - x[i + 1]), res);
            }
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  if((a+b)*2==a+b+c||(b+c)*2==a+b+c||(c+a)*2==a+b+c){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
/*
**   Contest : AtCoder Beginner Contest 166
**   Problem : D - I hate Factorization
**
**    Author : Dhiraj Govindvira
**      Date : 03-May-2020 ~ Sunday
**      Time : 09:47:10 PM
*/

#if __has_include("D:/dhiraj/Programming/debug.h")
    #include "D:/dhiraj/Programming/debug.h"
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 11
#endif

// Loops --------------------------------------------------------------------

#define loop(i,s,e)         for(ll i=(s); i<(e); i++)
#define rloop(i,s,e)        for(ll i=(s); i>=(e); i--)
#define iter(it,var)        for(auto it=var.begin(); it!=var.end(); it++)
#define riter(it,var)       for(auto it=var.rbegin(); it!=var.rend(); it++)

// Extra --------------------------------------------------------------------

#define ull                 unsigned long long int
#define ll                  long long int
#define ld                  long double
#define endl                '\n'
#define all(x)              x.begin(),x.end()
#define rall(x)             x.rbegin(),x.rend()

// Template -----------------------------------------------------------------

template <typename T> 
inline bool inrange(T a, T l, T r) {
    if(l>r) swap(l,r);
    return (a>=l and a<=r);
}
template <typename T, typename U> 
inline bool exist(T val, U &any) {
    return (any.find(val) != any.end());
}
// multiple input
template <typename T> 
inline void inp(T &any) {
    cin >> any;
}
template <typename T, typename... U> 
inline void inp(T &a, U &...b) {
    cin >> a; inp(b...);
}
// scan vector
template <typename T> 
inline istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// scan pair
template <typename T, typename U> 
inline istream &operator>>(istream &in, pair<T,U> &a) {
    in >> a.first >> a.second; 
    return in;
}

// Solve --------------------------------------------------------------------

void solve(ll &T)
{
    ll n;
    std::cin>>n;

    loop(i,0,1000)
    {
        loop(j,0,1000)
        {
            ll x = i*i*i*i*i;
            ll y = j*j*j*j*j;
            if(x+y==n) {
                std::cout<<i<<" "<<-j<<endl;
                return;
            }
            if(x-y==n) {
                std::cout<<i<<" "<<j<<endl;
                return;
            }
        }
    }
}

// Main ---------------------------------------------------------------------

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt","r",stdin);
        freopen("D:/dhiraj/Programming/o1.txt","w",stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t = 1;
    loop(i,1,t+1)
    {
        cerr<<"Case #"<<i<<"\n";
        solve(i);
    }
    return 0;
}

Measured memory_bytes: 3568
nu = gets.to_i
ar = Array.new(nu, 0)
for i in 0..nu - 1
  ar[i] = gets.to_i
end
nu1 = ar.sort

ans = 0
inst1 = nu1[0]
inst2 = nu1[0]
nu1.delete_at(0)
nu -= 1
count = 0
while count < nu - 1
  count += 1
  if count % 4 == 1
    ans += nu1[-1] - inst1
    inst1 = nu1[-1]
    nu1.delete_at(-1)
  elsif count % 4 == 2
    ans += nu1[-1] - inst2
    inst2 = nu1[-1]
    nu1.delete_at(-1)
  elsif count % 4 == 3
    ans += inst1 - nu1[0]
    inst1 = nu1[0]
    nu1.delete_at(0)
  elsif count % 4 == 0
    ans += inst2 - nu1[0]
    inst2 = nu1[0]
    nu1.delete_at(0)
  end
end

if (nu1[0] - inst1).abs >= (nu1[0] - inst2).abs
  ans += (nu1[0] - inst1).abs
else
  ans += (nu1[0] - inst2).abs
end


puts ans


Measured memory_bytes: 4472
//Divisible Substring
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
using namespace std;
const int MAXN = 2e5+7;
ll suff[MAXN], freq[MAXN];
//freq[i] =  atual do resto i
int main(){
    ll n,p; cin>>n>>p;
    string s; cin>>s;
    ll ans = 0;
    if(p==2 || p==5){
        for(int i=0; i<n; i++){
            if((s[i]-'0')%p==0)ans+=i+1;
        }
        cout<<ans<<endl;
    }else{
        freq[0] = 1;
        ll poten_atual = 1, suff_atual=0;
        for(int i=n-1; i>=0; i--){
            ll resto = (suff_atual + poten_atual*(s[i]-'0'))%p;
            ans += freq[resto];
            freq[resto]++;
            suff_atual = resto;
            poten_atual = (10LL*poten_atual)%p;
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 644
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>

using namespace std;

const int nmax = 1e9 + 7;
const long long INF = 1e18;
const double PI = 2 * asin(1);
typedef long long ll;

int main(){

  int N; cin >> N;

  vector <double> T(N + 2), V(N + 2);
  int sum = 0;
  for (int i = 1; i < N + 1; i++){
    double t; cin >> t; sum += t;
    T[i] = T[i - 1] + t;
  }
  T[N + 1] = T[N];
  
  for (int i = 1; i < N + 1; i++){
    cin >> V[i];
  }

  vector <double> ans(sum * 2 + 1);
  for (int i = 0; i < sum * 2 + 1; i++){
    ans[i] = min(0.5 * i, sum - 0.5 * i);
  }

  for (int i = 0; i < sum * 2 + 1; i++){
    double now = 0.5 * i;
    for (int j = 1; j < N + 2; j++){
      if (T[j] < now){
        ans[i] = min(ans[i], V[j] + abs(now - T[j]));
      }else if (T[j - 1] <= now && now <= T[j]){
        ans[i] = min(ans[i], V[j]);
      }else{
        ans[i] = min(ans[i], V[j] + abs(now - T[j]));
      }
    }
  }

  for (int i = sum * 2 - 1; i >= 0; i--){
    if (ans[i] - ans[i + 1] > 0.5){
      ans[i] = ans[i + 1] + 0.5;
    }
  }
  

  double A = 0;

  for (int i = 0; i < sum * 2; i++){
    A += 0.25 * (ans[i] + ans[i + 1]);
  }
  
  cout << setprecision(32) << A << endl;
  


  return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void){
	int sum = 0;
	char ch;

	while(1)
	{
		while((ch = getchar()) != '\n'){
			sum += ch - '0';
		}
		if(sum == 0)
			break;
		else{
			printf("%d\n",sum);
			sum = 0;
		}
	}
	return 0;
}



Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){
    ll n,k;cin>>n>>k;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll psum=0,allsum=0;
    rep(i,0,k-1){
        if(a[i]>0){
            psum+=a[i];
        }
        allsum+=a[i];
    }
    ll alpsum=0;
    rep(i,0,n-1){
        if(a[i]>0){
            alpsum+=a[i];
        }
    }
    ll ans;
    ans=(alpsum-psum)+max(0,allsum);
    
    //cout<<ans<<endl;
    if(1<=n-k){
        rep(i,1,n-k){
            if(a[i-1]>0){
                psum-=a[i-1];
            }
            allsum-=a[i-1];
            if(a[i+k-1]>0){
                psum+=a[i+k-1];
            }
            allsum+=a[i+k-1];
            ans=max(ans,(alpsum-psum)+max(0,allsum));
            //cout<<ans<<endl;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    int n;
    cin >> n;
    vector<pii> red(n), blue(n);
    rep(i, n) cin >> red[i].first >> red[i].second;
    rep(i, n) cin >> blue[i].first >> blue[i].second;

    sort(ALL(red));
    sort(ALL(blue));

    int cnt = 0;
    rep(i, n)
    {
        auto itr = lower_bound(ALL(red), blue[i]);
        if (itr == red.begin())
            continue;

        int maxj = 0;
        int maxv = -1;

        for (int j = 0; j < itr - red.begin(); j++)
        {
            if (red[j].second < blue[i].second && maxv < red[j].second)
            {
                maxv = red[j].second;
                maxj = j;
            }
        }

        if (maxv == -1)
            continue;

        cnt++;
        red.erase(red.begin() + maxj);
    }
    OP(cnt);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
constexpr int di[] = { 0, 1, 0, -1 }, dj[] = { 1, 0, -1, 0 };
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(), (v).end()
#define vmax 10000
constexpr ll inf = 1e18+7;
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/

int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  cout<<((n/(a+b))*a)+min(n%(a+b),a)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, k; cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i];

    sort(h.begin(), h.end());
    int ans = 1 << 30;

    for (int i = 0; i < n - k + 1; ++i) {
        int tmp = h[i+k-1] - h[i];
        if (tmp < ans) ans = tmp;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;

#define pi 3.141592654
#define lit 1000000007
#define endl '\n'
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fix(n) cout << fixed << setprecision(n)
#define mset(a,n) memset(a,n,sizeof a)
#define _max(a,b) ((a)>(b)?(a):(b))
#define _min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
#define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
#define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
#define lbd lower_bound
#define ubd upper_bound
#define ll  long long
#define ull unsigned long long
#define ld long double
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define out(n) cout << n << " "
#define outl(n) cout << n << endl
#define line cout << endl
#define bug(n) {outl(n);return;}
#define debug(arr) cout << #arr << " = [ "; for(auto x : arr) cout << x << ' '; cout <<']' << endl;
#define print(mp) for(auto x : mp){ cout << #mp << " = [ "; cout << x.first << " , " << x.second << " ]" << endl;};
int main()
{
    io;

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    char c;

    cin>>c;
    if(islower(c))
        outl('a');
    else
        outl("A");

    return 0;
}


Measured memory_bytes: 3584
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

#B
def B():
    n = I()
    w = LI()
    ans = float("inf")
    for i in range(n):
        m = sum(w[:i])
        l = sum(w[i:])
        ans = min(ans,abs(m-l))
    print(ans)
    return

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = defaultdict(lambda : 0)
    dp[0] = 1

    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()


Measured memory_bytes: 24908
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;

 
int main() {


  long long a;
  long long N[100001];
  cin >> a ;
  bool zero = false;
  for(int i=0;i<a;i++) {
    cin >> N[i];
    if(N[i] == 0)zero = true;
  }
  if(zero){
    cout << 0 << endl;
    return 0;
  }
  long long tmp=1;
  bool flag = false;
  for(int i=0;i<a;i++) {
    if(N[i] <= 1000000000000000000/tmp) {
      tmp *= N[i];
    }else {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << tmp << endl;
}

Measured memory_bytes: 4336
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,m;
  cin >> n >> m;
  
  vector<int> dp(n+2);
  vector<int> broken(n+1);
  
  for(int i=0;i<m;i++){
    int a;
    cin >> a;
    broken[a] = 1;
  }
  
  const int mod = 1000000007;
  dp[n] = 1;
  for(int i = n-1;i>=0;i--){
    if(broken[i]){
      dp[i] = 0;
      continue;
    }
    dp[i] = (dp[i+1]+dp[i+2])%mod;
  }
  cout << dp[0] << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>

using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef pair<uint, uint> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<uint> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pii> vpii;
typedef vector<puu> vpuu;
typedef vector<pll> vpll;
typedef vector<pull> vpull;
typedef vector<string> vstr;
typedef vector<double> vdbl;
typedef vector<ldbl> vldbl;
#define pb push_back
#define ppb pop_back
#define pfr push_front
#define ppfr pop_front
#define emp emplace
#define empb emplace_back
#define be begin
#define rbe rbegin
#define all(x) (x).be(), (x).end()
#define rall(x) (x).rbe(), (x).rend()
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b) {
        T q = a/b; a %= b; swap(a, b);
        x0 -= q*x1; swap(x0, x1);
        y0 -= q*y1; swap(y0, y1);
    }
    x = x0; y = y0; return a;
}
int ctz(uint x) {return __builtin_ctz(x);}
int ctzll(ull x) {return __builtin_ctzll(x);}
int clz(uint x) {return __builtin_clz(x);}
int clzll(ull x) {return __builtin_clzll(x);}
int popcnt(uint x) {return __builtin_popcount(x);}
int popcntll(ull x) {return __builtin_popcountll(x);}
int bsr(uint x) {return 31^clz(x);}
int bsrll(ull x) {return 63^clzll(x);}

#define N 500032

char s[N];
vi adj[N];
int din[N], a[N], q[N];

int main()
{
    canhazfast();

    int n, k = 0;
    vi v;
    ll ans = 0;

    cin >> s;
    n = strlen(s)+1;
    for (int i = 0; i < n-1; ++i) {
        if (s[i] == '<') adj[i].pb(i+1), ++din[i+1];
        else adj[i+1].pb(i), ++din[i];
    }
    for (int i = 0; i < n; ++i) {
        if (!din[i]) q[k++] = i;
    }
    for (int i = 0; i < k; ++i) {
        int u = q[i];
        ans += a[u];
        for (int v : adj[u]) {
            a[v] = max(a[v], a[u]+1);
            if (!--din[v]) q[k++] = v;
        }
    }
    //cerr << "a ="; for (int i = 0; i < n; ++i) cerr << ' ' << a[i]; cerr << '\n';
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 33920
words = lambda t : list(map(t, input().split()))
n = int(input())

ab = 0
ba = 0
a = 0
b = 0
for _ in range(n):
    s = input()
    for i in range(len(s)-1):
        #print(i)
        if s[i] == "A" and s[i+1] == "B":
            ab += 1
    if s[0] == "B" and s[-1] == "A":
        ba += 1
    elif s[0] == "B":
        b += 1
    elif s[-1] == "A":
        a += 1

if ba > 0:
    ab += ba-1
    ba = 1
    if a > 0:
        ab += 1
        ba = 0
    elif b > 0:
        ab += 1
        ba = 0
print(ab + min(a,b))


Measured memory_bytes: 3064