akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL

ll beki(ll x, ll n){
  ll res = 1LL;
  while(n > 0){
    if(n & 1){
      res *= x % MOD;
      res %= MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return res % MOD;
}

int main(){
  string S;
  cin >> S;
  ll N = S.size();
  vll dp1(N+1, 0LL), dp2(N+1, 0LL), dp3(N+1, 0LL);
  ll counter = 0LL;
  for(int i = 1; i <= N; i++){
    char c = S.at(i-1);
    if(c == '?') counter++;

    if(c == '?') dp1.at(i) = dp1.at(i-1) * 3LL % MOD + 1LL * beki(3LL, counter-1LL) % MOD;
    else if(c == 'A') dp1.at(i) = (dp1.at(i-1) + 1LL * beki(3LL, counter) % MOD) % MOD;
    else dp1.at(i) = dp1.at(i-1);
    dp1.at(i) %= MOD;

    if(c == '?') dp2.at(i) = (dp2.at(i-1) * 3LL % MOD + dp1.at(i-1)) % MOD;
    else if(c == 'B') dp2.at(i) = dp2.at(i-1) + dp1.at(i-1);
    else dp2.at(i) = dp2.at(i-1);
    dp2.at(i) %= MOD;

    if(c == '?') dp3.at(i) = (dp3.at(i-1) * 3LL % MOD + dp2.at(i-1)) % MOD;
    else if(c == 'C') dp3.at(i) = dp3.at(i-1) + dp2.at(i-1);
    else dp3.at(i) = dp3.at(i-1);
    dp3.at(i) %= MOD;
  }
  cout << dp3.at(N) << endl;
}


Measured memory_bytes: 2816
// AtCoder Beginner Contest - Problem C: Pyramid (https://beta.atcoder.jp/contests/abc112/tasks/abc112_c)
#include <bits/stdc++.h>

#define REP(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define REPN(i, N) for (int (i) = 0; (i) < N; (i)++)

using namespace std;

const int MAX { 110 };

int xs[MAX], ys[MAX], hs[MAX];

void solve(int N)
{
    int ans = -1, cx = -1, cy = -1;

    REP(x, 0, 100)
    {
        REP(y, 0, 100)
        {
            int H = 0;

            REPN(i, N)
            {
                if (not hs[i])
                    continue;

                H = hs[i] + abs(x - xs[i]) + abs(y - ys[i]);
            }

            ans = H;

            REPN(i, N)
            {
                auto h = max(H - abs(x - xs[i]) - abs(y - ys[i]), 0);

                if (hs[i] != h)
                {
                    ans = -1;
                    break;
                }
            }

            if (ans != -1)
            {
                cx = x;
                cy = y;
                break;
            }
        }

        if (ans != -1)
            break;
    }

    cout << cx << " " << cy << " " << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    REPN(i, N)
        cin >> xs[i] >> ys[i] >> hs[i];

    solve(N);

    return 0;
}


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

int main() {

int N; cin>>N;
  vector<int> A(N),B(N),C(N);
  vector<vector<int>> dp(3,vector<int>(N+1,0));
  for(int i=0;i<N;i++){
    cin>>A[i]>>B[i]>>C[i];}
  for(int i=0;i<N;i++){
   dp[0][i+1]=max(dp[1][i]+B[i],dp[2][i]+C[i]); 
   dp[1][i+1]=max(dp[0][i]+A[i],dp[2][i]+C[i]);
   dp[2][i+1]=max(dp[1][i]+B[i],dp[0][i]+A[i]);
  }
  cout<<max({dp[0][N],dp[1][N],dp[2][N]})<<endl;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define lli long long int 
#define pb push_back
using namespace std;

const int INF= 1e9 +5;
typedef std::vector<int> vi;
typedef pair<int,int> ii;


int main() {

	//freopen("input.txt", "r", stdin); 
  	//freopen("output.txt", "w", stdout); 


  	int a,b;
  	cin>>a>>b;
  	lli sum=a;

  	if(b==1){printf("0\n");
  	return 0;}

  	int n=1;
  	while(sum<=b)
  	{	if(sum==b)break;
  		sum+=a;
  		sum--;
  		n++;
  	}

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

	
	return 0;
}

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

int main(){
  ll n,m,i,a,b,x,y;
  queue<ll> w;
  cin >> n >> m;
  ll ans[n+1]={};
  ans[0]=1;
  vector<vector<ll>> v(n+1);
  for(i=0;i<m;i++){
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
    if(min(a,b)==1){
      w.push(max(a,b));
      ans[max(a,b)]=1;
    }
  }
  ans[1]=1;
  while(w.size()!=0){
    x=w.front();
    w.pop();
    for(i=0;i<v[x].size();i++){
      y=v[x][i];
      if(ans[y]==0){
        ans[y]=x;
        w.push(y);
      }
    }
  }
  x=1;
  for(i=2;i<=n;i++){
    x=min(x,ans[i]);
  }
  if(x==0)cout << "No";
  else{
    cout << "Yes" << endl;
  	for(i=2;i<=n;i++){
    	cout << ans[i] << endl;
  	}
  }
}

Measured memory_bytes: 12888
#!/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
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    a = s.count("-")
    b = s.count("+")
    print(b-a)
    return

#B
def B():
    n = S()
    num = sum(map(int, n))
    n = int("".join(n))
    print(["Yes", "No"][n % num > 0])
    return

#C
def C():
    return

#D
def D():
    return


#Solve
if __name__ == '__main__':
    B()

Measured memory_bytes: 38512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
 
#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}
 
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
 
using namespace std;
 
typedef pair<int,int> pii;
 
int main(){
 
  string s;
  cin >> s;
 
  int len = s.length();
  REP(i,len - 1){
    if(s[i] == 'S' && s[i + 1] == 'T'){
      s.erase(i, 2);
      len -= 2;
      i -= 2;
    }
  }
 
  cout << len << "\n";
  return 0;
}
 

Measured memory_bytes: 640
from itertools import combinations
import bisect
n = int(input())
l = list(map(int, input().split()))

l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        x = l[i] - l[j] + 1
        idx = bisect.bisect_left(l, x)
        if j > idx:
           cnt += j - idx
print(cnt)

Measured memory_bytes: 45388
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {

	private class Card {
		int id;
		int number;
		String letter;

		public Card(int number, String letter) {
			this.number = number;
			this.letter = letter;
		}

		public void setId(int id) {
			this.id = id;
		}

		public String toString() {
			return letter + " " + number;
		}
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.solv();
	}

	private void solv() {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();

		// ???????????????????????¨
		Card[] cards = new Card[n];
		for (int i = 0; i < n; i++) {
			String letter = input.next();
			int number = input.nextInt();
			Card card = new Card(number, letter);
			card.setId(i);
			cards[i] = card;
		}
		quickSort(cards, 0, n);

		// ????????????????????????????????????
		boolean isStable = true;
		int num = cards[0].number;
		for (int i = 0; i < cards.length - 1; i++) {
			if (num == cards[i].number && num == cards[i + 1].number) {
				if (cards[i].id > cards[i + 1].id) {
					isStable = false;
					break;
				}
			}else{
				num = cards[i + 1].number;
			}
		}

		if (isStable) {
			System.out.println("Stable");
		} else {
			System.out.println("Not stable");
		}

		// ???????????????????????????????????????
		for (Card card : cards) {
			System.out.println(card);
		}

		// System.out.println(Arrays.toString(cards));
		// System.out.println(cards2);

	}

	private void quickSort(Card[] cards, int p, int r) {
		if (p < r) {
			int q = partition(cards, p, r);
			quickSort(cards, p, q - 1);
			quickSort(cards, q , r);
		} else {
			return;
		}
	}

	private int partition(Card[] cards, int p, int r) {
		// p(???????????£?????§???)????????????????????????
		int partition = p;
		for (int i = p; i < r; i++) {
			if (cards[i].number <= cards[r - 1].number) {
				// swap
				Card temp = cards[i];
				cards[i] = cards[partition];
				cards[partition] = temp;
				// ???????????????
				partition++;
			}
		}
		return partition;
	}

	private void print(Object[] xs) {
		StringBuilder sb = new StringBuilder();
		for (Object x : xs)
			sb.append(x.toString()).append(' ');
		System.out.println(sb.toString().trim());
	}

	private void print(int[] xs) {
		StringBuilder sb = new StringBuilder();
		for (int x : xs) {
			sb.append(x).append(' ');
		}
		System.out.println(sb.toString().trim());
	}

	private static class Scanner {
		BufferedReader r;
		StreamTokenizer st;

		public Scanner(InputStream in) {
			r = new BufferedReader(new InputStreamReader(in));
			st = new StreamTokenizer(r);
		}

		public String next() {
			nextToken();
			return st.sval;
		}

		public Integer nextInt() {
			nextToken();
			return (int) st.nval;
		}

		private int nextToken() {
			int token = st.TT_EOF;
			try {
				token = st.nextToken();
			} catch (IOException e) {
			}
			return token;
		}
	}
}

Measured memory_bytes: 61896
n,m,k,l = map(int,input().split())
lst = [n,m,k,l]

if 1 in lst:
  if 9 in lst:
    if 7 in lst:
      if 4 in lst:
      	print ("YES")
      else:
        print("NO")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
template <class Q>
void clearQueue(Q & q) {
    q = Q();
}
void solve(){
	int dp[100005];
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int& x:a){
        cin>>x;
    }
    dp[0]=0;
    for(int i=1;i<=k;i++){
        dp[i]=0;
        for(int j=0;j<n;j++){
            if(i-a[j]>=0&&dp[i-a[j]]==0) dp[i]=1;
        }
    }
    if(dp[k]==1) cout<<"First";
    else cout<<"Second";
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL); 
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}


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

int main(void){
    int a,b,c,x;
    scanf("%d %d %d %d", &a,&b,&c,&x);


/*コインが区別されないのでビット式全探査はダメ
    int count=0;
    int coinnum=a+b+c;
    int yen=0;


    for(int i=0;i<(1<<coinnum);i++){
        bitset<50> bit(i);
        for(int j=0;j<coinnum;j++){
            if(bit.test(j)){
                if(j<a) yen += 500;
                else if(a<=j && j<a+b) yen += 100;
                else yen += 50;
            }
        }

        if(yen==x) count++;
        yen=0;
    }

    cout << count << endl;
*/
    int count=0;

    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                int yen = 500*i+100*j+50*k;
                if(yen==x) count++;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.*;
public class Main {
    public  static  void main(String args[]){
        Scanner sc=new Scanner(System.in);

        BigInteger b=sc.nextBigInteger();
        BigInteger res=(b.subtract(new BigInteger("1")).multiply(b)).divide(new BigInteger("2"));
        System.out.println(res);
    }
}


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


int main() {
	int n;
	cin>>n;
	int dp[n][3];
	for(int i=0;i<n;i++)
	    for(int j=0;j<3;j++)
	    cin>>dp[i][j];
	    for(int i=1;i<n;i++)
	    {
	        for(int j=0;j<3;j++)
	        {
	            if(j==0)
	                dp[i][j]=dp[i][j]+max(dp[i-1][1],dp[i-1][2]);
	            else if(j==1)
	                dp[i][j]=dp[i][j]+max(dp[i-1][0],dp[i-1][2]);
	            else
	                dp[i][j]=dp[i][j]+max(dp[i-1][0],dp[i-1][1]);
	        }
       }
	  int res=INT_MIN;
	  for(int j=0;j<3;j++)
	    res=max(res,dp[n-1][j]);
	cout<<res;
}

Measured memory_bytes: 4784
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

int main() {
	int K, T;
	cin >> K >> T;
	vector<int> a;
	FOR (i, T) {
		int b;
		cin >> b;
		a.pb(b);
	}
	sort(all(a));
	int val = a[a.sz - 1];
	int m = (K + 1) / 2;
	if (val <= m)
		cout << 0 << endl;
	else {
		int ret = 2 * (val - m);
		if (K % 2 == 0)
			ret--;
		cout << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;

const ll M = 2000;

int main()
{
    ll x;
    cin >> x;
    ll p[4005];
    for(ll i = -2000; i <= 2000; i++){
        p[i + M] = i * i * i * i * i;
    }
    for(int i = -2000; i <= 2000; i++){
        for(int j = -2000; j <= 2000; j++){
            if(p[i + M] - p[j + M] == x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 3668
a,b,c,k = list(map(int,input().split()))

if k%2 == 0:
    if abs(a-b)<=10**18:
        print(a-b)
    else:
        print('Unfair')
else:
    if abs(c-b)<= 10**18:
        print(b-a)
    else:
        print('Unfair')

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n, a, b;
  cin >> n >> a >> b;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int t = i;
    int s = 0;
    while (t) {
      s += t % 10;
      t /= 10;
    }
    if (a <= s && s <= b) ans += i;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 3648
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define ll long long int
#define lim 100010
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define ABS(x) ((x)>0?(x):-(x))

int main(void){
	int r,g,b,n;
	scanf("%d%d%d%d",&r,&g,&b,&n);
	int ans=0;
	for(int i=0;i<(n/r+1);i++){
		for(int j=0;j<(n/g+1);j++){
			if((n-i*r-j*g)%b==0 && (n-i*r-j*g)/b>=0){
				ans++;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
typedef long long ll;
typedef unsigned long long ull;
int cost[128][128];
int mincost[128];
bool used[128];
int V,E;
void init(){
	rep(i,V)rep(j,V)cost[i][j] = INF;
	fill(mincost,mincost+V,INF);
	fill(used,used+V,false);
}
int prim(){
	mincost[0] = 0;
	int res = 0;
	while(true){
		int v = -1;
		rep(u,V)if(!used[u] && (v == -1 || mincost[u] < mincost[v]))v = u;
		if(v == -1)break;
		used[v] = true;
		res += mincost[v];
		rep(u,V)mincost[u] = min(mincost[u],cost[v][u]);
	}
	return res;
}
int main(){
	int n,m;
	while(scanf("%d",&n),n){
		scanf("%d",&m);
		V = n;
		init();
		rep(i,m){
			int from,to,pay;
			scanf("%d,%d,%d",&from,&to,&pay);
			cost[from][to] = pay-100;
			cost[to][from] = pay-100;
		}
		int ans = prim();
		printf("%d\n",ans/100);
	}
	return 0;
}

Measured memory_bytes: 1236
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
for i in 0..n-1
  a[i] -= 1+i
end
ans = 0
a.sort!
for i in 0..n/2-1
  ans += a[n-1-i]-a[i]
end
puts ans

Measured memory_bytes: 19556
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<limits.h>
using namespace std;

int n;
int d[103][103];
void wf();

int main(){ 
  while(cin >> n)wf();
}




void wf(){
  int i1,m,J2;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i == j)d[i][j]=0;
      d[i][j]=1000000000;//INT_MAXテつづつセテつづδつバテつグテつづδゥ
    }
  }

  for(int i=0;i<n;i++){
    cin >> i1 >> m;
    for(int j=0;j<m;j++){
      cin >> J2;
      d[i1-1][J2-1]=1;
    }
  }

  for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
  int oh;

  cin >> oh;
  int st,ed,ttl;
  for(int i=0;i<oh;i++){
    cin >> st >> ed >> ttl;
    if(d[st-1][ed-1]+1 > ttl)cout << "NA" << endl;
    else cout << d[st-1][ed-1]+1 << endl;

  }/*
 for(int i=0;i<n;i++){
     for(int j=0;j<n;j++)cout << d[i][j] << " " ;
     cout << endl;
   }
   */

}

 

Measured memory_bytes: 0
#include <stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
  char suit;
  int value;
};

struct Card L[MAX/2+2], R[MAX/2+2];

void merge(struct Card A[], int n, int left, int mid, int right) {
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i=0;i<n1;i++) L[i] = A[left + i];
  for(int i=0;i<n2;i++) R[i] = A[mid  + i];
  L[n1].value = R[n2].value = SENTINEL;
  i = j = 0;
  for(k=left; k<right; k++) {
    if(L[i].value <= R[j].value) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(struct Card A[], int n, int left, int right) {
  if(left+1 < right) {
    int mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int partition(struct Card A[], int n, int p, int r) {
  int i, j;
  struct Card t, x;
  x = A[r];
  i = p-1;
  for(j=p; j<r; j++) {
    if(A[j].value <= x.value) {
      i++;
      t=A[i]; A[i]=A[j]; A[j]=t;
    }
  }
  t=A[i+1]; A[i+1]=A[r]; A[r]=t;
  return i+1;
}

void quickSort(struct Card A[], int n, int p, int r) {
  int q;
  if(p<r) {
    q = partition(A,n,p,r);
    quickSort(A,n,p,q-1);
    quickSort(A,n,q+1,r);
  }
}

int main() {
  int n, i, v;
  struct Card A[MAX], B[MAX];
  char S[10];
  int stable = 1;

  scanf("%d", &n);

  for(i=0;i<n;i++) {
    scanf("%s %d",S,&v);
    A[i].suit =  B[i].suit  = S[0];
    A[i].value = B[i].value = v;
  }

  mergeSort(A,n,0,n);
  quickSort(B,n,0,n-1);

  for(i=0;i<n;i++) {
    // マージソートとクイックソートの結果を比べる
    if(A[i].suit != B[i].suit) stable = 0;
  }

  if(stable==1) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0;i<n;i++) {
    printf("%c %d\n",B[i].suit,B[i].value);
  }

  return 0;
}

Measured memory_bytes: 4072
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
d=lambda x1,y1,x2,y2:((x1-x2)**2+(y1-y2)**2)**0.5
from itertools import permutations
x=0
f=1
for i in range(n):f*=i+1
for i in permutations(a):
  for j in range(n-1):
    x+=d(i[j][0],i[j][1],i[j+1][0],i[j+1][1])
print(x/f)

Measured memory_bytes: 3188
import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main
{
    public static final int MOD = 1_000_000_007;
    public static void main(String[] args) throws IOException {
//        BufferedReader in = new BufferedReader(new FileReader("pathsonagrid.txt"));
        Scanner in = new Scanner(System.in);
 
//        StringTokenizer line = new StringTokenizer(in.readLine());
        StringTokenizer line = new StringTokenizer(in.nextLine());
 
        int n = Integer.parseInt(line.nextToken());
        int m = Integer.parseInt(line.nextToken());
        
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++)
//            grid[i] = in.readLine().trim().toCharArray();
            grid[i] = in.nextLine().trim().toCharArray();
        
        int[][] paths = new int[n][m];
        paths[0][0] = 1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (grid[r][c] == '#')
                    continue;
                try { //look above
                    paths[r][c] += paths[r-1][c] % MOD;
                } catch (Exception e) {}
                try { //look left
                    paths[r][c] += paths[r][c-1] % MOD;
                } catch (Exception e) {}
            }
        }
        
        System.out.println(paths[n-1][m-1] % MOD);
    }
}

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

int main() {
  string s;
  cin >> s;
  int a[4];
  for (int i = 0; i < 4; i++) {
    a[i] = s[i] - '0';
  }
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int sum = a[0];
        if (i) sum += a[1];
        else sum -= a[1];
        if (j) sum += a[2];
        else sum -= a[2];
        if (k) sum += a[3];
        else sum -= a[3];
        if (sum == 7) {
          cout << a[0];
          cout << ((i) ? '+' : '-');
          cout << a[1];
          cout << ((j) ? '+' : '-');
          cout << a[2];
          cout << ((k) ? '+' : '-');
          cout << a[3] << "=7";
          cout << endl;
          return 0;
        }
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll N, K; cin >> N >> K;

	ll x = N / K;
	ll res = x * x * x;
	if (K % 2LL == 0LL){
		ll y = (N - K/2LL + K)/K;
		res += y * y * y;
	} // end if

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

enum { MAX_N = 123456 };

bool s[(MAX_N*2)+2];

int main(){
  int n;
 
  while(1){
    for(int i=0;i<=MAX_N;i++)
      s[i]=false;
  
    s[0]=true;
    s[1]=true;
  
    scanf("%d",&n);
    if(n==0)break;
    int cnt=0;
    for(int i=2;i<=2*n;i++){
      int k=2;
      if(s[i])continue;
      if(i>n && i<=2*n)cnt++;
      while(i*k<=2*n){
        s[i*k]=true;
        k++;
      }
    }
    printf("%d\n",cnt);
  }
  return 0;
}

Measured memory_bytes: 1000
#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define mor > muu & operator << (
#define R22(r) sim > typename \
  enable_if<1 r sizeof dud<c>(0), muu&>::type operator<<(c g) {
sim > struct rge { c b, e; };
sim > rge<c> range(c h, c n) { return {h, n}; }
sim > auto dud(c* r) -> decltype(cerr << *r);
sim > char dud(...);
struct muu {
#ifdef LOCAL
stringstream a;
~muu() { cerr << a.str() << endl; }
R22(<) a << boolalpha << g; ris; }
R22(==) ris << range(begin(g), end(g)); }
sim, class b mor pair < b, c > r) { ris << "(" << r.first << ", " << r.second << ")"; }
sim mor rge<c> u) {
  a << "[";
  for (c i = u.b; i != u.e; ++i)
    *this << ", " + 2 * (i == u.b) << *i;
  ris << "]";
}
#else
sim mor const c&) { ris; }
#endif
muu & operator()() { ris; }
};
#define imie(r...) "[" #r ": " << (r) << "] "
#define imask(r...) "[" #r ": " << bitset<8 * sizeof(r)>(r) << "] "
#define arr(a, i) "[" #a imie(i) ": " << a[i] << "] "
#define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] "
#define debug (muu() << __FUNCTION__ << "#" << __LINE__ << ": ")

const int N = 2e5 + 7;
const int mod = 1e9 + 7;

int sil[N];
int silr[N];

int potmod(long long x, int m) {
    long long res = 1;
    while (m > 0) {
        if (m & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        m /= 2;
    }
    return res;
}

int newton(int n, int k) {
    return 1ll * sil[n] * silr[k] % mod * silr[n - k] % mod;
}

int n, m, k;
vector <pair <int, int>> Z;
const int M = 3007;

int dp[M];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    Z.resize(k);
    for (int i = 0; i < k; ++i) {
        scanf("%d %d", &Z[i].first, &Z[i].second);
    }
    
    sil[0] = silr[0] = 1;
    int nn = n + m;
    for (int i = 1; i <= nn; ++i) {
        sil[i] = 1ll * i * sil[i - 1] % mod;
    }
    silr[nn] = potmod(sil[nn], mod - 2);
    for (int i = nn - 1; i >= 0; --i) {
        silr[i] = 1ll * (i + 1) * silr[i + 1] % mod;
    }
    
    Z.push_back({n, m});
    
    sort(Z.begin(), Z.end());
    
    for (int i = 0; i <= k; ++i) {
        long long pom = newton(Z[i].first + Z[i].second - 2, Z[i].first - 1);
        for (int j = 0; j < i; ++j) {
            if (Z[j].first <= Z[i].first && Z[j].second <= Z[i].second) {
                pom -= 1ll * dp[j] * newton(Z[i].first + Z[i].second - Z[j].first - Z[j].second, Z[i].first - Z[j].first) % mod;
            }
        }
        
        pom = (pom % mod + mod) % mod;
        dp[i] = pom;
        
        debug << imie(Z[i]) << imie(dp[i]);
    }
    
    debug << Z[k];
    printf("%d\n", dp[k]);
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>
#include <string.h>

int main(void)
{
char st1[300], st2[200];
char st3[ ] = {"END_OF_TEXT"};

int c = 0;
int i = 0;

scanf("%s", st2);

while(1){

scanf("%s", st1);

if(strcmp(st1, st3) == 0)
 break;

for(i = 0; st1[i] != '\0'; i++){
 if(st1[i] >= 'A' && st1[i] <= 'Z')
  st1[i] += 32;

}

 if(strcmp(st1, st2) == 0)
  c++;

 i = 0;
}

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

return 0;

}



Measured memory_bytes: 2044
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void input() {

    }

    bool solve() {
        input();
        int N, A, B, C, X;
        cin >> N >> A >> B >> C >> X;
        if (N == 0) return false;
        vector<int> Y(N);
        for (int i = 0; i < N; ++i) {
            cin >> Y[i];
        }

        int cnt = 0;
        int lim = 10000;

        for (int i = 0; i < N && cnt <= lim; ++i) {
            bool force = i > 0;
            while ( (Y[i] != X && cnt <= lim) || force) {
                cnt++;
                X = (X * A + B) % C;
                force = false;
            }
        }
        if (cnt > lim) cout << -1 << endl;
        else cout << cnt << endl;
        return true;
    }

};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);


    while (Solve().solve()) {};


    return 0;
}



Measured memory_bytes: 3148
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;


/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back


/*---  Type ---*/
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;


/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// 4-direction
int dy4[] = {0,  1, -1,  0};
int dx4[] = {1,  0,  0, -1};

// 8-direction
int dy8[] = {0,  1,  1,  1,  0, -1, -1, -1};
int dx8[] = {1,  1,  0, -1, -1, -1,  0,  1};

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

int main() {
  vector< pair<int, int> > c;
  int n;
  vector<int> a;
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];

  sort(a.begin(), a.end());
  vector<int>b;
  int _max = a[n-1];

  int _min = a[0];
  int p = 1;
  while(p < n-1 && a[p] < 0) {
    b.pb(a[p]);
    p++;
  }
  for(int i = p; i < n-1; i++) {
    c.pb(mp(_min, a[i]));
    _min -= a[i];
  }
  b.pb(_min);

  rep(i, b.size()) {
    c.pb(mp(_max, b[i]));
    _max -= b[i];
  }

  // cout << "---------------" << endl;
  // rep(i, b.size()) {
  //   cout << b[i] << endl;
  // }
  // cout << "---------------" << endl;
  // cout << "-----------" << endl;
  // rep(i, c.size()) {
  //   cout << c[i].first << ", " << c[i].second << endl;
  // }

  cout << _max << endl;
  rep(i, c.size()) {
    cout << c[i].first << " " << c[i].second << endl;
  }

  return 0;
}

Measured memory_bytes: 3572
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 31;
// clang-format on

ll N;

int main(void)
{
  cin >> N;

  int s = 0;
  int n = N;
  while (n > 0) {
    s += n % 10;
    n /= 10;
  }
  cout << (N % s == 0 ? "Yes" : "No") << endl;
  return 0;
}


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

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

    int a[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> a[i][j];
        }
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (a[j][k] == b) {
                    a[j][k] = -1;
                }
            }
        }
    }
    for (int i = 0; i < 3; i++) {
        bool ok = true;
        for (int j = 0; j < 3; j++) {
            if (a[i][j] != -1) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    for (int i = 0; i < 3; i++) {
        bool ok = true;
        for (int j = 0; j < 3; j++) {
            if (a[j][i] != -1) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    bool ok = true;
    for (int i = 0; i < 3; i++) {
        if (a[i][i] != -1) {
            ok = false;
        }
    }
    if (ok) {
        cout << "Yes" << endl;
        return 0;
    }
    ok = true;
    for (int i = 0; i < 3; i++) {
        if (a[2 - i][i] != -1) {
            ok = false;
        }
    }
    if (ok) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
    int i,j,N,max;
    while(~scanf("%d",&N))
    {
        max=1;
        if(N==1) printf("%d\n",max);
        else
        {
            for(i=1;; i++)
            {
                j=pow(2,(double)i);
                if(N>=j) max=j;
                else break;
            }
            printf("%d\n",max);

        }
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
vector <int> dp;
int solve(vector <int> & v, int index, int k){
	if(index>= (v.size()-1)){
		return 0;
	}
	if(dp[index]!=-1) return dp[index];
	int q = INT_MAX;
	for(int i=index+1; i<=index+k && i<v.size() ;i++){
		q = min(q, abs(v[i]-v[index])+solve(v, i , k));
	}
	dp[index] = q;
	return q;
}
int main(){
	int n;
  	cin>>n;
  	int k;
  	cin>>k;
  	vector <int> v(n);
    for(int i=0; i<n;i++){
    	dp.push_back(-1);
    	cin>>v[i];
	}
	cout<<solve(v, 0, k);
}

Measured memory_bytes: 8952
using System;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            int[] d = new int[100];
            for (int i = 0; i < N; i++)
            {
                d[i] = int.Parse(Console.ReadLine());
            }

            Console.WriteLine(d.Where(n => ((1 <= n) && (n <= 100))).Distinct().ToArray().Length);
        }
    }
}



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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  int N, K, R, S, P;
  std::string T;
  std::cin >> N >> K >> R >> S >> P >> T;

  std::map<char, int> score;
  score['s'] = R;
  score['p'] = S;
  score['r'] = P;

  ll ans = 0;
  std::vector<char> hist(N);
  rep(i, K) {
    ans += score[T[i]];
    hist[i] = T[i];
  }

  for(int i = K; i < N; ++i) {
    if(hist[i - K] != T[i]) {
      ans += score[T[i]];
      hist[i] = T[i];
    } else {
      hist[i] = '_';
    }
  }

  std::cout << ans << '\n';

}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int n,k,x,y;

int main(){
  double ans=0.0;
  cin >> n;
  vector<double> a(n);
  REP(i,n){
    cin>>a[i];
    ans+=1.0/a[i];
  }

  cout<<setprecision(10)<<(1.0/ans)<<endl;
  
  
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


ll calc_sum(int n, ll x, ll k, vector<ll> &numbers) {
    ll s = 0, t = 0;
    for (ll a : numbers) {
        if (a > 0) {
            int floor = -1, ceil = n;
            while (floor + 1 < ceil) {
                int mid = (floor + ceil) / 2;
                ll m = numbers[mid];
                if (a * m <= x) floor = mid;
                else ceil = mid;
            }
            s += ceil;
        } else if (a < 0) {
            int floor = -1, ceil = n;
            while (floor + 1 < ceil) {
                int mid = (floor + ceil) / 2;
                ll m = numbers[mid];
                if (a * m <= x) ceil = mid;
                else floor = mid;
            }
            s += n - ceil;
        } else if (x >= 0) {
            s += n;
        }
        if (a * a <= x) t++;
    }
    return (s - t) / 2;
}

int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> numbers(n);
    rep(i, n) cin >> numbers[i];
    sort(numbers.begin(), numbers.end());

    ll floor = -INF, ceil = INF;

    while (floor + 1 < ceil) {
        ll mid = (floor + ceil) / 2;
        ll sum = calc_sum(n, mid, k, numbers);
        if (sum >= k) ceil = mid;
        else floor = mid;
    }

    cout << ceil << endl;

}


Measured memory_bytes: 1792
import math

n = int(input())
aL = list(map(int, input().split(" ")))
bL = list(map(int, input().split(" ")))

aSum = sum(aL)

for i in range(n):
    dmg1 = min(aL[i], bL[i])
    aL[i] -= dmg1
    bL[i] -= dmg1

    dmg2 = min(aL[i + 1], bL[i])
    aL[i + 1] -= dmg2
    bL[i] -= dmg2

print(aSum - sum(aL))


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

bool checkp(int m) {
	if (m == 2) return true;
	if (m <= 1 || m % 2 == 0) return false;
	for (int i = 3; i <= sqrt(m); i += 2) {
		if (m % i == 0) return false;
	}
	return true;
}

int main() {
	int n, m, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m;
		if (checkp(m)) cnt++;
	}

	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define int long long
#define vin vector<int>
#define vcn vector<char>
#define ver pair<int,int>
#define pb push_back
#define ld long double
#define x first
#define y second
#define blush fflush(stdout);fflush(stdin);
#define $(a) (int)a.size()
#define scanf ;
#define printf ;
using namespace std;
void i_love_misaka_mikoto();
int32_t main(){
    #ifdef RNS
        freopen("input.txt","r",stdin);
        #ifndef DBG
            freopen("output.txt","w",stdout);
        #endif
    #else
        ios_base::sync_with_stdio(false);
    #endif
    i_love_misaka_mikoto();
    #ifdef RNS
        cout<<'\n'<<(ld)clock()/CLOCKS_PER_SEC<<'\n';
    #endif
    return 0;
}

void i_love_misaka_mikoto(){
    int n;
    cin>>n;
    vin in(n), sp(n);
    for(int i=0;i<n;i++)
        cin>>in[i];
    sp[0]=0;
    sp[1]=abs(in[0]-in[1]);
    for(int i=2;i<n;i++)
        sp[i]=min(abs(in[i]-in[i-1])+sp[i-1],abs(in[i]-in[i-2])+sp[i-2]);
    cout<<sp[n-1];
}

Measured memory_bytes: 1792
// D - Sum of Large Numbers
#include <bits/stdc++.h>
using namespace std;

int main(){
	long long N, K, MOD = 1'000'000'007;
	cin>>N>>K; ++N,--K;
	cout<< (N*(N-1)*(N+1)/6 + N + K*(K+1)*(2*K+1 - 3*N)/6 - K + MOD) % MOD <<endl;
}

Measured memory_bytes: 3648
n = int(input())
a = list(map(int, input().split()))

# 隣り合う二枚ずつひっくり返すことを繰り返す
# 負の数を数えて、偶奇判定
cnt = 0
for i in range(n):
    if a[i] < 0:
        cnt += 1
        a[i] = -a[i]
# absa = list(map(abs, a))
min = min(a)
# print(cnt, a, min)
if cnt % 2 == 0:
    print(sum(a))
else:
    print(sum(a)-2*min)


Measured memory_bytes: 14412
#include<bits/stdc++.h>
#define maxn 500005
#define kcz 1000000007
#define int long long
using namespace std;
inline int read()
{
	char x = getchar();
	int lin = 0, f = 1;
	while(x < '0' || x > '9')
	{
		if(x == '-') f = -1;
		x = getchar();
	}
    while(x >= '0' && x <= '9')
	{
		lin = lin * 10 + x - '0';
		x = getchar();
	}
	return lin * f;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
int n,f[4002][4002],a[maxn],b[maxn],fac[maxn],ni[maxn],ans;
int ksm(int a,int b)
{
	int ans = 1;
	while(b)
	{
		if(b & 1) ans = ans * a % kcz;
		a = a * a % kcz;
		b >>= 1;
	}
	return ans;
}
int get_c(int n,int m)
{
	if(n >= 0 && m >= 0 && n >= m) return fac[n] * ni[m] % kcz * ni[n - m] % kcz;
	return 0;
}
void pre()
{
	fac[0] = 1; ni[0] = 1;
	for(int i = 1; i <= 8001; i++)
	{
		fac[i] = fac[i - 1] * i % kcz;
		ni[i] = ksm(fac[i],kcz - 2);
	}
}
main(){
	n = read();
	pre();
	for(int i = 1; i <= n; i++)
	{
		a[i] = read(); b[i] = read();
		++f[2001 - a[i]][2001 - b[i]];
	}
	for(int i = 1; i <= 4001; i++)
		for(int j = 1; j <= 4001; j++)
			f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j - 1]) % kcz;
	for(int i = 1; i <= n; i++)
	{
		ans = (ans + f[2001 + a[i]][2001 + b[i]]) % kcz;
		ans = (ans - get_c((a[i] << 1) + (b[i] << 1),a[i] << 1)) % kcz;
	}
	cout << (ans % kcz + kcz) * ksm(2,kcz - 2) % kcz;
}

