akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

long long a[305][305],b[305][305],sum;
bool vis[305][305];
int n;

void FW1()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                b[i][j] = min(b[i][j],(b[i][k]+b[k][j]));
            }
        }
    }
    return;
}

void FW2()
{
    sum = 0;
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                long long x = a[i][j];
                long long y = a[i][k]+a[k][j];
                if(k!=i && k!=j && y==x)    vis[i][j] = vis[j][i] = true;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(!vis[i][j])  sum += a[i][j];
        }
    }
    sum /= 2;
    return;
}

long long check()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(b[i][j]!=a[i][j])    return  -1;
        }
    }
    FW2();
    return  sum;
}

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%lld",&a[i][j]);
            b[i][j] = a[i][j];
        }
    }
    FW1();
    printf("%lld\n",check());
    return  0;
}


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

using namespace std;

using i64 = long long;

const i64 MOD = 998244353;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    for(int i = 0; i < m; ++i){
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        int uu, vv;
        tie(uu, vv) = minmax(u[i], v[i]);
        u[i] = uu, v[i] = vv;
    }
    if(m % 2 == 1){
        cout << -1 << endl;
        return 0;
    }
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }
    vector<int> siz(n, -1);
    vector<vector<int>> g(n), h(n);
    set<pair<int,int>> ss;
    function<void(int,int)> f = [&](int x, int pre){
        siz[x] = 0;
        for(auto y : edges[x]){
            if(siz[y] == -1){
                f(y, x);
                siz[x] += siz[y] + 1;
                g[x].push_back(y);
            }
            else if(y != pre && ss.find(minmax(x, y)) == ss.end()){
                ++siz[x];
                ss.emplace(minmax(x, y));
                h[x].push_back(y);
            }
        }
    };
    f(0, -1);
    set<pair<int,int>> e;
    function<void(int)> gf = [&](int x){
        for(auto y : g[x]){
            if(siz[y] % 2 == 1)
                e.emplace(y, x);
            else
                e.emplace(x, y);
            gf(y);
        }
        for(auto y : h[x]){
            e.emplace(x, y);
        }
    };
    gf(0);
    for(auto& p : e)
        cout << p.first + 1 << " " << p.second + 1 << endl;
}




