akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
const ll INF = 1LL<<60;
const ll mod=1e9+7;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

ll a[220][220],d[220];
ll b[220];
int main(){
    ll n,k,ans=0;
    cin>>n>>k;
    rep(i,0,k){
        cin>>d[i];
        rep(j,0,d[i]){
            cin>>a[i][j];
            b[a[i][j]]++;
        }
    }
    rep(i,1,n+1)if(b[i]==0)ans++;
    cout<<ans;
}

Measured memory_bytes: 3812
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>

using namespace std;

int main(void) {
	int h, w;
	cin >> h >> w;
	vector<string>a(h);
	for (int i = 0; i < h; i++)cin >> a[i];
	for (int i = 1; i <= w + 2; i++) {
		cout << "#";
	}
	cout << endl;
	for (int i = 0; i < h; i++) {
		cout << "#" << a[i] << "#" << endl;
	}
	for (int i = 1; i <= w + 2; i++) {
		cout << "#";
	}
	return 0;
}

Measured memory_bytes: 256
from math import gcd


class Eratosthenes(): # エラトステネスの篩
    def __init__(self, N): # 素数リスト生成 O(n*log(log n))
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N**0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i * 2, N + 1, i):
                self.fact[j] = i


    def factor(self, NUM): # 高速素因数分解 O(log num)
        PRIME = set()
        while NUM > 1:
            PRIME.add(self.fact[NUM])
            NUM //= self.fact[NUM]
        return PRIME


n = int(input())
a = list(map(int, input().split()))

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')


Measured memory_bytes: 217184
integer n,m,a,ans
integer,allocatable,dimension(:)::x,dx(:)

read*,n, m
allocate(x(m),dx(m-1))
read*, (x(i), i=1,m)

if(n >= m)then
  print"(i0)",0
  stop
end if

call heapsort(m,x)

do i =1, m-1
  dx(i)=x(i+1) - x(i)
end do

call heapsort(m-1,dx)

ans = sum(dx)
if (n > 1)ans = ans - sum(dx(m-n+1:m-1))
print"(i0)",ans

contains

subroutine heapsort(n,array)
  implicit none
!ここの入力は状況に応じて変更すること
  integer,intent(in) :: n
  integer,intent(inout) :: array(1:n)
  integer::i,k,j,l
  integer:: t

  l=n/2+1
  k=n
  do while(k /= 1)
     if(l > 1)then
        l=l-1
        t=array(L)
     else
        t=array(k)
        array(k)=array(1)
        k=k-1
        if(k == 1) then
           array(1)=t
           exit
        endif
     endif
     i=l
     j=l+l
     do while(j<=k)
        if(j < k)then
           if(array(j) < array(j+1))j=j+1
        endif
        if (t < array(j))then
           array(i)=array(j)
           i=j
           j=j+j
        else
           j=k+1
        endif
     enddo
     array(i)=t
  enddo
  return
end subroutine heapsort
end

Measured memory_bytes: 1536
const input = require("fs").readFileSync("/dev/stdin", "utf8")

const N = parseInt(input, 10)

const dp = [...Array(N + 1).fill(null)].map((_, i) => i)

for (var i = 0; i < N; i++) {
    var j = 0
    var num = 0;
    while (i + num <= N) {
        j++
        num = Math.pow(6, j)
        if (i + num <= N) {
            dp[i + num] = Math.min(dp[i + num], dp[i] + 1)
        }
    }
    var j = 0
    var num = 0;
    while (i + num <= N) {
        j++
        num = Math.pow(9, j)
        if (i + num <= N) {
            dp[i + num] = Math.min(dp[i + num], dp[i] + 1)
        }
    }
}

console.log(dp[N])


Measured memory_bytes: 16936
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

class Tree:

    def __init__(self):
        self.root = None

    def insert(self, node):
        y = None
        x = self.root

        while x is not None:
            y = x
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        if y is None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def print_in_order(self, node):
        if node is None:
            return
        self.print_in_order(node.left)
        print(' ' + str(node.key), end='')
        self.print_in_order(node.right)

    def print_pre_order(self, node):
        if node is None:
            return
        print(' ' + str(node.key), end='')
        self.print_pre_order(node.left)
        self.print_pre_order(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_in_order(tree.root)
        print('')
        tree.print_pre_order(tree.root)
        print('')
    else:
        key = line[1]
        tree.insert(Node(int(key)))


Measured memory_bytes: 105168
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ITP1
{
    class ITP1_6_D
    {
        static void Main(string[] args)
        {
            int n, m;
            int[][] matrixA;
            int[] vectorB, vectorC;

            List<int> inputLine;

            inputLine = Console.ReadLine().Split().Select(int.Parse).ToList();
            n = inputLine[0];
            m = inputLine[1];

            matrixA = new int[n][];
            vectorB = new int[m];
            vectorC = new int[n];

            for (int i = 0; i < n; i++)
            {
                matrixA[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
            }

            for (int i = 0; i < m; i++)
            {
                vectorB[i] = (int.Parse(Console.ReadLine()));
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    vectorC[i] += (matrixA[i][j] * vectorB[j]);
                }
            }

            foreach (int number in vectorC)
            {
                Console.WriteLine(number);
            }
            Console.ReadLine();
        }
    }
}



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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main(){
    int h, w, k; 
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    
    // full search    
    ll ans = 0;
    rep(biti, (1<<h)){
        rep(bitj, (1<<w)){
            ll cnt = 0;
            rep(i, h){
                rep(j, w){
                    if(!(biti & (1<<i)) && !(bitj & (1<<j))){ 
                        if(s[i][j] == '#') cnt++;
                    }
                }
            }
            if(cnt == k) ans++;
            // cout << biti << " " << bitj << ": " << cnt << endl;
        }
    }
    
    cout << ans << endl;
    return;
}

int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}