Measured memory_bytes: 136960
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
#include <cassert>
#include <unordered_map>
#include <chrono>
#include <random>
#include <ctime>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ld PI = 3.14159265358979323846;
const ll MOD = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	srand(time(0));
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, m, k;
	cin >> n >> m >> k;
	vector<ll> a(n), b(m);
	for (int i = 0; i < n; i++){
		cin >> a[i];
		if (i)a[i] += a[i - 1];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		if (i)b[i] += b[i - 1];
	}
	ll l = 0, r = n + m + 1;
	while (r - l - 1 > 0) {
		ll mid = (l + r) / 2;
		ll su = 0, best = INT64_MAX;
		for (int i = 0; i <= mid; i++) {
			int f = i, s = mid - i;
			su = 0;
			if (f <= a.size() && s <= b.size()) {
				if (f)su += a[f - 1];
				if (s)su += b[s - 1];
			}
			if(su)best = min(su, best);
		}
		//cout << mid << " " << best << "\n";
		if (best <= k) {
			l = mid;
		}
		else {
			r = mid;
		}
	}
	cout << l;
}

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

#define ll long long
const long long int MOD=1e9+7;
const long long int MAXN=50;

struct matrix{

	ll mat[MAXN][MAXN];

	matrix(int idd = 0){
		for(int i = 0;i<MAXN;i++){
			for(int j = 0;j<MAXN;j++){
				mat[i][j] = (idd) ? (i == j) : (0);
			}
		}
	}