Measured memory_bytes: 29952
#include<iostream>
using namespace std;
int main(){
    int n;
    int A[200];
    cin >> n;
    int count = 0;
    for (int i = 0;i < n;i++) cin >> A[i];
    while (true){
        bool odd = false;
        for (int i = 0;i < n;i++){
            if (A[i] % 2 == 1) odd = true;
        }
        if (odd) break;
        for (int j = 0;j < n;j++){
            A[j] /= 2;
        }
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int,int>;
/* ちゃんと考えてわかって実装 */

int main(void){
    ll n;
    cin >> n;
    vector<ll> A(n);
    for(ll i=0; i<n; i++){
        cin >> A[i];
    }
    sort(A.rbegin(), A.rend());
    ll a, b;
    ll cnt = 0;
    for(int i=0; i<n-1; i++){
        if(A[i] == A[i+1] && cnt == 0){
            a = A[i];
            cnt++;
            i++; // 重複防止
        }
        else if(A[i] == A[i+1] && cnt == 1){
            b = A[i];
            cnt++;
        }
    }
    if(cnt == 2) cout << a * b << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 4004
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define endl "\n"
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);

    int k,a,b;
    cin >> k >> a >> b;
    for (int i=a;i<=b;i++)
    {
        if (i%k==0)
        {
            cout << "OK" << endl;
            return 0;
        }
    }

    cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3660
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int N, X[202020], Y[202020];

int main() {
    cin >> N;
    for (int j = 0; j < N; ++j) { cin >> X[j]; Y[j] = X[j]; }
    sort(Y, Y+N);
    for (int j = 0; j < N; ++j) {
        if (X[j] >= Y[N/2]) {
            cout << Y[(N-1)/2] << endl;
        } else {
            cout << Y[N/2] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int n;
  cin >> n;
  ll sum = 0;
  rep1(i,n){
    if(i%3==0 || i%5==0) continue;
    else sum += i;
  }
cout << sum << endl;
  return 0;
    

}


Measured memory_bytes: 3648
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int x,y,z,n;
	scanf("%d %d %d",&x,&y,&z);
	n=(x-z)/(y+z);

	printf("%d\n",n);
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String args[]){
    	Scanner scan = new Scanner(System.in);

    	int a = Integer.parseInt(scan.next());
    	int b = Integer.parseInt(scan.next());

    	if( a + b >= 10){
    		System.out.println("error");
    	}
    	else{
    		System.out.println(a + b);
    	}

    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n; cin >> n;
	int64_t a[n]; rep(i,n) cin >> a[i];
	sort(a, a + n);
	reverse(a, a + n);
	int64_t ans = a[0];
	int cnt = n - 2;
	for(int i = 1; i < n; ++i) {
		if(cnt <= 0) break;
		if(cnt > 1) {
			cnt -= 2;
			ans += a[i] * 2;
		} else if(cnt > 0) {
			cnt--;
			ans += a[i];
		}
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 5196
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	int n;
	cin >> n;
	vector <int> a(n);
	vector <lli> summ(n + 1,0);
	for(int i = 0;i < n;++i){
		cin >> a[i];
		summ[i + 1] = summ[i] + a[i];
	}
	lli ans = 0;
	for(int i = 0;i < n;++i){
		ans = ans + ((lli)a[i] * ((summ[n] - summ[i + 1]) % mod)) % mod;
		ans = ans % mod;
	}
	cout << (ans + mod) % mod << newl;

	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 5512
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>

typedef long double ld;
typedef long long ll;

using namespace std;

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

	while (true) {
		c -= b;
		if (c <= 0) {
			cout << "Yes";
			return 0;
		}
		a -= d; 
		if (a <= 0) {
			cout << "No";
			return 0;
		}
	}
	

	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define MOD 1000000007
 
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
template<class T>void print(T x){cout << x << endl;}
template<class T>void printvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} cout << a[a.size()-1] << endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
int main()
{
    int n, x, y; cin >> n >> x >> y;
    int dist[n][n]={};
    rep(i, n) FOR(j, i+1, n) dist[i][j] = j-i;

    vector<int> ans(n, 0);

    // rep(i, n){
    //     rep(j, n){
    //         printf("%d ", dist[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("\n");

    rep(i, n){
        FOR(j, i+1, n){
            chmin(dist[i][j], abs(x-1-i) + abs(y-1-j)+1);
            ans[dist[i][j]]++;
        }
    }

    // rep(i, n){
    //     rep(j, n){
    //         printf("%d ", dist[i][j]);
    //     }
    //     printf("\n");
    // }
    // printf("\n");
    FOR(i, 1, n){
        printf("%d\n", ans[i]);
    }
    
    return 0;
}

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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 60, M = 1010;

int n;
int cnt[M];
LL m;

int main()
{
	scanf("%d%lld", &n, &m);
	for (int i = 0; i < n; i ++ )
	{
		LL x;
		scanf("%lld", &x);
		for (int j = 0; j < N; j ++ ) cnt[j] += (x >> j) & 1;
	}
	
	int u = -1;
	for (int i = N - 1; i >= 0; i -- )
		if ((m >> i) & 1)
		{
			if (n - cnt[i] > cnt[i]) cnt[i] = n - cnt[i];
			else
			{
				u = i;
				break;
			}
		}
		
	for (int i = u - 1; i >= 0; i -- )
		if (n - cnt[i] > cnt[i])
			cnt[i] = n - cnt[i];
	
	LL res = 0;
	for (int i = 0; i < N; i ++ ) res += (LL)cnt[i] * (1LL << i);
	printf("%lld\n", res);
	return 0;
}

Measured memory_bytes: 256
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String temp = sc.nextLine();

        SimpleDateFormat df = new SimpleDateFormat("yyyy/MM/dd");

        try {
            Date a = df.parse(temp);

            if (a.compareTo(df.parse("2019/04/30")) <= 0) {
                System.out.println("Heisei");
            } else {
                System.out.println("TBD");
            }

        } catch (Exception ex) {
            ex.printStackTrace();
        }

    }

}


Measured memory_bytes: 22096
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        //値を取得
        Scanner sc = new Scanner(System.in);
        int N= sc.nextInt();
        long[] A = new long[N];
        long result = 1;    //計算結果を格納
        long max = (long)Math.pow(10,18);   //上限
        
        for (int i = 0; i < N; ++i){
            A[i] = sc.nextLong();
            //0が含まれている場合は何を掛けても0になるため、ここで終了
            if (A[i] == 0){
                System.out.println(0);
                System.exit(0);
            }
        }
        
        //配列を昇順にソート
        Arrays.sort(A);
        
        //各要素を順番に乗算する
        for (int i = 0; i < N; ++i){
            
            if (A[i] > max/result){ //上限を超えそうなら終了
               result = -1;
            } else{ //超えなければ乗算を続行
                result *= A[i];
            }
        }
        
        //出力
        System.out.println(result);
    }
}

Measured memory_bytes: 61960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

template<typename T>
struct BIT {
    int n;
    vector<T> dat;
 
    BIT(int n=0){
        initialize(n);
    }
 
    void initialize(int nin){
        n = nin;
        dat.resize(n);
        for(int i = 0; i<n; i++) dat[i] = 0;
    }
 
    T sum(int i){
        T s = 0;
        while(i >= 0){
            s += dat[i];
            i = (i & (i+1)) - 1;
        }
        return s;
    }
 
    T sum_between(int i, int j){
        if(i > j) return 0;
        return sum(j) - sum(i-1);
    }
 
    void plus(int i, T x){
        while(i < n){
            dat[i] += x;
            i |= i+1;
        }
    }
 
    // a[0]+...+a[ret+1] >= x
    int lower_bound(T x){
        int ret = -1;
        int k = 1;
        while(2*k <= n) k <<= 1;
        for( ;k>0; k>>=1){
            if(ret+k < n && dat[ret+k] < x){
                x -= dat[ret+k];
                ret += k;
            }
        }
        return ret + 1;
    }
};