Measured memory_bytes: 3644
m = mod = 10 ** 9 + 7

class Combination
  
  attr_accessor :n_max, :mod
  
  def initialize(mod)
    @mod = mod
    @n_max = 1
    @fact = [1, 1]
    @inv = [0,1]
    @factinv = [1, 1]
  end
  
  def f(t)
    (@n_max+1).upto(t) do |i|
      @fact.push( @fact[-1] * i % mod )
      @inv.push( -@inv[mod % i] * (mod / i) % mod )
      @factinv.push( @factinv[-1] * @inv[-1] % mod )
    end
    @n_max = t
  end
  
  def cmb(n,r)
    return 0 if r < 0 || n < r
    f(n) if n_max < n
    @fact[n] * (@factinv[r] * @factinv[n-r] % mod) % mod
  end
  
  def factorial(n)
    f(n) if n_max < n
    @fact[n]
  end
  
  def prm(n,k)
    f(n) if n_max < n
    @fact[n] * @factinv[n-k] % mod
  end
end


mod = 10 ** 9 + 7

n, k = gets.to_s.split.map{|i|i.to_i}
a    = gets.to_s.split.map{|i|i.to_i}.sort

inst = Combination.new(mod)

ans = 0 
(n-k+1).times do |i|
  t = inst.cmb( n-i-1, k-1)
  mi = a[i] * t % mod
  ma = a[n-(i+1)] * t % mod
  ans += (ma - mi)
  ans %= mod if ans < 0 || mod <= ans
end
 
puts ans

