akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    int A,B,C;
    cin >> A >> B >> C;

    if(A<=C && C<=B)cout << "Yes" << endl;
    else if (A>=C && C>=B)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 REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

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

    string s; cin >> s;
    int ans = 0;
    int p = 0;
    REP(i, (int)s.length())
    {
        if(p > 0)
        {
            if(s[i] == 'g')
            {
                ans++;
                p--;
            }
            else
            {
                p--;        
            }
        }
        else
        {
            if(s[i] == 'g') 
            {
                p++;
            }
            else
            {
                ans--;
                p++;         
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3728
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>
#include<utility>
#include<numeric>

#define PB push_back
#define all(a)  (a).begin(),(a).end()
#define ALL(v) begin(v), end(v)
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)
#define V vector<int>
#define VV vector<V>
#define VVV vector<VV>

using namespace std;

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

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int INF = (int)1e9;
const ll inf = (ll)1e18;
const ll MOD{ (ll)1e9 + 7 };
const long double EPS = 1e-10;

map<int, int> num;

ll n, m;
string s, t;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

int main() {
	cin >> n >> m;
	cin >> s >> t;

	ll L = lcm(n, m);
	for (int i = 0; i < n; i++) {
		num[i * L / n + 1]++;
	}

	vector<int> a;
	for (int j = 0; j < m; j++) {
		if (num[j * L / m + 1] > 0) {
			a.push_back(j * L / m + 1);
		}
	}

	for (int k = 0; k < (int)a.size(); k++) {
		int i = (n * (a[k] - 1)) / L;
		int j = (m * (a[k] - 1)) / L;
		if (s[i] != t[j]) {
			cout << -1 << endl;
			return 0;
		}
	}

	cout << L << endl;
	return 0;
}

Measured memory_bytes: 8192
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
import random
def resolve():
    A,B,N=pin()
    def f(A,B,x):
        t=(A*x)//B
        s=x//B
        return t-A*s
    ans=0
    for i in range(10**6):
        k=random.randint(0,N)
        ans=max(ans,f(A,B,k))
    print(ans)
#%%submit!
resolve()

Measured memory_bytes: 9432
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<sstream>

using namespace std;

int main()
{
	long long int r, d, x2000;
	cin >> r >> d >> x2000;
	for (int i = 0; i < 10; i++)
	{
		x2000 *= r;
		x2000 -= d;
		cout << x2000 << endl;
	}

}

Measured memory_bytes: 256
A,B,K = map(int,input().split())
s = []

for i in range(K):
    if A+i <= B:
        s.append(A+i)
for i in range(K):
    if B-K+1+i >= A:
        s.append(B-K+1+i)
s = set(s)
Ans = []
for i in s:
    Ans.append(i)
Ans = sorted(Ans)
for i in Ans:
    print(i)

Measured memory_bytes: 38384
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    group = [set() for _ in range(2)]
    q = deque([(0, 0, -1)])
    while len(q):
        cur, g, prev = q.popleft()
        group[g].add(cur)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, 1-g, cur))
    if len(group[0]) > len(group[1]):
        tmp = group[0]
        group[0] = group[1]
        group[1] = tmp
    ans = [0] * N
    pool = set(range(1, N+1))
    if len(group[0]) <= N//3:
        for i, x in enumerate(group[0]):
            ans[x] = (i+1)*3
            pool.remove((i+1)*3)
        for x in group[1]:
            ans[x] = pool.pop()
    else:
        cand = (list(range(1, N+1, 3)) +
                list(range(3, N+1, 3)))[:len(group[0])]
        for x, v in zip(group[0], cand):
            ans[x] = v
            pool.remove(v)
        for x in group[1]:
            ans[x] = pool.pop()
    print(*ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 135024
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 11

int main(){

	int len;
	char migi[N] = "yuiophjklnm";
	char input[128];
	int cnt;
	int flag,a_flag;
	int flag2;
	int i,j;

	while(1){

		cnt = 0;
		flag2 = 0;

		scanf("%s",input);
		len = strlen(input);


		if(input[0] == '#' ){
			break;
		}
		for(i=0; i<len; i++){
			for(j=0; j<N; j++){
				if(input[i] == migi[j]){
					flag = 1;
					break;
				}
				else{
					flag = 0;
				}
			}
			if(flag2 == 0){
				flag2 = 1;
				a_flag = flag;
			}

			if(flag != a_flag){
				cnt++;
			}
			a_flag = flag;

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

	return 0;
}

Measured memory_bytes: 540
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#define maxn 200005
#define Rint register int
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long lxl;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

int n,Q,A,B,a[maxn];
lxl f[maxn];

struct node
{
	int l,r;
	lxl min1,min2,lazy;//f_{i,j}+j f_{i,j}-j
}tree[maxn<<2];

#define ls (p<<1)
#define rs (p<<1|1)

inline void add(int p,lxl d)
{
	tree[p].min1+=d;
	tree[p].min2+=d;
	tree[p].lazy+=d;
}

inline void push_down(int p)
{
	if(!tree[p].lazy) return;
	add(ls,tree[p].lazy);
	add(rs,tree[p].lazy);
	tree[p].lazy=0;
}

inline void maintain(int p)
{
	tree[p].min1=min(tree[ls].min1,tree[rs].min1);
	tree[p].min2=min(tree[ls].min2,tree[rs].min2);
}

inline void build(int p,int l,int r)
{
	tree[p]=(node){l,r,INF,INF,0};
	if(l==r) return;
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	maintain(p);
}

inline void modify(int p,int ps,lxl d)
{
	int l=tree[p].l,r=tree[p].r;
	if(l==r)
	{
		tree[p].min1=min(tree[p].min1,d+l);
		tree[p].min2=min(tree[p].min2,d-l);
		return;
	}
	push_down(p);
	int mid=(l+r)>>1;
	if(ps<=mid) modify(ls,ps,d);
	else modify(rs,ps,d);
	maintain(p);
}

inline lxl query_min1(int p,int L,int R)
{
	int l=tree[p].l,r=tree[p].r;
	if(L<=l&&r<=R) return tree[p].min1;
	push_down(p);
	int mid=(l+r)>>1;lxl ans=INF;
	if(L<=mid) ans=min(ans,query_min1(ls,L,R));
	if(R>mid) ans=min(ans,query_min1(rs,L,R));
	return ans;
}

inline lxl query_min2(int p,int L,int R)
{
	int l=tree[p].l,r=tree[p].r;
	if(L<=l&&r<=R) return tree[p].min2;
	push_down(p);
	int mid=(l+r)>>1;lxl ans=INF;
	if(L<=mid) ans=min(ans,query_min2(ls,L,R));
	if(R>mid) ans=min(ans,query_min2(rs,L,R));
	return ans;
}

inline lxl query(int p,int L,int R)
{
	int l=tree[p].l,r=tree[p].r;
	if(l==r) return tree[p].min1-l;
	push_down(p);
	int mid=(l+r)>>1;lxl ans=INF;
	if(L<=mid) ans=min(ans,query(ls,L,R));
	if(R>mid) ans=min(ans,query(rs,L,R));
	return ans;
}

int main()
{
	read(n),read(Q);
	read(A),read(B);
	build(1,1,n);
	a[0]=A;
	modify(1,B,0);
	for(int i=1;i<=Q;++i)
	{
		read(a[i]);
		lxl val=min(query_min1(1,a[i],n)-a[i],query_min2(1,1,a[i])+a[i]);
		tree[1].min1+=abs(a[i]-a[i-1]);
		tree[1].min2+=abs(a[i]-a[i-1]);
		tree[1].lazy+=abs(a[i]-a[i-1]);
		modify(1,a[i-1],val);
	}
	printf("%lld\n",query(1,1,n));
	return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n; i += 1)
        cin >> a[i];
        
    vector<vector<int64_t>> dp(n + 1, vector<int64_t> (n + 1, numeric_limits<int64_t> :: max() / 2));
    
    dp[1] = vector<int64_t> (n + 1, 0);

    for (int len = 2; len <= n; len += 1)
        for (int start = 0; start + len - 1 < n; start += 1) {
            int left = start;
            int right = start + len - 1;
            for (int split = left; split < right; split += 1) 
                dp[len][start] = min(dp[len][start], dp[split - left + 1][left] + dp[right - split][split + 1]);
            dp[len][start] += accumulate(a.begin() + start, a.begin() + start + len, 0LL);
        }

    cout << dp[n][0] << "\n";
}

Measured memory_bytes: 1536
from collections import Counter
from sys import stdin

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

cnt = Counter(A)

tmp = cnt.most_common()


def comb(n):
    return n * (n - 1) // 2


sumall = 0

for i in range(len(cnt)):
    sumall += comb(tmp[i][1])

for a in A:
    ans = sumall - (comb(cnt[a]) - comb(cnt[a] - 1))
    print(ans)


Measured memory_bytes: 29808
X, N = map(int, input().split())
p = list(map(int, input().split()))

not_in_p = list(range(-101,102))
for pn in p:
    if pn in not_in_p:
        not_in_p.remove(pn)

diff_p = []
for not_in_pn in not_in_p:
    diff_p.append(abs(not_in_pn - X))
answer = not_in_p[diff_p.index(min(diff_p))]

print(answer)

Measured memory_bytes: 9192
#include<stdio.h>

struct Card{
  char Su;
  char Va;
};

void bubble(struct Card o[], int n){
  int i, j;
  struct Card t;
  for (i=0;i<n;i++){
    for (j= n-1;j>= i+1;j--){
      if (o[j].Va<o[j-1].Va){
	t=o[j];o[j]=o[j-1];o[j-1]=t;
      }
    }
  }
}

void selection(struct Card o[], int n){
  int i, j, Mi;
  struct Card t;
  for ( i = 0; i < n; i++ ){
    Mi=i;
    for (j=i;j<n;j++){
      if(o[j].Va<o[Mi].Va )Mi=j;
    }
    t=o[i];o[i]=o[Mi];o[Mi]=t;
  }
}

void print(struct Card o[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( i ) printf(" ");
    printf("%c%c", o[i].Su, o[i].Va);
  }
  printf("\n");
}

int isStable(struct Card C1[], struct Card C2[], int n){
  int i;
  for ( i = 0; i < n; i++ ){
    if ( C1[i].Su != C2[i].Su ) return 0;
  }
  return 1;
}

int main(){
  struct Card C1[101], C2[101];
  int n, i;
  char ch;

  scanf("%d\n", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%c%c ", &C1[i].Su, &C1[i].Va);
  }

  for (i=0;i<n;i++)C2[i]=C1[i];

  bubble(C1, n);
  selection(C2, n);

  print(C1, n);
  printf("Stable\n");
  print(C2, n);
  if ( isStable(C1, C2, n) ){
    printf("Stable\n");
  } else {
    printf("Not stable\n");
  }

  return 0;
}



Measured memory_bytes: 2052
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val ab = (1..n).map{
        val (a, b) = readLine()!!.split(' ').map(String::toInt)
        Pair(a, b)
    }.sortedBy { it.second }
    var po = 0
    var ans = "Yes"
    for(i in 0 until n) {
        po += ab[i].first
        if (po > ab[i].second) {
            ans = "No"
            break
        }
    }
    println(ans)
}


Measured memory_bytes: 124460
#include<iostream>
using namespace std;
int main()
{   
	int N,K,h,p;
	cin>>N>>K;
	p=0;
	for(int t=1;t<=N;t++)
	{
		cin>>h;
		if(h>=K)
		p++;	
	}
	cout<<p;
	return 0; 		
}	

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
#define MOD 1000000007
using namespace std;
typedef long long ll;


int main(void) {
	int n, x, y; cin >> n >> x >> y;
	vint a(n);
	vvint v(n);
	x--; y--;
	v[x].push_back(y);
	v[y].push_back(x);
	rep(i, n-1) {
		v[i].push_back(i + 1);
		v[i + 1].push_back(i);
	}

	for (int i = 0; i < n-1;i++) {
		vint d(n, INT_MAX);
		queue <int> q;
		q.push(i);
		d[i] = 0;
		while (q.size() != 0) {
			int now = q.front(); q.pop();
			for (int k = 0; k < v[now].size(); k++) {
				if (d[v[now][k]]>d[now] + 1) {
					q.push(v[now][k]);
					d[v[now][k]] = d[now] + 1;
				}
			}
		}
		for (int j = i +1; j < n; j++) {

			a[d[j]]++;
			
		}
	}
	for (int i = 1; i < n;i++) {
		cout << a[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N;
  cin >> N;
  int h, n, w;
  for (int i = 1; i <= 3500; i++) {
    for (int j = 1; j <= 3500; j++) {
      ll part = N * i * j;
      ll div = (4 * i * j - N * i - N * j);
      if (div > 0 && part % div == 0) {
        h = i, n = j;
        w = part / div;
        cout << h << " " << n << " " << w << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 11
#define SIZE 6000

int N, K;
char A[MAXN][10];
int used[MAXN];
char num[100];
int size;
int arr[SIZE];

void rec(int k) {
  int i;
  int length = strlen(num);
  if(k == K) {
    arr[size++] = atoi(num);
    return;
  }
  for(i = 0; i < N; ++i) {
    if(!used[i]) {
      used[i] = 1;
      strcat(num, A[i]);
      rec(k+1);
      used[i] = 0;
      num[length] = '\0';
    }
  }
}

void bubbleSort() {
  int i, j, t;
  for(i = 0; i < size; ++i) {
    for(j = 1; j < size-i; ++j) {
      if(arr[j-1] > arr[j]) {
	t = arr[j-1];
	arr[j-1] = arr[j];
	arr[j] = t;
      }
    }
  }
}

int main() {
  int i, ans;
  while(1) {
    scanf("%d", &N);
    scanf("%d", &K);
    if(N == 0 && K == 0) break;
    for(i = 0; i < N; ++i) {
      scanf("%s", A[i]);
    }

    for(i = 0; i < N; ++i) {
      used[i] = 0;
    }
    strcpy(num, "");
    size = 0;
    rec(0);
    bubbleSort();

    ans = 0;
    for(i = 0; i < size; ++i) {
      if(i == 0 || arr[i-1] != arr[i]) {
	++ans;
      }
    }

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

Measured memory_bytes: 1060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
 
 
 
 
public class Main {
    ArrayList<Integer>[] graph;
    boolean[] vis;
    int[] cost;
    queue q = new queue((int)1e6);
    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        new Main();
    }
 
    Main() throws IOException {
        solve();
    }
 
    void solve() throws IOException {
        Reader.init(System.in);
        int N = Reader.nextInt();
        int K = Reader.nextInt();
        long c1 = N/K;
        if((K&1) == 1){System.out.println((c1*(c1)*(c1)));}
        else{
            long c2 = N/K;
            if(N%K >= K/2 && K/2 != 0){c2 += 1;}
            System.out.println(((c1)*(c1)*(c1)) + (c2*c2*c2));
        }
    }
 
}
 
class queue{
    int front;
    int rear;
    int[] array;
    int capacity;
    int size;
    queue(int cap){
        front = rear = -1;
        array = new int[cap+1];
        capacity = cap;
        size = 0;
    }
 
    void enqueue(int x){
        if(front == -1){
            array[++front] = x;
            rear++;
            size++;
            return;
        }
        else{
            array[++rear] = x;
            size++;
        }
    }
 
    int dequeue(){
        if(size == 0){return -1;}
        if(front == rear){
            int out = array[front];
            front = rear = -1;
            size--;
            return out;
        }
        else{
            size--;
            return array[front++];
        }
    }
}
 
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
    /** call this method to initialize reader for InputStream */
 
    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
 
    }
 
    static String nextToken() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
 
                tokenizer = new StringTokenizer(reader.readLine());
 
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    static String next() throws IOException {
 
        while ( ! tokenizer.hasMoreTokens() ) {
 
            tokenizer = new StringTokenizer(
 
                    reader.readLine() );
 
        }
        return tokenizer.nextToken();
 
    }
 
    static int nextInt() throws IOException {
 
        return Integer.parseInt( next() );
 
    }
 
    static double nextDouble() throws IOException {
 
        return Double.parseDouble( next() );
 
    }
 
    static long nextLong() {
 
        return Long.parseLong(nextToken());
    }
}

Measured memory_bytes: 25556
#include<stdio.h>
#include<stdlib.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define POS(i,j) ((i)*n+(j))

inline void swap(int *a,int *b){
  int t=*a;
  *a=*b;
  *b=t;
}

int calc(int index,int *v,int r,int *d,int n){
  if(index==r){
    int sum=0;
    for(int i=0;i+1<r;i++) sum+=d[POS(v[i],v[i+1])];
    return sum;
  }
  int res=calc(index+1,v,r,d,n);
  for(int i=index+1;i<r;i++){
    swap(v+index,v+i);
    int local=calc(index+1,v,r,d,n);
    res=MIN(res,local);
    swap(v+index,v+i);
  }
  return res;
}

void run(void){
  int n,m,r;
  scanf("%d%d%d",&n,&m,&r);
  int v[8];
  int i,j,k;
  for(i=0;i<r;i++){
    scanf("%d",v+i);
    v[i]--;
  }
  int *d=(int *)calloc(n*n,sizeof(int));
  for(i=0;i<n;i++) for(j=0;j<n;j++) d[POS(i,j)]=(i==j?0:100000*200);
  for(i=0;i<m;i++){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    a--;b--;
    d[POS(a,b)]=d[POS(b,a)]=c;
  }
  for(k=0;k<n;k++){
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	d[POS(i,j)]=MIN(d[POS(i,j)],d[POS(i,k)]+d[POS(k,j)]);
      }
    }
  }
  int ans=calc(0,v,r,d,n);
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 384
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using 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 (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

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

uintmax_t combination(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;
  uintmax_t dividend = 1;
  uintmax_t divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

int modPow(long long a, long long n, long long p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  long long t = modPow(a, n / 2, p);
  return (t * t) % p;
}

int main()
{
    ll n,k;
    cin >> n >> k;
    vector<pair<int,int>> a(n);
    rep(i,n) cin >> a[i].first >> a[i].second;

    sort(a.begin(),a.end());

    ll count = 0;
    ll ans;

    rep(i,n){
        count+=a[i].second;
        if(count >= k){
            ans = a[i].first;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
//
//  main.cpp
//  contest
//
//  Created by TmpGuest on 2020/4/18.
//  Copyright © 2020 TmpGuest. All rights reserved.
//

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
int main() {
ios_base::sync_with_stdio(false);
    cin.tie(0);
    int day,homework,write=0,temp;
    cin>>day>>homework;
    for(int i=0;i<homework;i++) {
        cin>>temp;
        write+=temp;
    }
    if(write>day)
        cout<<"-1\n";
    else
        cout<<day-write<<endl;
        
    
    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int sN = s.size();
    int tN = t.size();

    vector<vector<int>> l(26);
    rep(i,sN){
      int al = s[i] - 'a';
      l[al].push_back(i+1);
    }

    ll ans = 0;
    int before = -1;

    rep(i,tN){
      int al = t[i] - 'a';

      if(l[al].size() == 0){
        cout << "-1" << endl;
        return 0;
      }

      if(i == 0){
        ans = l[al][0];
        before = ans;
        continue;
      }

      int index = lower_bound(all(l[al]),before+1) - l[al].begin();

      if(index >= l[al].size()){
        ans += sN - before + l[al][0];
        before = l[al][0];
      } else {
        ans += l[al][index] - before;
        before = l[al][index];
      }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1216
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include<deque>
#include<list>


using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const ll MOD_CONST = 1000000007;
const ll BIG_NUM = 1000000000000000000;
const int BIG_INT = 1000000000;




int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());

	vector<ll> sum(n + 1);
	for (int i = 1;i <= n;i++) {
		sum[i] = sum[i - 1] + a[i - 1];
	}
	if (k == 1) {
		cout << 0 << endl;
		return 0;
	}

	

	vector<ll> facto(n + 1);
	vector<ll> inv_mod(n + 1);
	vector<ll> inv_facto(n + 1);
	facto[0] = inv_mod[1] = inv_facto[0] = 1;
	for (int i = 2;i <= n;i++) {
		inv_mod[i] = (MOD_CONST - (inv_mod[MOD_CONST%i] * (MOD_CONST / i)) % MOD_CONST) % MOD_CONST;

	}

	for (int i = 1; i <= n;i++) {
		facto[i] = (facto[i - 1] * i) % MOD_CONST;
		inv_facto[i] = (inv_facto[i - 1] * inv_mod[i]) % MOD_CONST;
	}


	ll ans = 0;
	for (int i = k;i <= n;i++) {
		ll s = (MOD_CONST+ sum[n] - sum[i - 1] - sum[n - i + 1]) % MOD_CONST;
		
		s = (s * facto[i - 2]) % MOD_CONST;
		s = (s * inv_facto[k - 2]) % MOD_CONST;
		s = (s * inv_facto[i - k]) % MOD_CONST;
		
		ans = (ans + s) % MOD_CONST;
	}

	cout << ans << endl;
}



Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
int main(){
    int a,b;
    cin>>a>>b;
    cout<<(b-a-1)*(b-a)/2 - a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for(int i = (int)(n); i>=0; --i)
struct fast_ios { fast_ios(){cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast_ios_;

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> lst(N);
    rep(i, N)
    {
        cin >> lst[i];
    }

    sort(lst.begin(), lst.end());

    int sum=0;
    rep(i, K)
    {
        sum+=lst[i];
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
const int inf = 1e+9+10;
struct Graph{
  int node;
  vector<vector<int>> edge;
  int liq;
  vector<vector<int>> edge2;

  
  Graph(int n,int l){
    node = n;
    liq = l;
    edge.resize(node,vector<int>(node,inf));
    edge2.resize(node,vector<int>(node,inf));    
  }

  void add(int from,int to,int cost){
    edge[from][to]=cost;
  }

  void wf(){
    rep(k,node){
      rep(i,node){
  	rep(j,node){
	  edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
	}
      }
    }
  }

  void add2(){
    rep(i,node){
      rep(j,node){
	if(i==j) continue;
	if(edge[i][j]<=liq) edge2[i][j]=1;
      }
    }
  }
  
  void wf2(){
    rep(k,node){
      rep(i,node){
  	rep(j,node){
	  edge2[i][j]=min(edge2[i][j],edge2[i][k]+edge2[k][j]);
	}
      }
    }
  }

  
  

};



int main()
{
  int n,m,l;
  cin >> n >> m >> l;
  vector<int> a(m),b(m),c(m);
  rep(i,m) cin >> a[i] >> b[i] >> c[i];
  int q;
  cin >> q;
  vector<int> s(q),t(q);
  rep(i,q) cin >> s[i] >> t[i];

  Graph gp(n,l);

  rep(i,m){
    a[i]--;
    b[i]--;
    gp.add(a[i],b[i],c[i]);
    gp.add(b[i],a[i],c[i]);    
  }
  gp.wf();

  gp.add2();
  gp.wf2();

  rep(i,q){
    s[i]--;
    t[i]--;
    if(gp.edge2[s[i]][t[i]]==inf) cout << -1 << "\n";
    else cout << gp.edge2[s[i]][t[i]]-1 << "\n";
  }
  

  
  return 0;
}


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

string check(string S, char edge) {
  int i = 0;
  do {
    ++i;
    char c = S[i];
    if (edge != c) {
      break;
    } else {
      S[i] = edge == 'B' ? 'W' : 'B';
    }
  } while (i != S.size() - 1);
  return S;
}

int main() {
  string S;
  cin >> S;
  int result = 0;
  char cur_c = S[0];
  for (int i = 1; i < S.size(); ++i) {
    char c = S[i];
    if (cur_c != c) {
      cur_c = c;
      ++result;
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 512
#include <stdio.h>
#include <ctype.h>

int main(){
	char ch;
	
	while(1){
       scanf("%c", &ch);
       // ??????????????????
	   if(islower(ch)){
	       ch = toupper(ch);
	   }else if(isupper(ch)){
	       ch = tolower(ch);
	   }
	   printf("%c", ch);
       if ( ch == '\n' ) break;
	}
	return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", ans);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main(void) {
    int d, n;
    cin >> d >> n;

    if (d == 2 && n == 100) {
        cout<<1010000<<endl;
    }
    else if (n != 100) cout << pow(100, d) * n << endl;
    else cout << pow(100, d) * n + pow(100, d) << endl;

    return 0;
}


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

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define ALL(v) v.begin(), v.end()
#define SZ(x) ((ll)(x).size())

const double PI  = acos(-1.0);
const ll INF = 1e18+3;
const ll mod = 1e9 + 7; //998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define print(x) cerr << #x << " is " << x << endl;

ll A[100001], sum[100001];

int main(void){
    ll N, X, M;
    cin >> N >> X >> M;
    vector<ll> PREV(M + 1, -1);
    
    A[0] = X;
    sum[0] = X;
    if (N == 1){
        cout << sum[0];
        return 0;
    }
    PREV[X] = 0;
    ll ans = 0;
    
    rep(i, N){
        A[i + 1] = A[i] * A[i] % M;
        sum[i + 1] = sum[i] + A[i + 1];
        //fprintf(stderr, "%d, %d, %d\n", i + 1, A[i + 1], sum[i + 1]);
        if (i + 1 == N - 1){
            cout << sum[i + 1];
            return 0;
        }
        
        if (PREV[A[i + 1]] == -1){
            PREV[A[i + 1]] = i + 1;
        } else {
            int p = PREV[A[i + 1]];
            int q = i + 1;
            ll ans = sum[p - 1];
            ans += (sum[q] - sum[p]) * (ll)((N - 1 - p)/(q - p));
            ll val = A[i + 1];
            reps(j, p, q){
                ans += val;
                if ((N - 1) % (q - p) == j % (q - p)){
                    cout << ans;
                    return 0;
                }
                val = val * val % M;
            }
        }
    }
    return 0;
}
   

Measured memory_bytes: 4672
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FOR(i) for(cin>>i;i>0;i--)
#define elif else if
#define pb push_back
#define ll long long
#define mp make_pair
#define all(x) x.begin(),x.end()
#define re(x) {cout<<x<<endl;return 0;}
//#define x first
//#define y second

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
	li x = 0,y = 0,c = gc;
	while(!isdigit(c)) y = c,c = gc;
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
	return y == '-' ? -x : x;
}
void print(li q){
	if(q < 0){
		pc('-');
		q = -q;
	}
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
li s1 = 19260817,s2 = 23333333,s3 = 998244853,srd;
li rd(){
	return srd = (srd * s1 + s2 + rand()) % s3;
}
int n,m,a[200010],as;
bool usd[200010];
void file(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
//const int mo = 998244353;
//const int mo = 1000000007;

int main(){
	srand(time(0));rd();
	//file();
	int i,j,k,mx;
	n = read();for(i = 1;i <= n;++i) a[i] = read();sort(a + 1,a + n + 1);
	for(k = 30;k;--k){
		mx = 1 << k;
		for(i = 1,j = n;i < j;++i){
			while(usd[i] && i < j) ++i;
			while((usd[j] || a[i] + a[j] > mx) && i < j) --j;
			if(i < j && a[i] + a[j] == mx){
				usd[i] = usd[j] = 1;++as;
			}
		}
	}
	print(as);	
	return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include<math.h>
using namespace std;

int main()
{
    int w,h,x,y,r;
    w=h=x=y=r=0;
    cin >> w;
    cin >> h;
    cin >> x;
    cin >> y;
    cin >> r;
    if ((x-r >= 0) && (y-r >= 0) && (x+r <= w) &&(y+r <= h)) {

            cout << "Yes" << endl;

    }

    else{
        cout << "No" << endl;
    }
}

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

using ll = long long;
using pp = pair<ll,ll>;
const ll amari = 1e9+7;
const char BC = 'A' - 'a';
#define ben(a) a.begin(),a.end()
#define pb(a,b) a.push_back(b)
//fixed << setprecision(20)
int main(){
	ll l,r;
	cin >> l >> r;
	ll mini = 2019;
	int ok = 0;
	for(ll i = r; i >= l; i--){
		for(ll j = r; j >= l; j--){
			if(i == j)continue;
			mini = min(mini,(i * j) % 2019);
			if(mini == 0)ok = 1;

			if(ok)break;
		}
		if(ok)break;
	}
	cout << mini << endl;
	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, s: "List[int]", c: "List[int]"):

    G = [-1]*N

    for i in range(M):
        if G[s[i]-1] != -1 and G[s[i]-1] != c[i] :
            print(-1)
            sys.exit()
        elif s[i] == 1 and c[i] == 0 and N != 1:
            print(-1)
            sys.exit()
        else:
            G[s[i]-1] = c[i]


    for j in range(N-1):
        if G[j+1] == -1:
            G[j+1] = 0


    if G[0] == -1 and N >= 2:
        G[0] = 1
    
    if G[0] == -1 and N == 1:
        G[0] = 0
         

    G = [str(n) for n in G]

    num = ''.join(G)

    print(num)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    s = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        s[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, s, c)

if __name__ == '__main__':
    main()


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

#define ll long long int
#define fi first
#define se second
#define pb push_back
#define pi 3.141592653589793238
#define MOD 1000000007
#define FOR(i,a,n) for(ll i=a;i<=n;i++)
#define ROF(i,n,a) for(ll i=n;i>=a;i--)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    float r; cin>>r;
    cout<<(2*pi*r)<<endl;
   return 0; 
}

Measured memory_bytes: 3800
#79c
S = str(input())

for i in range(2**(len(S)-1)):
    bit_array = str(bin(i)[2:]).zfill((len(S)-1))
    
    stored = int(S[0])
    
    for j in range(len(bit_array)):
        
        if bit_array[j]=="0":
            stored = stored + int(S[j+1])
        elif bit_array[j]=="1":
            stored =  stored - int(S[j+1])
    
    if stored == 7:
        print(int(S[0]),end="")
        for k in range(3):
            if bit_array[k]=="0":
                print("+",end="")
            elif bit_array[k]=="1":
                print("-",end="")
            
            print(S[k+1],end="")
        print("=7")
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
const ull MOD = (int)1e9 + 7;
#ifdef LOCAL
#include "../../pp.hpp"
#define debug pp::debug
#else
#define debug(args...)
#endif

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

    int h, w; cin >> h >> w;
    vvi A(h, vi(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) { 
            char c; cin >> c;
            A[i][j] = (c == '.');
        }
    }

    vvi dp(h, vi(w, 0));
    dp[h-1][w-1] = 1;
    for (int i = h - 1; i >= 0; --i) {
        for (int j = w - 1; j >= 0; --j) {
            if (i == h - 1 && j == w - 1) {

            } else if (i == h - 1) {
                if (A[i][j+1]) dp[i][j] = dp[i][j+1];
            } else if (j == w - 1) {
                if (A[i+1][j]) dp[i][j] = dp[i+1][j];
            } else {
                if (A[i+1][j]) dp[i][j] = dp[i+1][j];
                if (A[i][j+1]) dp[i][j] = (dp[i][j] + dp[i][j+1]) % MOD;
            }
        }
    }
    debug("A", A);
    debug("dp", dp);

    cout << dp[0][0] << '\n';
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

int main() {
    int N;
    string S;
    cin >> N >> S;

    if (N % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i < S.size() / 2; i++) {
        if (S[i] != S[S.size() / 2 + i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

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

int main() {
    int M, D;
    cin >> M >> D;
    int cnt = 0;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= D; j++) {
            string d = to_string(j);
            int d_ten = d[0] - '0';
            int d_one = d[1] - '0';
            if (d_ten >= 2 && d_one >= 2 && d_ten * d_one == i) {
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <list>
#include <stack>
#include <queue>
#include <utility>

using namespace std;

#define ll long long
#define ld long double
#define MOD 1000000007
#define rep(i, n) for(int i = 0;i < n;i++)
#define PI 3.14159265358979323846

ll binary(ll bina){
    ll ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<char> > list;
    ll temp;
    for (int i = 0; i < n; i++)
    {
        int test;
        cin >> test;
        vector<char> vc(n,2);//2は不明。1が正直、0が不親切
        for (int j = 0; j < test; j++)
        {
            int x,y;
            cin >> x >> y;
            if (y==1)
            {
                vc[x-1] = '1';
            }else
            {
                vc[x-1] = '0';
            }
        }
        list.push_back(vc);
    }
    //cout << list[0][1] << endl;
    int ans = 0;
    for (int i = 0; i < pow(2,n); i++)
    {
        temp = binary(i);
        string str;
        str = to_string(temp);
        if (str.length()<n)
        {
            int limit = n-str.length();
            for (int j = 0; j < limit; j++)
            {
                str ="0"+str;
            }
        }
        //cout << str << endl;
        //vector<int> honest_unkind(n,2);
        int flag = 0;
        for (int k = 0; k < n; k++)
        {
            if (flag == 1)
            {
                break;
            }
            
            if (str[k]=='1')
            {
                for (int l = 0; l < n; l++)
                {
                    if (list[k][l]!=2)
                    {
                        if (str[l]!=list[k][l])
                        {
                            flag = 1;
                            break;
                        } 
                    }
                }
            }
        }
        //cout << flag << endl;
        if (flag==0)
        {
            int ans_temp = 0;
            for (int i = 0; i < n; i++)
            {
                if (str[i]=='1')
                {
                    ans_temp++;
                }
            }
            ans = max(ans, ans_temp);
        }
        
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main()
{
	int n, k, x, y, bill;
	scanf("%d%d%d%d", &n, &k, &x, &y);
	if(n <= k) bill = n * x;
	else {
		bill = k * x + (n - k) * y;
	}
	printf("%d\n", bill);
	return 0;
}


Measured memory_bytes: 128
//Pasta
#include <iostream>
#include <map>

using namespace std;

static const int MOD = 10000;

int main() {
    int N, K, a, b;
    cin >> N >> K;
    map<int, int> m;
    for(int i = 0; i < K; i++) {
        cin >> a >> b;
        m.insert(make_pair(a - 1, b - 1));
    }
    int dp[N][3][3];
    for(int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                dp[i][j][k] = 0;
            }
        }
    }

    auto itr1 = m.find(0);
    if(itr1 == m.end()) {
        for(int j = 0; j < 3; j++) {
            auto itr2 = m.find(1);
            if(itr2 == m.end()) {
                for (int k = 0; k < 3; k++) {
                    dp[1][j][k] = 1;
                }
            } else dp[1][j][itr2 -> second] = 1;
        }
    } else {
        auto itr2 = m.find(1);
        if(itr2 == m.end()) {
            for (int k = 0; k < 3; k++) {
                dp[1][itr1 -> second][k] = 1;
            }
        } else dp[1][itr1 -> second][itr2 -> second] = 1;
    }

    for(int i = 2; i < N; i++) {
        auto itr = m.find(i);
        if(itr == m.end()) {
            for(int k = 0; k < 3; k++) {
                for(int j = 0; j < 3; j++) {
                    if(j != k) dp[i][j][k] = dp[i - 1][0][j] + dp[i - 1][1][j] + dp[i - 1][2][j];
                    else dp[i][j][k] = dp[i - 1][0][j] + dp[i - 1][1][j] + dp[i - 1][2][j] - dp[i - 1][j][j];
                    dp[i][j][k] %= MOD;
                }
            }
        } else {
            for(int j = 0; j < 3; j++) {
                if(j != itr -> second) dp[i][j][itr -> second] = dp[i - 1][0][j] + dp[i - 1][1][j] + dp[i - 1][2][j];
                else dp[i][j][itr -> second] = dp[i - 1][0][j] + dp[i - 1][1][j] + dp[i - 1][2][j] - dp[i - 1][j][j];
                dp[i][j][itr -> second] %= MOD;
            }
        }
    }

    int c = 0;
    for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++)
            c += dp[N - 1][j][k];
    c %= MOD;

    cout << c << endl;

    return 0;
}


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

using namespace std;

const int maxn=110000;
int n,k,h[maxn],f[maxn];
int main(){
    scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	memset(f,0x3f,sizeof(f)),f[1]=0;
	for(int i=2;i<=n;i++) for(int j=1;j<i&&j<=k;j++) f[i]=min(f[i],f[i-j]+abs(h[i]-h[i-j]));
	printf("%d",f[n]);
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
int main() {
	std::cin.tie(0); std::cin.sync_with_stdio(false);
	int n; long long int k; std::cin >> n >> k;
	std::vector<long long int> consumption(n), foods(n); 
	for (auto& c : consumption) std::cin >> c;
	for (auto& f : foods) std::cin >> f;
	std::sort(consumption.begin(), consumption.end(), std::greater<int>()); 
	std::sort(foods.begin(), foods.end());
	long long int min = 0LL, max = consumption.front() * foods.back();
	while (min < max) {
		const auto mid = (min + max) / 2;
		long long int rest = k;
		for (auto i = 0; i < n; ++i) {
			if (foods[i] * consumption[i] > mid) {
				rest -= consumption[i] - mid / foods[i];
			}
		}
		if (rest >= 0) max = mid;
		else min = mid + 1;
	}
	std::cout << min << '\n';
}


Measured memory_bytes: 3328
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 1e5 + 10 ;
int main(){
    fastio
    ll n , m , q ;
    cin >> n >> m >> q ;
    map<ll,vector<ll> > mp ;
    for(ll i = 0; i < m; i++){
        ll x , y ;
        cin >> x >> y ; 
        mp[x].push_back(y) ; 
    }
    for(auto &p : mp){
        sort(p.second.begin(), p.second.end());
    }
    for(ll i = 0; i < q; i++){
        ll x , y ;
        cin >> x >> y ; 
        ll ans = 0 ; 
        for(ll j = x; j <= y; j++){
            auto it = mp.find(j) ; 
            vector<ll> &v = it->second ;
            ans += upper_bound(v.begin(), v.end(), y) - v.begin() ;
        }
        cout << ans << endl;
    }
    return 0 ;
}

Measured memory_bytes: 3584
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]*n*9
for i in range(n):
 for j in a:
  c=(0,2,5,5,4,5,6,3,7,6)[j]
  if d[i]or i<1:d[i+c]=max(d[i+c],d[i]*10+j)
print(d[n])

Measured memory_bytes: 15332
s = gets.chomp.split('').map(&:to_i)
s_length = s.length
a = (1..s_length).map { |i| (i % 2 == 1) ? 0 : 1 }
b = a.map { |i| i.to_s == '0' ? 1 : 0 }
count_a = 0
count_b = 0
s.each_with_index do |i, index|
  if i == a[index]
    count_b += 1    
  else
    count_a += 1
  end
end

puts count_a > count_b ? count_b : count_a

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

const int limit=3000;
bool isprime[limit+1];
vector<ll> prime;

void init(){
	rep(i,limit+1) isprime[i]=true;
	isprime[0]=isprime[1]=false;
	for(ll i=2;i*i<=limit;++i){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=i*i;j<=limit;j+=i)
				isprime[j]=false;
		}
	}
	return;
}

map<ll,int> cnt;

int main(void){
	init();
	const int m=prime.size();

	int n;
	cin >> n;
	rep(i,n){
		ll cur;
		cin >> cur;

		rep(j,m){
			ll cube=1LL*prime[j]*prime[j]*prime[j];
			while(cur%cube==0) cur/=cube;
		}
		cnt[cur]++;
	}

	ll ans=0LL;

	/*
	for(auto &it:cnt){
		cout << it.first << " " << it.second << " " << comp[it.first] << endl;
	}
	*/

	for(auto &it:cnt){
		if(it.first==1)
			ans+=min<ll>(1LL,it.second);
		else{
			ll tar=1LL*it.first*it.first;
			rep(j,m){
				ll cube=1LL*prime[j]*prime[j]*prime[j];
				while(tar%cube==0) tar/=cube;
			}
			ans+=max<ll>(it.second,cnt[tar]);
			it.second=0LL;
			cnt[tar]=0LL;
		}
	}
	cout << ans << endl;
	return 0;	
}

Measured memory_bytes: 21376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, k;
    cin >> n >> k;
    ll r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    set<ll> rs, ss, ps;
    ll ans = 0;
    rep(i, n) {
        if (t[i] == 'r') {
            if (ps.count(i - k) == 0) {
                ps.insert(i);
                ans += p;
            }
        }
        if (t[i] == 's') {
            if (rs.count(i - k) == 0) {
                rs.insert(i);
                ans += r;
            }
        }
        if (t[i] == 'p') {
            if (ss.count(i - k) == 0) {
                ss.insert(i);
                ans += s;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5072