int main(){
  int n,m;cin>>n>>m;
  int l[n],r[n];
  rep(i,n){
    cin>>l[i]>>r[i];
    l[i]--;r[i]--;
  }
  vector<int> w[m];
  rep(i,n)w[r[i]-l[i]].push_back(i);
  BIT<int> bit(m+1);
  int stablen=n;
  rep(i,m){
    int s=0;
    int k=i+1;
    for(int x=k;x<=m;x+=k){
      s+=bit.sum(x-1);
    }
    cout<<stablen+s<<endl;

    rep(j,w[i].size()){
      int lri=w[i][j];
      bit.plus(l[lri],1);
      bit.plus(r[lri]+1,-1);
      stablen--;
    }
  }
}


      

Measured memory_bytes: 9088
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
B = list(map(int, input().split()))

A = [INF] * N
for i in range(N-1):
    A[i] = min(A[i], B[i])
    A[i+1] = min(A[i+1], B[i])
    # print(A)
ans = sum(A)
print(ans)

Measured memory_bytes: 8872
#include <iostream>
using namespace std;
int n, m, c[21];

int coin(){
    int d[50001]={0};
    d[0] = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j+c[i]<=n; j++){
            if(d[j+c[i]] == 0)  d[j+c[i]]=d[j]+1;
            else d[j+c[i]]=min(d[j+c[i]], d[j]+1);
        }
    }//1~nまでそれぞれで必要なコインの最小枚数を出してく。
    return d[n];
}

int main(void){
    cin >> n >> m;
    for(int i=0; i<m; i++)  cin >> c[i];
    cout << coin() << endl;
    return 0;
}



Measured memory_bytes: 3292
#include <iostream>
#include <algorithm>
using namespace std;
int a,b,c;
int main(){
  cin>>a>>b>>c;
  if(max(max(a,b),c)-(a+b+c-max(max(a,b),c))==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}

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

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

int main(){
  ll n,m;
  cin>>n>>m;
  ll a[m];
  ll count=0;
  rep(i,m){
    cin>>a[i];
    count+=a[i];
  }
  if(n-count>=0)
    cout<<n-count<<endl;
  else
    cout<<-1<<endl;

  return 0;
}


Measured memory_bytes: 3716
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define MOD 1e9+7
typedef long long llong;
using namespace std;

int main(){
	int n;
	cin>>n;
	
	int dp[101][4][4][4]={0};//dp[i][k][l][m]は長さiで後ろ４文字がj,k,l,mと並ぶ文字列の場合の数."TAGC"=0123とおく.
	REP(i,4){
		REP(j,4){
			REP(k,4){
				if((i==1&&j==2&&k==3)||(i==1&&j==3&&k==2)||(i==2&&j==1&&k==3)) dp[3][i][j][k]=0;
				else dp[3][i][j][k]=1;
			}
		}
	}
	for(int i=3;i<n;++i){
		REP(j,4){
			REP(k,4){
				REP(l,4){
					REP(m,4){
						if(k==1&&l==2&&m==3) continue;
						if(k==1&&l==3&&m==2) continue;
						if(k==2&&l==1&&m==3) continue;
						if(j==1&&k==2&&m==3) continue;//AG*C.
						if(j==1&&l==2&&m==3) continue;//A*GC.
						
						dp[i+1][k][l][m]+=dp[i][j][k][l];
						dp[i+1][k][l][m]%=(int)MOD;
					}
				}
			}
		}
	}
	
	llong ans=0;
	REP(i,4){
		REP(j,4){
			REP(k,4){
				ans+=dp[n][i][j][k];
				ans%=(int)MOD;
			}
		}
	}	
	
	cout<<ans<<endl;
	return 0;
}//abc122_d.復習.解答参考.

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int A,B;
	cin>>A>>B;
	string a="",b="";
	for(int i=0;i<B;++i) a+=char('0'+A);
	for(int i=0;i<A;++i) b+=char('0'+B);
	cout<<min(a,b);
	return 0;
}

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

int main() {
  int N, X, T;
  cin >> N >> X >> T;
  if (N % X == 0) {
    cout << N / X * T << endl;
  }
  else {
    cout << (N - N % X) / X * T + T << endl;
  }
}

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