Measured memory_bytes: 13692
#include <bits/stdc++.h>
#define rep(k,i,n) for(long long i=k;i<n;++i)
using namespace std;
typedef long long ll;
int main(void){
    // Your code here!
    ll N;
    cin>>N;
    ll A[N],B[N],C[N];
    rep(0,i,N)cin>>A[i];
    rep(0,i,N)cin>>B[i];
    rep(0,i,N-1)cin>>C[i];
    ll ans=0;
    rep(0,i,N){
        ans+=B[A[i]-1];
        if(i!=0 && A[i]==A[i-1]+1){
            ans+=C[A[i]-2];
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
ll N,M;
const int MAX=3030;
ll dp[MAX+1][MAX+1];
struct Combinatorics {
  using int64 = long long;
  int64 mod;
  int64 fact[202020];
  int64 invfact[202020];
  Combinatorics(int64 mod):mod(mod) {
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < 202020; ++i) {
      fact[i] = fact[i-1]*i%mod;
      invfact[i] = minv(fact[i]);
    }
  }
  int64 mpow(int64 x, int64 n) const {
    int64 res = 1;
    while(n > 0) {
      if(n&1) res = res*x%mod;
      x = x*x%mod;
      n >>= 1;
    }
    return res;
  }
  int64 minv(int64 x) const {
    return mpow(x, mod-2);
  }
  int64 mfact(int64 x) const {
    return fact[x];
  }
  int64 C(int64 n, int64 r) const {
    if(r < 0 || n < r) return 0;
    return fact[n]*invfact[r]%mod*invfact[n-r]%mod;
  }
  int64 P(int64 n, int64 r) const {
    if(r < 0 || n < r) return 0;
    return fact[n]*invfact[n-r]%mod;
  }
};
void calcDP(){
  dp[0][0]=1;
  FOR(i,1,MAX){
    FOR(j,0,i+1){
      (dp[i][j]+=dp[i-1][j]*(j+1)%M)%=M;
      if(j)(dp[i][j]+=dp[i-1][j-1])%=M;
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>N>>M;
  calcDP();
  Combinatorics c1(M);
  Combinatorics c2(M-1);
  ll ans=0;
  FOR(k,0,N+1){
    ll cal=0;
    ll b=c1.mpow(2,N-k);
    ll p=1;
    FOR(x,0,k+1){
      cal=(cal+dp[k][x]*p)%M;
      p=p*b%M;
    }
    cal=(cal*c1.C(N,k))%M;
    cal=(cal*c1.mpow(2,c2.mpow(2,N-k)))%M;
    if(k&1){
      ans = (ans - cal + M) % M;
    }else{
      ans = (ans + cal) % M;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 76672
#include <iostream>
#include <algorithm>

using namespace std;

void show(int arr[], int n) {
	for (int i = 0; i < n - 1; i++)
		cout << arr[i] << " ";
	cout << arr[n - 1] << endl;
}

int selsctionSort(int arr[], int n) {
	int swCnt = 0, minj;
	for (int i = 0; i < n-1; i++) {
		minj = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[minj])
				minj = j;
		}
		if (arr[i] != arr[minj]) {
			swap(arr[i], arr[minj]);
			swCnt++;
		}
	}
	return swCnt;
}

int main() {
	int arr[100];
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int resCnt = selsctionSort(arr, n);
	show(arr, n);
	cout << resCnt << endl;

	return 0;
}

Measured memory_bytes: 1164
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Panasonic2020
{
    class A
    {
        static void Main(string[] args)
        {
            int[] sequence = new int[] { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
            string input1 = Console.ReadLine();
            int i = int.Parse(input1);

            Console.WriteLine(sequence[i-1]);
            // Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N, M;
int h[100010];
int main(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        h[i] = 1 << 30;
    }
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        h[a] = min(h[a], b);
    }
    int count = 0;
    int e = h[1];
    for(int i = 1; i <= N; i++){
        e = min(e, h[i]);
        if(e == i + 1) {
            count++;
            e = h[i + 1];
        }
    }
    cout << count << endl;
    return 0;
}

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

int main() {
  int n;
  string s;
  cin >> n >> s;
  string t = s.substr(0,s.size()/2);
  if (n % 2 == 0 && t == s.substr(s.size()/2, s.size())) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3616
#include<cstdio>
#include<cstring>
#define MAXN 2000
int sumEdge[MAXN+10][MAXN+10],sumEdgeRow[MAXN+10][MAXN+10],sumEdgeCol[MAXN+10][MAXN+10];
int sumPoint[MAXN+10][MAXN+10];
bool g[MAXN+10][MAXN+10];
int n,m,Q;
inline void SumInit() {
	for(int i=1; i<=n; i++)//Horizontal
		for(int j=1; j<=m; j++) {
			sumPoint[i][j]=sumPoint[i][j-1]+g[i][j];
			sumEdge[i][j]=sumEdge[i][j-1];
			if(g[i][j]&&g[i][j-1]) sumEdge[i][j]++;
			sumEdgeCol[i][j]=sumEdge[i][j];
		}
	for(int j=1; j<=m; j++)//Vertical
		for(int i=1; i<=n; i++){
			sumPoint[i][j]+=sumPoint[i-1][j];
			sumEdgeRow[j][i]=sumEdgeRow[j][i-1];
			if(g[i][j]&&g[i-1][j]) sumEdgeRow[j][i]++;
		}
	for(int i=1,tmp; i<=n; i++){//Link Vertical and Horizontal for Edge
		tmp=0;
		for(int j=1; j<=m; j++){
			if(g[i][j]&&g[i-1][j]) tmp++;
			sumEdge[i][j]+=sumEdge[i-1][j]+tmp;
		}
	}
}
inline int Query1D(int l,int r,int table[]) {
	return table[r]-table[l-1];
}
inline int Query2D(int x1,int y1,int x2,int y2,int table[][MAXN+10]) {
	return table[x2][y2]-table[x2][y1-1]-table[x1-1][y2]+table[x1-1][y1-1];
}
int main() {
	scanf("%d%d%d\n",&n,&m,&Q);
	char c;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			c=getchar();
			if(c=='1') g[i][j]=true;else g[i][j]=false;
		}
		c=getchar();
	}
	SumInit();
	int x1,y1,x2,y2;
	while(Q--){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		//printf("%d %d %d %d\n",Query2D(x1,y1,x2,y2,sumPoint),Query2D(x1+1,y1+1,x2,y2,sumEdge),Query1D(x1+1,x2,sumEdgeRow[y1]),Query1D(y1+1,y2,sumEdgeCol[x1]));
		printf("%d\n",Query2D(x1,y1,x2,y2,sumPoint)-Query2D(x1+1,y1+1,x2,y2,sumEdge)-Query1D(x1+1,x2,sumEdgeRow[y1])-Query1D(y1+1,y2,sumEdgeCol[x1]));
	}
	return 0;
}

Measured memory_bytes: 68736
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner();
		int n= sc.nextInt();
		int[] p = sc.nextIntArray(n);
		
		int max = 0;
		for(int i = 0; i < n; i++) {
			if(p[max] < p[i])
				max = i;
		}
		int sum = p[max] /2;
		p[max] = 0;
		for(int i : p)
			sum += i;
		System.out.println(sum);
	}
}

class Scanner {
	private static final int SPACE = (int)' ';
	private static final int LINE_END_0 = 13;
	private static final int LINE_END_1 = 10;
	private static final int BEFORE = -1;
	private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	public String next(){
		StringBuilder sb = new StringBuilder();
		
		int length = BEFORE;
		readLoop: while(true) {
			try {
				int value = br.read();
				switch(value) {
				case LINE_END_1:
					if(length == BEFORE)
						break;
					
					if((int)sb.charAt(length) == LINE_END_0)
						sb.deleteCharAt(length);
				case SPACE:
					break readLoop;
				}
				sb.append((char)value);
				length++;

			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		return sb.toString();
	}
	
	public String[] nextArray(int length) {
		String[] array = new String[length];
		for(int i = 0; i < length; i++)
			array[i] = next();
		return array;
	}
	
	public double nextDouble() {
		return Double.parseDouble(next());
	}
	
	public double[] nextDoubleArray(int length) {
		double[] array = new double[length];
		for(int i = 0; i < length; i++)
			array[i] = nextDouble();
		return array;
	}
	
	public int nextInt() {
		return Integer.parseInt(next());
	}
	
	public int[] nextIntArray(int length) {
		int[] array = new int[length];
		for(int i = 0; i < length; i++)
			array[i] = nextInt();
		return array;
	}
	
	public long nextLong() {
		return Long.parseLong(next());
	}
	
	public long[] nextLongArray(int length) {
		long[] array = new long[length];
		for(int i = 0; i < length; i++)
			array[i] = nextLong();
		return array;
	}
	
	public boolean ready() {
		try {
			return br.ready();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return false;
	}
}


Measured memory_bytes: 21076
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <random>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
ll mod = 1e9 + 7;

int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cout.setf(ios::fixed); 
	cout.precision(20);

	int n, k;
	cin >> n >> k;
	long long ans = 0;
	if (k == 0) {
		ans = (long long)n*n;
	}
	else {
		for (int i = k; i <= n; i++) {

			ans += (long long)(i - k)*(n / i);
			if (n%i >= k) {
				ans += n % i - k + 1;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
	int a,b,c;
	 scanf("%d", &a);
	 scanf("%d", &b);
     scanf("%d", &c);
  
  
	if(a+b+c<=21)
     printf("win\n");
    else
     printf("bust\n");
     return(0);
}

Measured memory_bytes: 128
#include <iostream>
#include<iomanip>
#include<math.h>
using namespace std;
int main(void){
    long n;
    cin>>n;
    long a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long x = a[0];
    long y = a[0];
    long z = 0;
    for(int j = 0; j<n; j++){
        x = min(x,a[j]);
        y = max(y,a[j]);
        z = z+a[j];
    }
    cout<<x<<" "<<y<<" "<<z<<endl;
    
    return 0;
}



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

using namespace std;

void Solve(){
    int n, k;
    cin>>n>>k;
    vector<bool> v(n + 1);
    for(int i = 0; i < k; i++){
        int t;
        cin>>t;
        while(t--){
            int x;
            cin>>x;
            v[x] = true;
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        if(!v[i]) res++;
    }
    cout<<res<<endl;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    //cin>>T;
    while(T--){
        Solve();
    }
}

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

const ll MOD = 998244353;

int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> seq;
    vector<bool> seen(m);
    ll val = x;
    vector<int> cycle;
    while (!seen[x]) {
        seen[x] = true;
        seq.push_back(x);
        //cout << "x: " << x << endl;
        x *= x;
        x %= m;
    }
    while (seq.back() != x) {
        cycle.push_back(seq.back());
        seq.pop_back();
    }
    cycle.push_back(x);
    seq.pop_back();
    reverse(cycle.begin(), cycle.end());
    ll ans = 0;
    for (ll j = 0; j < min((ll)(seq.size()), n); ++j) {
        ans += seq[j];
    }
    n -= (ll) seq.size();
    if (n < 0) {
        cout << ans << endl;
        return 0;
    }
    vector<ll> pref(cycle.size());
    for (int i = 0; i < cycle.size(); ++i) {
        pref[i] = cycle[i];
        if (i) pref[i] += pref[i - 1];
    }
    ans += (n / ((ll) cycle.size())) * 1ll * pref.back();
    if (n % ((ll) cycle.size()) != 0) ans += pref[n % ((ll) cycle.size()) - 1];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4428
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ll long long
#define ld long double
int main(){
  string s,t;
  cin>>s>>t;
  ll count=0;
  rep(i,s.size()){
    if(s[i]!=t[i]) count++;
  }
  cout<<count;
return 0;
}

Measured memory_bytes: 3896
import java.util.Scanner;

public class Main {
	public static void main(String arg[]) {

		Scanner sc = new Scanner(System.in);

		// N面のサイコロ
		int N = sc.nextInt();
		
		// 点数
		int K = sc.nextInt();

		double anser = 0;

		// サイコロの目数分回す
		for (int i = 1; i <= N; i++) {

			// サイコロの目
			int a = i;
			// コインを振った回数
			int c = 0;

			// K-1点を超えるまで繰り返しコインを振る
			while(true) {
				if (!(a > K-1)) {
					a = a * 2;
					c++;
				} else {
					break;
				}
			}

			// 確率を求める式
			double b = Math.pow(0.5, c);
			anser +=  b/N;

		}

		// 出力
		System.out.print(anser);

	}
}


Measured memory_bytes: 23124
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
    static ArrayList<Integer>[]adj;
    static void bfs(int s,int []d){
        Arrays.fill(d,-1);
        d[s]=0;
        Queue<Integer>q= new LinkedList<>();
        ((LinkedList<Integer>) q).add(s);
        while (!q.isEmpty()){
            int u = q.poll();
            for (int v:adj[u]){
                if (d[v]==-1){
                    d[v]=1+d[u];
                    ((LinkedList<Integer>) q).add(v);
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[][]dis = new int[n][n];
        adj= new ArrayList[n];
        for (int i =0;i<n;i++)adj[i]=new ArrayList<>();
        int x= sc.nextInt()-1;
        int y= sc.nextInt()-1;
        adj[x].add(y);
        adj[y].add(x);
        for (int i =0;i<n-1;i++){
            adj[i].add(i+1);
            adj[i+1].add(i);
        }
        int[]ans= new int[n];
        for (int i =0;i<n;i++){
            bfs(i,dis[i]);
        }
        for (int i =0;i<n;i++){
            for (int j =i+1;j<n;j++){
                ans[dis[i][j]]++;
            }
        }
        for (int i =1;i<n;i++)
            pw.println(ans[i]);
        pw.flush();
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }

}

Measured memory_bytes: 103944
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	cin>>n>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]+n>'Z')s[i]='A'+(n-'Z'+s[i])-1;
		else s[i]+=n;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
import numpy as np

N,M=(int(x) for x in input().split())
A=list(map(int, input().split()))
A=np.array(A)
B=A[1:]-A[:-1]
b=max(B)
c=A[-1]-A[0]
if c > N/2:
    d=int(N-c)
else:
    d=c
e=max(b,d)
f=N-e

print(f)


Measured memory_bytes: 34160
from collections import Counter

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

MOD = 1000000007

# 2 WA
def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)
    z = 0
    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      if g != 0:
        a = a//g
        b = b//g
        if a*b<0: a = -abs(a)
        elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if a==b==0: z+=1
        elif b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],  d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0], d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0], d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print((ans-1+z)%MOD)

if __name__ == '__main__':
    main()


Measured memory_bytes: 46816
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	tests := make([]string, n)
	i := 0
	for i < n {
		fmt.Scanf("%s", &tests[i])
		i++
	}

	m := map[string]int{"AC": 0, "WA": 0, "TLE": 0, "RE": 0}
	for _, s := range tests {
		m[s]++
	}
	fmt.Printf("AC x %d\n", m["AC"])
	fmt.Printf("WA x %d\n", m["WA"])
	fmt.Printf("TLE x %d\n", m["TLE"])
	fmt.Printf("RE x %d", m["RE"])
}


Measured memory_bytes: 6540
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    long long a,b,c,x,y,d;
    cin>>a>>b>>c>>x>>y;
    if(a+b>=c*2){
        if(x>=y){
            d=min(c*2*x,c*2*y+a*(x-y));
        }else{
            d=min(c*2*y,c*2*x+b*(y-x));
        }
    }else{
        d=a*x+b*y;
    }
    cout<<d<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  vector<ll> A(N);
  ll as = 0;
  ll mod = 1e9+7;
  REP(i, N){
    cin >> A[i];
    as += A[i];
    as %= mod;
  }
  ll ans = 0;
  REP(i, N-1){
    as = as - A[i];
    if(as < 0){
      as += mod;
    }
    ans += A[i]*(as)%mod;
    ans %= mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 4744
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,p,a[N],b[N],c[N];
main()
{
	cin>>n>>m>>p;
	for(int i=0;i<m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		a[i]--,b[i]--;
		c[i]-=p;
	}
	vector<long>d(n,-1e18);
	d[0]=0;
	for(int i=0;i<m;i++)
		for(int j=0;j<m;j++)
			d[b[j]]=max(d[b[j]],d[a[j]]+c[j]);
	long ans=d[n-1];
	for(int i=0;i<m;i++)for(int j=0;j<m;j++)
		d[b[j]]=max(d[b[j]],d[a[j]]+c[j]);
	cout<<(ans<d[n-1]?-1:ans<0?0:ans)<<endl;
	return 0; 
}


Measured memory_bytes: 384
import itertools
from collections import Counter


n = int(input())
v = list(map(int, input().split()))
ev_cnt = Counter(v[::2])
od_cnt = Counter(v[1::2])
ev_cnt[-1] = 0
od_cnt[-2] = 0
ev = ev_cnt.most_common(2)
od = od_cnt.most_common(2)
ans = n
for (k1, v1), (k2, v2) in itertools.product(ev, od):
    if k1 == k2:
        continue
    x = (n - v1 - v2)
    ans = min(ans, x)
print(ans)


Measured memory_bytes: 18520
from fractions import gcd
A, B = map(int, input().split())


def BIG_SMALL(A, B):
    if A % B == 0:
        print(A)
    else:
        print(A*B//gcd(A,B))


if A > B:
    BIG_SMALL(A, B)
elif A < B:
    BIG_SMALL(B, A)
else:
    print(A)


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

int ban[24][24];
int W,H;
int p[2];
int cnt;
int ans;
int D[4] = {1, 0, -1, 0};

void dfs() {
	if (cnt > 9) return;
	cnt += 1;
	for (int i = 0; i < 4; i++) {
		int dx = D[i];
		int dy = D[3 - i];
		int x = p[0];
		int y = p[1];
		if (ban[y + dy][x + dx] == 1 or ban[y + dy][x + dx] == -1) continue;
		for (int j = 1; j < 21; j++) {
			if (ban[y + dy * j][x + dx * j] == 3) {
				ans = min(ans, cnt);
				cnt --;
				return;
			}
			if (ban[y + dy * j][x + dx * j] == 0 and ban[y + dy * (j + 1)][x + dx * (j + 1)] == 1) {
				p[0] = x + dx * j;
				p[1] = y + dy * j;
				ban[y + dy * (j + 1)][x + dx * (j + 1)] = 0;
				dfs();
				p[0] = x;
				p[1] = y;
				ban[y + dy * (j + 1)][x + dx * (j + 1)] = 1;
				break;
			}
			if (ban[y + dy * j][x + dx * j] == -1) break;
		}
	}
	cnt -= 1;
	return;
}

int main() {
	cin >> W >> H;
	while(W) {
		p[0] = 0;
		p[1] = 0;
		ans = 100;
		cnt = 0;
		for (int y = 0; y < 22; y++) {
			for (int x = 0; x < 22; x++) {
				if (x >= 1 and x <= W and y >= 1 and y <= H) {
					cin >> ban[y][x];
					if (ban[y][x] == 2) {
						p[0] = x; p[1] = y;
						ban[y][x] = 0;
					}
				} else {
					ban[y][x] = -1;
				}
			}
		}
		dfs();
		if (ans <= 10) cout << ans << endl;
		else cout << -1 << endl;
		cin >> W >> H;
	}
}



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

int main() {
    int N;
    while (cin >> N, N) {
        int count = 0;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int sum = (2 * i + j) * (j + 1) / 2;
                if (sum == N) count++;
                if (sum >= N) break;
            }
        }

        cout << count << endl;
    }

    return 0;
}



Measured memory_bytes: 2992
#include <stdio.h>
#include <ctype.h>
#include <string.h>

int main(void) {
    int i,alpha[26]={0};
    char string[1201];
    while (fgets(string,sizeof(string),stdin)!=NULL) {
        for (i=0; i<strlen(string); i++) {
            if (isalpha(string[i])) {
                if (islower(string[i])) {
                    alpha[string[i]-'a']++;
                } else {
                    alpha[string[i]-'A']++;
                }
            }
        }
    }
    for (i=0; i<26; i++) printf("%c : %d\n",i+'a',alpha[i]);
    return 0;
}

Measured memory_bytes: 524
#include<iostream>
using namespace std;
 
int main(){
  int N;
  int W;
  cin >> N >> W;
 
  int w[100];
  int v[100];
  for(int i=0; i<N; i++){
    cin >> v[i] >> w[i];
  }
 
 
  int DP[N+1][W+1];
 
  for(int j=0; j<=W; j++)
    DP[0][j] = 0;
 
  for(int i=1; i<=N; i++)
    for(int j=0; j<=W; j++)
      if(j<w[i-1]){
        DP[i][j] = DP[i-1][j];
      }else{
        if(DP[i-1][j]>DP[i-1][j-w[i-1]]+v[i-1])
          DP[i][j] = DP[i-1][j];
        else
          DP[i][j] = DP[i-1][j-w[i-1]]+v[i-1];
        }
 
 
 
  cout << DP[N][W] << endl;
 
  return 0;
}


Measured memory_bytes: 7028
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin>>s>>t;
  int index=0;
  bool flg=false;
  for(int i=0;i<s.size();i++){
    if(s[i]==t[0]||s[i]=='?'){
      for(int j=0;j<t.size();j++){
        if(s[i+j]!='?'&&s[i+j]!=t[j]){
          break;
        }
        if(j==t.size()-1){
          flg=true;
          index=i;
        }
      }
    }
  }
  if(!flg){
    cout<<"UNRESTORABLE"<<endl;
    return 0;
  }
  for(int i=0;i<s.size();i++){
    if(s[i]!='?'){
      cout<<s[i];
      continue;
    }
    if(i<index){
      cout<<'a';
    }else if(index<=i&&i<index+t.size()){
      cout<<t[i-index];
    }else{
      cout<<'a';
    }
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3616
#include<stdio.h>
int main(){
    int i,j,n;
    for( i = 0 ; ; i += 1 ){
        int sum = 0,y[1001] = {};
        char x[1001] = {};
        for( j = 0 ; ; j += 1 ){
            scanf("%c",&x[j]);
            if( x[j] == '\n' ){
                n = j;
                break;
            }
            else{
                y[j] = x[j] - '0';
            }
        }
        if( x[0] == '0' ){
            break;
        }
        else{
            for( j = 0 ; j <= n ; j += 1){
                sum = sum + y[j];
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
#define SIZE 100005
vector< int > graph[SIZE];
vector< int > ans;
vector< int > vis(SIZE,0);
vector< int > low(SIZE,0);
vector< int > tin(SIZE , 0);

int timer;
void dfs(int u , int p = -1){
	vis[u] = true;
	tin[u] = low[u] = timer++;
	int children = 0;
	for(auto it : graph[u]){
			if(it == p) continue;
			if(vis[it] == 1)
				low[u] = min(low[u] , tin[it]);
			else{
				dfs(it , u);
				low[u] = min(low[u] , low[it]);
				if(p != -1 && low[it] >= tin[u])
					ans.push_back(u);
				children++;
			}
	}
	if(p == -1 && children > 1)
		ans.push_back(u);
}
int main(){
	dhoom;
	int n , m;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++){
		int x , y ;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	for(int i = 0 ; i < n ; i++){
			if(!vis[i])
				dfs(i);
	}
	sort(ans.begin() , ans.end());
	ans.erase(unique(ans.begin() , ans.end()), ans.end());
	for(int i = 0 ; i < (int) ans.size() ; i++)	
		cout << ans[i] << endl;
    return 0;
}




Measured memory_bytes: 7536
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define pb pop_back

struct ant
{
	int pos, ind;
	bool dir;
};

int n, R[300003], lef[2];
LL m, t, asd;
//char C[5];
vector<ant> V[2];

bool cmp(ant a, ant b)
{
	return a.pos<b.pos;
}

int main()
{
	//ios_base::sync_with_stdio(0);
	scanf("%d%lld%lld", &n, &m, &t);
	LL tt=t%m;
	t*=2;
	asd=t/m;
	t%=m;
	for(int i=0; i<n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		a++;
		ant x;
		x.pos=a;
		x.ind=i;
		if(b == 1)
		{
			x.dir=1;
			lef[1]++;
		}
		else
		{
			x.dir=0;
			lef[0]++;
		}
		V[0].PB(x);
		x.pos=m-a+1;
		x.dir=!x.dir;
		V[1].PB(x);
	}
	for(int ind=0; ind<2; ind++)
	{
		sort(V[ind].begin(), V[ind].end(), cmp);
		//printf("%d:\n", ind);
		for(int i=0; i<n; i++)
		{
		//	printf("%d %d %d\n", V[ind][i].pos, V[ind][i].ind, V[ind][i].dir);
			V[ind].PB(V[ind][i]);
			V[ind][n+i].pos+=m;
		}
		int tmp=0, left=0;
		for(int i=0; i<n; i++)
		{
			while(tmp<2*n && V[ind][tmp].pos<=V[ind][i].pos+t)
			{
				if(!V[ind][tmp].dir)
					left++;
				tmp++;
			}
		//	printf("%d %d ind=%d dir=%d tmp=%d left=%d\n", ind, i, V[ind][i].ind, V[ind][i].dir, tmp, left);
			if(V[ind][i].dir)
			{
				LL left2=(left+asd*lef[ind])%n;
				R[V[ind][i+left2].ind]=V[ind][i].pos+tt;
				//printf("%d %d %d\n", i+left, V[ind][i+left].ind, V[ind][i].pos+t);
				while(R[V[ind][i+left2].ind]>m)
					R[V[ind][i+left2].ind]-=m;
				if(ind==1)
					R[V[ind][i+left2].ind]=m-R[V[ind][i+left2].ind]+1;
			}
			else
				left--;
		}
	}
	for(int i=0; i<n; i++)
		printf("%d\n", R[i] - 1);
	//printf("\n");
	return 0;
}

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

int main() {
  
  string s, t, u;
  int a, b;
  
  cin >> s >> t >> a >> b >> u;
  
  if (u == s) {
    a -= 1;
  }
  else {
    b -= 1;
  }
  
  cout << a << " " << b << endl;
  

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

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

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

    ll x[N+10];
    ll ans = 0;
    rep(i,N)
    {
        cin >> x[i];
        ans = gcd(ans, abs(x[i]-X));
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <cstdio>

int main()
{
    int k;
    scanf("%d", &k);
    for (int i = 1, p = 7; i < 9 * k; i ++ , p = (10 * p + 7) % k)
        if (p % k == 0)
        {
            printf("%d\n", i);
            return 0;
        }
    puts("-1");
    return 0;
}

Measured memory_bytes: 1676
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
ans = 0
n, k = MAP()
dd = defaultdict(int)
for i in range(k):
    d = INT()
    temp = LIST()
    for el in temp:
        dd[el] = 100
for i in range(n):
    if(dd[i+1]==0):
        ans+=1
print(ans)

Measured memory_bytes: 68876
//
//  main.cpp
//  atcoder-deque
//
//  Created by r on 6/1/19.
//  Copyright © 2019 r. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

long long N;
long long a[3010];
long long dp[3010][3010][2];

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (long long i = 0; i<N; i++) {
        cin >> a[i];
    }
    for (long long i = N-1; i>=0; i--) {
        for (long long j = i; j<N; j++) {
            dp[i][j][0] = max(a[i]+dp[i+1][j][1], a[j]+dp[i][j-1][1]);
            dp[i][j][1] = min(dp[i+1][j][0]-a[i], dp[i][j-1][0]-a[j]);
        }
    }
    cout << dp[0][N-1][0] << endl;
    return 0;
}





Measured memory_bytes: 141568
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	private static Map<Character, Character> firstRule = new HashMap<Character, Character>();
	private static Map<Character, Character> nextRule = new HashMap<Character, Character>();
	static {
		firstRule.put('1', '.');
		firstRule.put('2', 'a');
		firstRule.put('3', 'd');
		firstRule.put('4', 'g');
		firstRule.put('5', 'j');
		firstRule.put('6', 'm');
		firstRule.put('7', 'p');
		firstRule.put('8', 't');
		firstRule.put('9', 'w');

		// 1
		nextRule.put('.', ',');
		nextRule.put(',', '!');
		nextRule.put('!', '?');
		nextRule.put('?', ' ');
		nextRule.put(' ', '.');

		// 2
		nextRule.put('a', 'b');
		nextRule.put('b', 'c');
		nextRule.put('c', 'a');

		// 3
		nextRule.put('d', 'e');
		nextRule.put('e', 'f');
		nextRule.put('f', 'd');

		// 4
		nextRule.put('g', 'h');
		nextRule.put('h', 'i');
		nextRule.put('i', 'g');

		// 5
		nextRule.put('j', 'k');
		nextRule.put('k', 'l');
		nextRule.put('l', 'j');

		// 6
		nextRule.put('m', 'n');
		nextRule.put('n', 'o');
		nextRule.put('o', 'm');

		// 7
		nextRule.put('p', 'q');
		nextRule.put('q', 'r');
		nextRule.put('r', 's');
		nextRule.put('s', 'p');

		// 8
		nextRule.put('t', 'u');
		nextRule.put('u', 'v');
		nextRule.put('v', 't');

		// 9
		nextRule.put('w', 'x');
		nextRule.put('x', 'y');
		nextRule.put('y', 'z');
		nextRule.put('z', 'w');
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = Integer.parseInt(s.next());
		for (int i = 0; i < N; i++) {
			String in = s.next();
			System.out.println(solve(in));
		}
	}

	private static String solve(String in) {
		StringBuilder buf = new StringBuilder();
		Character current = null;
		for (char ch : in.toCharArray()) {
			if (ch == '0' && current != null) {
				buf.append(current);
				current = null;
				continue;
			}
			current = nextChar(ch, current);
		}
		return buf.toString();
	}

	private static Character nextChar(char in, Character current) {
		return (current == null) ? firstRule.get(in) : nextRule.get(current);
	}

}

Measured memory_bytes: 22164
N = int(input())
a = list(map(int, input().split()))

A = 0
B = 0
while True:
  m_a = max(a)
  A += m_a
  a.remove(m_a)
  if len(a) == 0: break
  
  m_b = max(a)
  B += m_b
  a.remove(m_b)
  if len(a) == 0: break

print(A-B)

Measured memory_bytes: 9076
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
 
using namespace std;
typedef long long int lli;
//const int MAX=;
 
int main(){
	int N;
	cin>>N;
	string A,B,C;
	cin>>A>>B>>C;
	int ans=0;
	rep(i,N){
		if(A[i]==B[i]&&B[i]==C[i])ans+=0;
		else if(A[i]==B[i])ans+=1;
		else if(B[i]==C[i])ans+=1;
		else if(C[i]==A[i])ans+=1;
		else ans+=2;
	}
	cout<<ans;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}

const int MOD = 1e9 + 7;

int mul(int a, int b) {
    return (ll) a * b % MOD;
}

int add(int a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += MOD;
    return a;
}

int binpow(int a, int n) {
    if (!n) return 1;
    if (n & 1) {
        return mul(a, binpow(a, n - 1));
    }
    else {
        return binpow(mul(a, a), n / 2);
    }
}

int inv(int a) {
    return binpow(a, MOD - 2);
}

const int MAXN = 2e6 + 10;

int fact[MAXN], rfact[MAXN];

void build() {
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = mul(fact[i - 1], i);
        rfact[i] = inv(fact[i]);
    }
}

int c_n_k(int n, int k) {
    if (min(n, k) <= 0) return 1;
    return mul(fact[n], mul(rfact[k], rfact[n - k]));
}

int r1, r2, c1, c2;

void read() {
    cin >> r1 >> c1 >> r2 >> c2;
} 

int get(int r, int c) {
    return c_n_k(r + c + 2, c + 1) - 1;
}

int ans;

void run() {
    ans = 0;
    ans = add(ans, get(r2, c2));
    ans = sub(ans, get(r1 - 1, c2));
    ans = sub(ans, get(r2, c1 - 1));
    ans = add(ans, get(r1 - 1, c1 - 1));
}

void write() {
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    build();
    read();
    run();
    write();
    return 0;
}

Measured memory_bytes: 15872
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int64_t> vec(n);
    for (auto &num : vec) {
        cin >> num;
    }
    sort(vec.begin(), vec.end(), greater<int>());

    vector<pair<int64_t, int64_t>> ops(m);
    for (auto &op : ops) {
        cin >> op.second >> op.first;
    }
    sort(ops.begin(), ops.end(), greater<pair<int64_t, int64_t>>());

    int64_t sum = 0;
    for (const auto &op : ops) {
        for (auto i = 0; i < op.second && !vec.empty() && op.first > vec.back(); i += 1) {
            sum += op.first;
            vec.pop_back();
        }
    }
    for (const auto &num : vec) {
        sum += num;
    }

    cout << sum << "\n";
    return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main() {
	int n;
	string s;

	cin >> n >> s;

	vector<int> cnt_vcb(n+1);
	vector<int> cnt_vcw(n+1);

	int cnt_b = 0, cnt_w = 0; 
	long mini = 200000;

	REP(i, n) {

		if (s[i] == '.') cnt_w++;
		else 			 cnt_b++;

		cnt_vcw[i+1] = cnt_w;	cnt_vcb[i+1] = cnt_b;
	}
		
	REP(i, n+1) {
		long change = cnt_vcb[i]+cnt_w-cnt_vcw[i];
		mini = min(mini, change);
	}

	cout << mini << endl;

}

Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
typedef long long ll;

int main() {
  int k,n;
  cin >> k >> n;
  vector<int> a(n);
  rep(i,n){
    cin >> a.at(i);
  }
  int m = 0 ;
  rep(i,n-1){
    m = max(m,a.at(i+1)-a.at(i));
  }
  m= max(m,k-a.at(n-1)+a.at(0)); 
  cout << k-m << endl;
}



Measured memory_bytes: 1024
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
ans=INF
1.upto(N-1) do|i|
  i_=i.to_s.split("").map(&:to_i)
  n=(N-i).to_s.split("").map(&:to_i)
  v=i_.inject(:+)+n.inject(:+)
  ans=min(ans,v)
end
puts ans

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

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++){
    cin >> s[i];
  }
  int m;
  cin >> m;
  vector<string> t(m);
  for (int i = 0; i < m; i++){
    cin >> t[i];
  }
  int an = 0;
  for (int i = 0; i < n; i++){
    int ans = 0;
    for (int j = 0; j < n; j++){
      if (s[i] == s[j]) ans++;
    }
    for (int j = 0; j < m; j++){
      if (s[i] == t[j]) ans--;
    }
    an = max(ans, an);
  }
  cout << an << endl;
}


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

int main() {
    int x,y;
    bool check = false;
    cin >> x >> y;
    rep(i,x+1) {
        if (y == (((x-i)*2) + (i*4))) {
            check = true;
            break;
        }
    }
    if (check) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
from scipy.sparse import*
(n,m),*d=[map(int,o.split())for o in open(0)]
*w,a=zip(*[(i,j+n-1,1)for i,(_,*d)in enumerate(d)for j in d])
print("YNEOS"[1in csgraph.connected_components(csr_matrix(((a,w)),[n+m]*2))[1][:n]::2])

Measured memory_bytes: 61084