	matrix operator*(const matrix& other)const{
		matrix ans;
		for(int i = 0;i<MAXN;i++){
			for(int j = 0;j<MAXN;j++){
				for(int k = 0;k<MAXN;k++){
					ans.mat[i][j] += mat[i][k]*other.mat[k][j];
					if(ans.mat[i][j] > MOD) ans.mat[i][j] %= MOD;
				}
			}
		}
		return ans;
	}

};


matrix fast_exponentiation(matrix m, long long int power)
{
    
    matrix result(1);

    while(power) {
        if(power & 1)
            result = (result * m) ;
        m = (m * m) ;
        power >>= 1;
    }

    return result;
}


int main()
{
    long long int n,k,z;
    cin>>n>>k;
    matrix base;
    for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cin>> base.mat[i][j];
    }}
    
    matrix ans=fast_exponentiation(base,k);
    long long int path=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        path=(path+ans.mat[i][j])%MOD;
    }
    cout<<path<<"\n";
    
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a[5],k,c=0;
  
  for(int i=0; i<5; i++){
    cin >> a[i];
  }
  
  cin >> k;
  
  for(int i=0; i<5; i++){
    for(int j=0; j<5; j++){
      if( abs(a[i] - a[j] ) > k ) c++;
    }
  }
  
  if( c==0 ) cout << "Yay!" << endl;
  else cout << ":(" << endl;
 
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main(){
    int n, k;
    cin >> n >> k;
    vector<pll> xy(n);
    vector<ll> x(n),y(n);
    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i];
        xy[i].first = x[i];
        xy[i].second = y[i];
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    ll ans = 9223372036854775807;

    for(int xi = 0; xi < n; xi++){
        for(int xj = xi+1; xj < n; xj++){
            for(int yi = 0; yi < n; yi++){
                for(int yj = yi+1; yj < n; yj++){
                    int num = 0;
                    ll left = x[xi];
                    ll right = x[xj];
                    ll down = y[yi];
                    ll up = y[yj];

                    for(int i = 0; i < n; i++){
                        if(left <= xy[i].first && xy[i].first <= right && down <= xy[i].second && xy[i].second <= up){
                            num ++;
                        }
                    }
                    if(num >= k){
                        ans = min(ans, (right-left)*(up-down));
                    }
                }
            }
        }
    }


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


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
if n==0:
    print(1 if a[0]==1 else -1)
    exit()