int main() {
    int n; cin >> n;
    vector<int> S(n);
    for(int i=0; i < n; ++i){
        cin >> S.at(i);
    }
    int q; cin >> q;
    
    int C=0;
    int T;
    for(int i=0; i < q; ++i){
        cin >> T;
        if(binary_search(S.begin(),S.end(),T)){
            ++C;
        }
    }
    
    cout << C <<endl;
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
//Remove below header file if c++ version greater than 14
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>

#define ll long long int
#define pb push_back
#define mp make_pair
#define all(X) X.begin(), X.end()
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define deb(x) cout << #x << " "<< x << endl;
#define fo(i, n) for(i=0; i<n; i++)
#define Fo(i, k, n) for(i=k; i<n; i++)

using namespace std;
using mii=map<int, int>;
using mll=map<ll, ll>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int mod = 1000000007;

ll desc(ll x, ll y)
{
    return x > y;
}

void solve(map<int, vi> & ma, vector<int>& arr, int p, int x)
{
    if(p != -1)
    arr[x] += arr[p];

    for(auto c: ma[x])
    {
        if(c != p)
            solve(ma, arr, x, c);
    }
}

int main() {
    fastIO

    int n, Q, i;
    cin >> n >> Q;
//    bool visited[n + 1];

    map<int, vi> ma;
    vector<int> arr(n + 1, 0);
    fo(i, n - 1) {
        int a, b;
        cin >> a >> b;
        ma[a].push_back(b);
        ma[b].push_back(a);
    }

    while(Q--)
    {
        int p,q;
        cin >> p >> q;
        arr[p] += q;
    }
    solve(ma, arr, -1, 1);

    for(i =1; i <= n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 43776
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
char s[510][510];
int dp[510][510];
int gcd(int a,int b) {
    return a%b?gcd(b,a%b):b;
}
int long long n;
int main(){
    long long n;
    int t,k;
    char x[10];
    string s;
    while (scanf("%lld",&n)!=EOF) {
        s.clear();
        while (n) {
            int tmp = (n%26==0?26:n%26);
            s.append(1,tmp+'a'-1);
            n-=tmp;
            n/=26;
        }
        if (n)
           s.append(1,n+'a'-1);
        reverse(s.begin(),s.end());
        cout << s << endl;

    }

    return 0;
}


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

typedef long long ll;

using namespace std;

namespace Solver {

    int N, M, r, q;
    vector<int> t, n, m, s, qts, qte, qm;
    inline bool Read() {
        cin >> N >> M;
        if (N == 0) return false;

        cin >> r;
        t.resize(r);
        n.resize(r);
        m.resize(r);
        s.resize(r);
        for (int i = 0; i < r; i++) cin >> t[i] >> n[i] >> m[i] >> s[i];

        cin >> q;
        qts.resize(q);
        qte.resize(q);
        qm.resize(q);
        for (int i = 0; i < q; i++) cin >> qts[i] >> qte[i] >> qm[i];

        return true;
    }

    inline void Work() {
        for (int i = 0; i < q; i++) {
            int ans = 0, pc = 0, st = 0;
            for (int j = 0; j < r; j++) {
                if (qm[i] == m[j]) {
                    if (s[j] == 1) {
                        if (pc == 0) st = t[j];
                        pc++;
                    } else {
                        if (pc == 1) ans += max(0, min(qte[i], t[j]) - max(qts[i], st));
                        pc--;
                    }
                }
            }

            cout << ans << endl;
        }
    }

    inline void Solve() {
        while (Read()) Work();
    }
}

int main() {
    Solver::Solve();
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define SQ(a) (a)*(a)

int level[200011];

vector<int> g[200011];
ll n,k,p,m,s;
ll arr[200011];
bool vis[200011];
queue<int> q;

void bfs(int node,int d)
{
	if(vis[node])
		return;
	//vis[node]=1;
	q.push(node);
	level[1] = 1;
	while(!q.empty())
	{
		int temp = q.front();
		q.pop();
		if(!vis[temp])
		{
			vis[temp] = 1;
			for(int i=0;i<g[temp].size();i++)
			{
				if(vis[g[temp][i]])
					continue;
				level[g[temp][i]] = level[temp]+1;
				q.push(g[temp][i]);
			}
		}
	}
	return;
}
int main(){

	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	bfs(1,1);
	//for(int i=1;i<=n;i++)
	//	cout<<level[i]<<" ";
	if(level[n] - level[1] == 2)
		cout<<"POSSIBLE";
	else
		cout<<"IMPOSSIBLE";
	return 0;
}


Measured memory_bytes: 13424
#include<bits/stdc++.h>
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;

int main(){
    int N, K;  cin >> N >> K;
    vector<int> h(N+1,0);
    for(int i=1; i<=N; i++){
        cin >> h[i];
    }

    vector<int> dp(N+1, 1e9);
    dp[1] = 0;
    for(int i=2; i<=N; i++){
        for(int k=1; k<=K; k++){
            if(i-k<1) break;
            dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]));
        }
    }
    cout << dp[N] << endl;
}


Measured memory_bytes: 1152
n = int(input())

number = [[0]*10 for _ in range(10)]

for _ in range(1, n+1):

    s=str(_)
    i=int(s[0])
    j=int(s[-1])

    number[i][j] += 1

count = 0
for i in range(10):

    for j in range(10):
        count += number[i][j]*number[j][i]

print(count)

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

#define ll long long int
#define pi pair<ll,ll>

ll power(ll x, ll y, ll mod = 1e9+7){
    ll res = 1;
    while(y > 0){
        if(y & 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x*x)% mod;
    }
    return res % mod;
}

void solve(){
    int n, m;   cin >> n >> m;
    int ans = 0;
    vector<ll> v(n);
    for (int i = 0; i < n; i += 1) {
        cin >> v[i];
    }

    ll sum = accumulate(v.begin(), v.end(), 0LL);
    for (int i = 0; i < n; i += 1) {
        if (v[i]*4*m >= sum)
            ans += 1;
    }
    
    if (ans >= m)
        cout << "Yes\n";
    else 
        cout << "No\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);	cout.tie(0);

    int test = 1;
    // cin >> test;
    while(test--)
        solve();
    return 0;
}

Measured memory_bytes: 256
/* * * * * * * * * * * **
*                      *
*	   saurabh8522	   *
*	  I will handle	   *
*		   it.		   *
*                      *
* * * * * * * * * * * **/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ld long double
#define zero(a) memset((a),0,sizeof((a)))
#define one(a) memset((a),1,sizeof((a)))
#define minus(a) memset((a),-1,sizeof((a)))
#define all(g) g.begin(),g.end()
#define ppb pop_back
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> //indexed_set;
typedef long long int ll;
#define MOD 1000000007
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll modpow(ll a,ll b,ll m) {ll res=1;a%=m;for(;b;b>>=1){if(b&1)res=res*a%m;a=a*a%m;}return res;}
ll numdigit(ll n){return floor(log10(n)) + 1;}
bool isPowerTwo (ll x) { return x && (!(x&(x-1))); }
ll power5(ll a){
	ll ans=a*a;
	ans*=ans;
	return ans*a;
} 
int  main(){
	FastRead;
	ll t=1;
	// cin>>t;
	while(t--){
		ll x;
		cin>>x;
		for(int i=-120;i<=120;i++){
			for(int j=-120;j<=120;j++){
				if(power5(i)-power5(j)==x){
					cout<<i<<" "<<j<<endl;
					return 0;
				}
			}
		}
	}
}

Measured memory_bytes: 3644
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    input! {
    a:usize,
    b:usize,
    c:usize,
    }
    println!("{}",(c/a)*b)
}

Measured memory_bytes: 2096
#include<stdio.h>
int memo [10000],a;
int kugiri(int x);
int kugiri(int x){
    if(x==1)return 2;
    if(memo[x]!=0)return memo[x];
    a=kugiri(x-1)+x;
    memo[x]=a;
    return a;
}
int main(void){
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",kugiri(n));
    }
    return 0;
}

Measured memory_bytes: 908
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = getLine >> readLine >>= print . solve

solve :: [Int] -> Int
solve = calc . sort
    where
        calc (x : y : zs)
            | m == 0 = calc $ x : zs
            | otherwise = calc $ m : x : zs
            where
                (r, m) = y `divMod` x
        calc [x] = x

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine



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

int main(){
    int a,b,c,x,y;

    while(scanf("%d%d%d%d%d",&a,&b,&c,&x,&y)==5){
        int ApB = x*a + y*b;
        int minAB;

        if(x<y){
            minAB = 2*x*c + (y-x)*b;
        }

        else{
            minAB = 2*y*c + (x-y)*a;
        }

        int maxAB = max(x,y)*2*c;
        int ans = min(ApB, min(minAB, maxAB));

        printf("%d\n",ans);
    }

    return 0;
}


Measured memory_bytes: 256
NY = input().split(' ')
N = int(NY[0])
Y = int(NY[1])

sum_Y = 0
break_flag = False
ans = (-1,-1,-1)
for x in range(N+1):
    for y in range(N+1-x):
        sum_Y = 10000*x + 5000*y + 1000*(N-x-y)
        if sum_Y == Y:
            ans = (x,y,N-x-y)
    
    if x == N:
        sum_Y = 10000*x
        if sum_Y == Y:
            ans = (x,y,N-x-y)
print(' '.join(map(str,ans)))

Measured memory_bytes: 3064
k = int(input())
import math
ans = 0
def GCD(a,b,c):
    return math.gcd(math.gcd(a,b),c)
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=GCD(i,j,k)
print(ans)

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

int main() {
  int n;
  cin >>n;
  vector<int> a(n,0);
  int b;
  rep(i,n){
    cin >>b;
    a[b-1]++;
  }
  for(auto au:a){
    cout <<au<<endl;
  }
}


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

#include <unistd.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
 
 
typedef long long ll;
//#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx_ori[4] = { -1,0, 1,0 }, dy_ori[4] = { 0,1,0,-1 };
int dx[4] = {0, 0, 0, 0}, dy[4] = {0, 0, 0, 0};
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
const ll MOD = 1000000007;
//const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