e=[1-a[0]]
for i in range(n):
    e.append(max(e[i]-a[i],0)*2)
#print(e)
p=[i for i in a]
for i in range(n-1,-1,-1):
    if -p[i+1]//2*-1+p[i]>e[i]:
        print(-1)
        exit()
    if p[i+1]+p[i]>e[i]:
        p[i]=e[i]
    else:
        p[i]+=p[i+1]
print(sum(p))
#print(p)

Measured memory_bytes: 680104
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7
MIN = 100


def org(N, M, dp):
    a = [0] * M

    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    for i in range(3, max(N+1, MIN)):
        dp[i] = dp[i-1] + dp[i-2]

    ans = 1

    for i in range(M):
        a[i] = int(input())

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= dp[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= dp[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    if M == 0:
        ans *= dp[N]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)
    else:
        ans *= dp[N - a[M-1] - 1]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)


def good(N, M, dp):
    a = [0] * len(dp)

    for i in range(M):
        a[int(input())-1] = True

    dp[0] = 0 if a[0] is True else 1
    dp[1] = 0 if a[1] is True else dp[0] + 1

    if N == 1:
        print(dp[0])
        return
    elif N == 2:
        print(dp[1])
        return

    for i in range(2, N):
        if a[i] is True:
            dp[i] = 0
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD

    print(dp[N-1] % MOD)
    # print(dp)


def main():
    N, M = map(int, input().split())
    dp = [0] * max((N + 1), MIN)

    good(N, M, dp)


if __name__ == '__main__':
    main()


Measured memory_bytes: 43228
#include<bits/stdc++.h>
using namespace std;
int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int L = a + b, R = c + d;
	if (L > R) {
		cout << "Left" << endl;

	}
	else if (L < R) {
		cout << "Right" << endl;


	}
	else {
		cout << "Balanced" << endl;
	}
	return 0;

}

Measured memory_bytes: 256
X, K, D = map(lambda x: int(x), input().split(" "))

candidates = []

if abs(X) >= abs(K*D):
    candidates.append(abs(X - K * D))
    candidates.append(abs(X + K * D))
else:
    tmp = X // D  # 何回移動すれば良いのか
    if tmp % 2 == K % 2:
        candidates.append(abs(X - tmp * D))
        candidates.append(abs(X + tmp * D))
    else:
        candidates.append(abs(X - (tmp+1) * D))
        candidates.append(abs(X + (tmp+1) * D))
        candidates.append(abs(X - (tmp-1) * D))
        candidates.append(abs(X + (tmp-1) * D))

print(min(candidates))



Measured memory_bytes: 9220