signed main() {
  int h, w;
  cin >> h >> w;
  vll a(h + 1, vl(w + 1, inf)), b(h + 1, vl(w + 1, inf));
  rep (i, h) {
    rep (j, w) {
      cin >> a[i][j];
    }
  }
  rep (i, h) {
    rep (j, w) {
      cin >> b[i][j];
    }
  }

  const int ma = 25601;
  vector<vector<bitset<ma>>> dp(h, vector<bitset<ma>>(w));
  dp[0][0][a[0][0] - b[0][0] + 12800] = true;
  dp[0][0][b[0][0] - a[0][0] + 12800] = true;

  rep (i, h) {
    rep (j, w) {
      rep (k, ma) {
        if (not dp[i][j][k]) continue;
        if (i < h - 1) {
          dp[i + 1][j][k + a[i + 1][j] - b[i + 1][j]] = true;
          dp[i + 1][j][k + b[i + 1][j] - a[i + 1][j]] = true;
        }
        if (j < w - 1) {
          dp[i][j + 1][k + a[i][j + 1] - b[i][j + 1]] = true;
          dp[i][j + 1][k + b[i][j + 1] - a[i][j + 1]] = true;
        }
      }
    }
  }

  int ans = inf;
  rep (k, ma) {
    if (dp[h - 1][w - 1][k]) {
      chmin(ans, abs(k - 12800));
    }
  }
  cout << ans << endl;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

void solve(){
    double W, H, x, y;
    cin >> W >> H >> x >> y;

    cout << setprecision(9) << (W*H) / 2.0 << " ";
    if (W / 2 == x && H / 2 == y) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }


    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <string>
#include<string.h>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fuck(x) cout<<x<<endl
#define mem(a,b) memset(a,b,sizeof a)
#define lowbit(x) (x&-x)
const int MAX=1e5*2+10;
int main()
{
    int a,b,c,d;
    while(cin>>a>>b>>c>>d)
    {
        if(a>c)
        {
            swap(a,c);
            swap(b,d);
        }
        if(b<c)
            cout<<0;
        else if(b>=c && b<=d)
            cout<<b-c<<endl;
        else if(b>d)
            cout<<d-c<<endl;
    }
}


Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

long long a,b,x;

int main()
{
	//fuck
	cin>>a>>b>>x;
	long long ans=(b/x)-(a%x?a/x:a/x-1);
	printf("%lld\n",ans);
}

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

int main()
{
    int n;
    std::cin >> n;
    std::unordered_map<int, int> map;
    for (int i = 0; i < n; ++i)
    {
        int tmp;
        std::cin >> tmp;
        ++map[tmp];
    }

    int count1 = 0, count2 = 0;
    for (const auto &e : map)
    {
        // 3枚以上の場合は2枚ずつ減らせるので
        // 結局のところでカードの枚数は1枚か2枚
        if (e.second % 2 == 1)
        {
            ++count1;
        }
        else
        {
            ++count2;
        }
    }

    if (count2 == 0)
    {
        // 重複がない
        std::cout << count1 << std::endl;
        return 0;
    }

    // 重複しているものからそれぞれ異なる数字を取り出すと
    // 重複していない2枚とそのまま重複している1枚にできる
    if (count2 >= 3)
    {
        const int tmp = (count2 - 1) / 2 * 2;

        count1 += tmp;
        count2 -= tmp;
    }
    // 重複しているのは1種類か2種類
    // 1種類の場合：
    //  重複している2枚と重複していない1枚を取り出す
    //  1枚返ってくるのでcount1の値は変化しない
    // 2種類の場合：
    //  重複しているカードの値をa, a, b, bとする
    //  a, a, bを取り出す
    //  返ってくるのはa
    //  残ったのはa, bでcount1の値は2増える
    if (count2 == 1)
    {
        std::cout << count1;
    }
    else
    {
        std::cout << count1 + 2;
    }
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 7148
import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#    c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
print(math.ceil((e1+e2)/2))




Measured memory_bytes: 8972
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 3);
  (v[0], v[1], v[2])
}

fn main() {
    let (a, b, c) = read_touple::<usize>();

    if (a == b && b == c) || (a != b && b != c && a != c) {
       println!("No");
    } else {
      println!("Yes");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define pri 1000000007
#define pr pair <ll,ll>

using namespace std;

void masterstroke(){
	
ll n;
cin>>n;
vector <pair<string,pair<ll,ll> > > as;
for(ll i=0;i<n;i++){
string a;
cin>>a;
ll b;
cin>>b;
as.PB(MP(a,MP(-b,i+1)));
}
sort(all(as));
for(auto j:as){
	cout<<j.ss.ss<<endl;
}

}
int main() {
    ll t=1;
    //cin>>t;
    for(ll i=0;i<t;i++)masterstroke();
	// your code goes here
	return 0;
}

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

int main() {
    long long N, M;
    cin >> N >> M;

    if (N * 2 <= M) {
        cout << (N * 2 + M) / 4 << endl;
    }
    else {
        cout << M / 2 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    string s;
    cin>>n>>s;
    if(n==0)
        cout<<s<<endl;
    else{
        for(int i=0;i<s.size();i++){
            if(s[i]-64+n<=26){
                s[i] = (char)(s[i]+n);
            }else{
                s[i] = (char)(s[i]+n-26);
            }
        }
        cout<<s<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
N = int(input())
W = tuple(map(int,input().split()))

sum_1 = 0
sum_2 = sum(W)
min_num = 1000
for i in range(N):
    sum_1+=W[i]
    sum_2-=W[i]
    if abs(sum_1-sum_2)<min_num:
        min_num = abs(sum_1-sum_2)
print(min_num)

Measured memory_bytes: 38256
#D
import math
a,b,x = map(float,input().split())
w_theta = math.atan(b / a)
w_p = 0.5 * a * b * math.sin(w_theta) * math.sqrt(a ** 2 + b ** 2)
if x > 0.5*a*a*b:
    theta = math.degrees(math.atan((2. * (((a ** 2) * b) - x)) / (a ** 3)))
else:
    theta = math.degrees(math.atan((a * (b ** 2))/ (2. * x)))
print(theta)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream& operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream& operator<<(ostream &os, vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream& operator<<(ostream &os, set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream& operator<<(ostream &os, unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream& operator<<(ostream &os, multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream& operator<<(ostream &os, unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream& operator<<(ostream &os, pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream& operator<<(ostream &os, map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream& operator<<(ostream &os, unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

lint N, X;
vector<lint> sz(52);
vector<lint> whole(52);

lint cou(lint l, lint x)
{
    if (l == 0 && x == 1) return 1;
    if (x <= 1) return 0;
    x--;
    lint ans = 0;
    if (x >= sz[l - 1])
    {
        ans += whole[l - 1];
        x -= sz[l - 1];
        if (x == 0) return ans;
        ans += 1;
        x--;
    }
    return ans + cou(l - 1, min(x, sz[l - 1]));
}

int main()
{
    cin >> N >> X;

    sz[0] = 1;
    REP(i, N + 1) sz[i + 1] = sz[i] * 2 + 3;
    whole[0] = 1;
    REP(i, N + 1) whole[i + 1] = whole[i] * 2 + 1;
    cout << cou(N, X) << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            int n = sc.nextInt();
            int r = sc.nextInt();

            int[] num =  new int[n];
            int[] temp =  new int[n];

            for(int i = 0; i < n; i++){
                num[i] = n - i;
            }

            if(n == 0 && r == 0) break;

            for(int i = 0; i < r; i++){
                int p = sc.nextInt();
                int c = sc.nextInt();

                for(int j = 0; j < p+c-1; j++){
                    if(j < p-1){
                        temp[j+c] = num[j];
                    }else{
                        temp[j-p+1] = num[j];
                    }
                }
                for(int j = 0; j < p+c-1; j++){
                    num[j] = temp[j];
                }
            }
            System.out.println(num[0]);
            
        }
    }
}


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

using namespace std;

int main() {
	int k;
	cin >> k;
	vector<int> used(k, 0);
	int cur = 0;
	for (int i = 0; ; i++) {
		cur = (cur * 10 + 7) % k;
		if (cur == 0) {
			cout << i + 1 << endl;
			return 0;
		}
		if (used[cur] == 1) {
			cout << -1 << endl;
			return 0;
		}
		used[cur] = 1;
	}
}

Measured memory_bytes: 6676
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    N, K = LI()
    h = []
    [h.append(I()) for i in range(N)]

    h = sorted(h)
    #  print(h)
    h_diff = [h[i+K-1] - h[i] for i in range(N-K+1)]
    print(min(h_diff))

if __name__ == '__main__':
    main()


Measured memory_bytes: 78176
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(){

    string s;
    cin >> s;
    s += "XYZ";
    ll ans = 0;
    for(ll i = 0; i < s.size();){
        if(s[i] == 'X')break;
        if(s[i] == 'C' || (s[i] == 'B' && s[i + 1] != 'C')){
            i++;
            continue;
        }
        vector<ll>vec;
        for(;i < s.size();){
            if(s[i] == 'A'){
                vec.push_back(0);
                i++;
            }
            else if(s[i] == 'B' && s[i + 1] == 'C'){
                vec.push_back(1);
                i+=2;
            }
            else{
                break;
            }
        }
        ll cnt = 0;
        for(ll j = 0; j < vec.size(); j++){
            if(vec[j] == 0)cnt++;
            else ans += cnt;
        }
    }
    

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2680
/*
 * main.c
 *
 *  Created on: 2020/03/28
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;
typedef unsigned long long int ull;

int sort_inc(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int sort_dec(const void* a, const void* b) { return (*(int*)b - *(int*)a);}
int sort_dec_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = -1; }
    else if (da == db) { val = 0; }
    else { val = 1; }
    return val;
}
int sort_inc_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = 1; }
    else if (da == db) { val = 0; }
    else { val = -1; }
    return val;
}
int sort_dic(const void *a, const void *b) {
    char *pa = (char *)a;    char *pb = (char *)b;    int i = 0, val = 0, N = 10;
    for (i = 0; i < N; i++) {
    	char da = pa[i], db = pb[i];
    	if (da == db) continue;
  		if (da > db) val = 1; else val = -1;
        break;
    }
    return val;
}

void yesno(int ans) {
	if (ans == 1) {	printf("Yes\n");
	} else {		printf("No\n");	}
	return;
}

void okng(int ans) {
	if (ans == 1) { printf("OK\n");
	} else { 		printf("NG\n");	}
	return;
}


int contest[27] = {0};
int satisfact[366][27] = {0};
int ans[366] = {0};
int t[366] = {0};
int last[27] = {0};
int last_day(int i)
{
	int ret = last[i];
	return ret;
}
int main()
{
	int D = 0;
	scanf("%d", &D);
	memset(satisfact, 0, sizeof(satisfact));

	int i = 1, d = 1;
	for (i = 1; i <= 26; i++ ) {
		scanf("%d", &contest[i]);
	}
	for (d = 1; d <= D; d++) {
		for (i = 1; i <= 26; i++ ) {
			scanf("%d", &satisfact[d][i]);
		}
	}
	for (d = 1; d <= D; d++ ) {
		scanf("%d", &t[d]);
	}

	// day 1 stisfact = 0
	// contest open .. day d, contest type i statisfact(d,i) increase
	// if contest type not open, test never open last(d,i) = 0.
	for (d = 1; d <= D; d++) {
		ans[d] = satisfact[d][t[d]] + ans[d - 1];
		for (i = 1; i <= 26; i++ ) {
			if (i != t[d]) {
				ans[d] -= contest[i] * (d - last_day(i));
			}
		}
		last[t[d]] = d;
	}
	for (d = 1; d <= D; d++) {
		printf("%d\n", ans[d]);
	}
	return 0;
}


Measured memory_bytes: 1764
#include <bits/stdc++.h>
using namespace std;
const long long INF = 123456789;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for (ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i, r, n) for (ll i = (ll)(n - 1); i >= r; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll>> vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
    cin>>n>>m>>k;
    FOR(i,1,n+1){
        ll l = i;
        ll te=0;
        while(l!=0){
            te+=l%10;
            l/=10;
        }
        if(m<=te&&te<=k){
            ans+=i;
        }
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 256
def ext_euclid(a, b):
    # 互いに素なa,bに対して、方程式ax+by=1の整数解を1つ求める
    x0, y0, r0 = 1, 0, a
    x1, y1, r1 = 0, 1, b
    while r0 != 0:
        x0, y0, r0, x1, y1, r1 = x1 - x0 * (r1 // r0), y1 - y0 * (
            r1 // r0), r1 % r0, x0, y0, r0
    if a * x1 + b * y1 == 1:
        return x1, y1


def gcd(a, b):
    while a:
        a, b = b % a, a
    return b


a, b = map(int, input().split())
g = gcd(a, b)
a, b = a // g, b // g
x, y = ext_euclid(a, b)
if a == b and x > y:
    x, y = y, x
print(x, y)



Measured memory_bytes: 5600
#include <iostream>
#include <set>
using namespace std;
set<int>x;
int main(void){
    int n;
    cin>>n;
    while(n){
        int num;
        cin>>num;
        
        if(x.count(num))x.erase(num);
        else x.insert(num);
 
        n--;
    }
    cout<<x.size()<<endl;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#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 all(x) (x).begin(),(x).end()
ll tmp1,tmp2,tmp3;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}

int main(){
  ll n;
  cin >> n;
  vector<ll> vec(n);
  vector<ll> keta(60,0);
  rep(i,n){
    cin >> vec[i];
  }
  ll ans = 0;
  rep(i,n){
    tmp1 = vec[i];
    ll cou = 0;
    while(tmp1 != 0){
      if(tmp1 & 1){
        keta[cou]++;
      }
      cou++;
      tmp1 = tmp1 >> 1;
    }
  }
  ll piv = 0;
  rep(i,60){
    tmp1 = keta[i];
    tmp2 = (tmp1 * (n - tmp1)) % mod;
    tmp3 = (ll)1 << piv;
    tmp3 %= mod;
    ans += ((tmp3 * tmp2) % mod);
    ans %= mod;
    //cout << ans << endl;
    piv++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <iostream>

void test(int number, int &cnt_5, int &cnt_7){
    if(number == 5) ++cnt_5;
    else if(number == 7) ++cnt_7;
}

int main(int argc, char const *argv[])
{
    int A,B,C;
    std::cin >> A >> B >> C;
    int cnt_5 = 0, cnt_7 = 0;
    test(A, cnt_5, cnt_7);
    test(B, cnt_5, cnt_7);
    test(C, cnt_5, cnt_7);
    if(cnt_5 == 2 && cnt_7 == 1){
        std::cout << "YES\n";
    } else{
        std::cout << "NO\n";
    }
    return 0;
}


Measured memory_bytes: 3600
S = input()
T = input()

is_ok = False
li = []
ans = '{'
for i in range(len(S)-len(T)+1):
    flag = True
    for ind,j in enumerate(T):
        if(S[i+ind]=='?' or S[i+ind]==j):
            pass
        else:
            flag = False
    if(flag):
        is_ok=True
        li.append(i)

if(is_ok):
    for i in li:
        s = S[:i]+T+S[i+len(T):]
        ans = min(ans,s.replace('?','a'))

    print(ans)
else:
    print('UNRESTORABLE')


Measured memory_bytes: 3064