akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var xy = Console.ReadLine().Split(' ').Select(num => int.Parse(num)).ToArray();
            if (xy[1] % 2 == 1) { Console.WriteLine("No"); return; };

            var sa = (4 * xy[0] - xy[1]) / 2;
            Console.WriteLine(sa <= xy[0] && sa >= 0 ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 28292
/*
                _____________   ______________       __
               / _________  /\ /_____   _____/\     / /\
              / /\       / /  \\    /  /\    \ \   / /  \
             / /  \_____/ /   / \__/  /  \____\/  / /   /
            / /   /    / /   /    /  /   /       / /   /
           / /   /    / /   /    /  /   /       / /   /
          / /   /    / /   /    /  /   /       / /   /
         / /___/____/ /   /    /  /   /       / /___/________
        /____________/   /    /__/   /       /______________/\
        \            \  /     \  \  /        \              \ \
         \____________\/       \__\/          \______________\/
           ___       ___               ___    ___________
          /  /\     /  /\             /  /\  /_______   /\
         /  /__\___/  /  \           /  /  \ \      /  /  \
        /____    ____/   /          /  /   /  \____/  /   /
        \   /   /\   \  /          /  /   /       /  /   /
         \_/   /  \___\/ ___      /  /   /       /  /   /
          /   /   /     /  /\    /  /   /       /  /   /
         /   /   /     /  /__\__/  /   /       /  /___/____
        /___/   /     /___________/   /       /___________/\
        \   \  /      \           \  /        \           \ \
         \___\/        \___________\/          \___________\/

          A FAN OF FIZZYDAVID

*/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#include <utility>
#include <functional>
using namespace std;
//orz jzm
#define ll long long
#define ull unsigned ll
#define orz int
#define yjz main
#define fizzydavid return
#define ak 0
#define la ;
#define plusonesecond {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define minusonesecond exit(0)
const double EPS = 1e-8;
const ll PR = 19260817;
const ll inv2 = 500000004;
const ll inv3 = 333333336;
const int N = 100005;
int n, a[N];
orz yjz() {
	scanf("%d", &n);for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	int c=0;
	for(int i=1; i<=n; i++) {
		if(a[i]!=i) continue;
		int j=i+1;
		while(j<=n&&a[j]==j) j++;
		c+=((j-i+1)/2);
		i=j-1;
	}
	printf("%d\n", c);
	fizzydavid ak la
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void){
    int loop1,loop2;
    int n;
    scanf("%d",&n);
    //素因数分解
    if(n==1){
        printf("1\n");
        return 0;
    }
    int enz[1001]={0};
    for(loop1=2;loop1<=n;loop1++){
        int temp=loop1;
        int a=2;
        while(temp>=a*a){
            if(temp%a==0){
                enz[a]++;
                temp=temp/a;
            }else{
                a++;
            }
        }
        enz[temp]++;
    }
    long long int ans=1;
    for(loop1=2;loop1<1000;loop1++){
        if(enz[loop1]!=0){
            ans*=(enz[loop1]+1);
            ans%=1000000007;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define pb push_back
#define mp make_pair



int main() {
	
	int n;
	cin >> n;
	int a[1+n];
	int b[1+n];
	int c[n];
	
	rep1(i,n) cin >> a[i];
	rep1(i,n) cin >> b[i];
	rep1(i,n-1) cin >> c[i];
	
	int sum = b[a[1]];
	int prev = a[1];
	for(int i =2;i<=n;i++){
		
		sum += b[a[i]];
		if ( prev +1 == a[i]) sum+=c[prev];
		prev = a[i];
	}
	
	cout << sum <<endl;
	
	
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

const lld N = 200043;
const lld MOD = 1000000007;

lld add(lld x, lld y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

lld mul(lld x, lld y)
{
    return (x * 1ll * y) % MOD;
}

lld binpow(lld x, lld y)
{
    lld z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

lld inv(lld x)
{
    return binpow(x, MOD - 2);
}

lld divide(lld x, lld y)
{
    return mul(x, inv(y));
}

// Combinations

/*
lld fact[N];

void precalc()
{
    fact[0] = 1;
    for(lld i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

lld C(lld n, lld k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}
*/
vector<lld>v[100005];
lld n,m;
lld indegree[100005];
lld dist[100005];
lld visited[100005];
lld dfs(lld a)
{
    visited[a]=1;
    for(lld b :v[a])
    {
        dist[b]=max(dist[b],dist[a]+1);
        //cout<<a<<" "<<b<<" "<<dist[b]<<endl;
        indegree[b]--;
        if(indegree[b]==0)
            dfs(b);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t,i,j;
    t=1;
    while(t--)
    {
        cin>>n>>m;
        for(i=0;i<m;i++)
        {
            lld a,b;
            cin>>a>>b;
            v[a].push_back(b);
            indegree[b]++;
        }
        for(i=1;i<=n;i++)
        {
            v[0].push_back(i);
            indegree[i]++;

        }
        for(i=0;i<=n;i++)
        {
            if(visited[i]==0 && indegree[i]==0)
                dfs(i);
        }
        lld ans=0;
        for(i=0;i<=n;i++)
            ans=max(ans,dist[i]);
        cout<<ans-1<<endl;
    }
}



Measured memory_bytes: 9844
n=int(input())
word=[]

for i in range(n):
    a=int(input())
    l=[list(map(int, input().split())) for j in range(a)]
    word.append(l)

ans=0

for i in range(2**n):
    flag=0
    cnt=0
    for j in range(n):
        if((i>>j)&1)==1 and flag==0:#正直者の言うことは矛盾が生じていない場合調べる
            for k in range(len(word[j])):
                if ((i>>word[j][k][0]-1)&1) != word[j][k][1]:
                    flag=1#正直者が嘘を言う矛盾が生じた
                    break
    
    if flag==0:
        cnt=bin(i).count("1")
        ans=max(ans, cnt)

print(ans)

Measured memory_bytes: 43880
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#define rep(i, m, n) for(int i = m;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define ll long long
#define ull unsigned long long
#define push(a) push_back(a)
#define pop(a) pop_back(a)
#define debug(x) cout<<#x<<": "<<x<<endl
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
  int x;
  cin >> x;
  if(x < 1200){
    cout << "ABC" << endl;
  }else{
    cout << "ARC" << endl;
  }
}


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

using namespace std;

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

int in() { int x; scanf("%d", &x); return x; }
template<typename T> void pv(T a, T b) { for (T i = a; i < b; i++) cout << *i << ' '; cout << endl; }
template<typename T, typename U> void chmin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> void chmax(T &x, U y) { if (x < y) x = y; }

using ll = long long;

int N;
int a[200010];

int main() {
  N = in();
  REP(i,N) a[i] = in();

  ll sum = 0L, t = 0L, res = (1L<<61);
  REP(i,N) sum += a[i];
  REP(i,N-1) {
    t += a[i];
    ll x = sum - t, y = t;
    ll diff = x - y;
    chmin(res, max(diff, -diff));
  }
  cout << res << endl;

  return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    sort(A.begin(), A.end(), greater<long long>());

    if (N % 2 == 0) {
        long long res = 0;
        for (int i = 0; i < N/2 - 1; ++i) res += A[i] * 2;
        res += A[N/2 - 1];
        res -= A[N/2];
        for (int i = N/2 + 1; i < N; ++i) res -= A[i] * 2;
        cout << res << endl;
    }
    else {
        long long res1 = 0;
        for (int i = 0; i < N/2 - 1; ++i) res1 += A[i] * 2;
        res1 += A[N/2 - 1] + A[N/2];
        for (int i = N/2 + 1; i < N; ++i) res1 -= A[i] * 2;
        
        long long res2 = 0;
        for (int i = 0; i < N/2; ++i) res2 += A[i] * 2;
        res2 -= A[N/2] + A[N/2 + 1];
        for (int i = N/2 + 2; i < N; ++i) res2 -= A[i] * 2;
        cout << max(res1, res2) << endl;
    }
}












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

void dfs(int& time,
    int start,
    const vector<vector<int>>& graph,
    vector<int>& arraialTimes,
    vector<int>& leftTimes,
    vector<bool>& checkList)
{
    stack<int> stack;
    stack.push(start);
    checkList[start] = true;
    arraialTimes[start] = ++time;
 
    while (!stack.empty())
    {
        int v = stack.top();
        int vSize = 0;
        for (int w : graph[v]) {
            if (!checkList[w]) {
                ++vSize;
                stack.push(w);
                checkList[w] = true;
                arraialTimes[w] = ++time;
                break;
            }
        }
        if (vSize == 0) {
            stack.pop();
            leftTimes[v] = ++time;
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    vector<bool> checkList(n);
    vector<int> arrivalTimes(n);
    vector<int> leftTimes(n);


    graph.reserve(n);
    for (auto& g : graph) {
        int id;
        cin >> id;
        int size;
        cin >> size;
        for (int j = 0; j < size; ++j) {
            int k;
            cin >> k;
            g.push_back(k-1);
        }
    }
    int time = 0;
    for (int i = 0; i < n; ++i) {
        if (!checkList[i]) {
            dfs(time, i, graph, arrivalTimes, leftTimes, checkList);
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << i+ 1 << " " << arrivalTimes[i] << " " << leftTimes[i]<< endl;
    }

}


Measured memory_bytes: 3176
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int k = 0, n;
string s, t, u;
vector<string> ans;

int main(){
	cin >> n;
	REP(j, n){
		cin >> s >> t;
		k = 0;
		if (s.size() > 80 || t.size() > 80){
			cout << "overflow" << endl;
			continue;
		}
		reverse(ALL(s));
		reverse(ALL(t));
		while (s.size() != t.size()){
			if (s.size() > t.size()) t += "0";
			else s += "0";
		}
		reverse(ALL(s));
		reverse(ALL(t));
		REP(i, s.size()){
			int x = (s[s.size() - 1 - i] - '0') + (t[s.size() - 1 - i] - '0');
			string q;
			stringstream ss;
			if (i != s.size() - 1){
				ss << ((x + k) % 10);
			}
			else{
				ss << x + k;
			}
			ss >> q;
			ans.push_back(q);
			if (x + k >= 10){
				k = (x + k) / 10;
			}
			else{
				k = 0;
			}
		}
		reverse(ALL(ans));
		REP(i, ans.size()){
			u += ans[i];
		}
		if (u.size() > 80)cout << "overflow" << endl;
		else cout << u << endl;
		u = "";
		ans.clear();
	}
}

//int a[110], b[110], ans[110];
//string s, t;
//int n;
//
//int main(){
//	cin >> n;
//	while (n--){
//		cin >> s >> t;
//		if (s.size() > 80 || t.size() > 80){
//			cout << "overflow\n";
//			continue;
//		}
//		REP(i, s.size())a[i] = s[s.size() - 1 - i] - '0';
//		REP(i, t.size())b[i] = t[t.size() - 1 - i] - '0';
//		ll k = 0;
//		REP(i, 101){
//			ans[i] = (a[i] + b[i] + k) % 10;
//			k = (a[i] + b[i] + k) / 10;
//		}
//		if (ans[80] != 0){
//			cout << "overflow\n";
//			continue;
//		}
//		for (int i = max(s.size(), t.size()); i >= 0; i--){
//			if (i == max(s.size(), t.size())){
//				if (ans[i] != 0){
//					cout << ans[i];
//				}
//			}
//			else{
//				cout << ans[i];
//			}
//		}
//		cout << endl;
//		REP(i, 101){
//			ans[i] = 0;
//			a[i] = 0;
//			b[i] = 0;
//		}
//	}
//}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pi pair<int,int>
#define vp vector<pi>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define For(i,a,b) for(int i=a;i<b;i++)
#define debug(x) cout<<"DEBUG------> "<<#x<<" -> "<<x<<endl
#define endl "\n"
#define all(x) x.begin(),x.end()

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	if (n % 1000 == 0)
		cout << 0 << endl;
	else {
		cout << 1000 - n % 1000 << endl;
	}

	return 0;
}



Measured memory_bytes: 3648
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
	static String[] Lb;
	private static Scanner in;
	public static void main(String[] args) {
		in = new Scanner(System.in);
    int N = in.nextInt(); // the number of cells on the Y axis
    int X = in.nextInt(); // the number of cells on the Y axis
    List<String>  lineA= new ArrayList<>();
    List<String>  lineB= new ArrayList<>();
    in.nextLine();
    int count = 0;
    while(count< N){
        lineA.add(in.nextLine());
    count++;
    }
    count =0;
    while(count< X){
        lineB.add(in.nextLine());
    count++;
    }
      System.out.println(recalTo(lineA,lineB));
}
	static int cal (int N,int X){
		int L = 0;
		L = N + X;
		L += (N-X)/X * 2 -X * 2;
		return L;
	}
	//文字列比較 何文字目から一致しているかを返す
	public static int recal(String A , String B ,int i ,boolean trig){
		if(B.length() + i > A.length()){
			return -1;
		}
		if(A.substring(i, i + B.length()).equals(B)){
			return i;
		}else{
			if(trig){
				return recal(A,B,++i, trig);
			}else{
				return -1;
			}
		}
	}
	
	public static boolean matchList(List<String> LA , List<String> LB ,int indexA){
		boolean trig = false;
		int indexB = 0;
		int length = 0;
		int length1 = 0;
		for(String A : LA){
			A = A.substring(indexA);
			String B = LB.get(indexB);
			if((length = recal(A,B,length, trig)) != -1){
				if(!trig){
					length1 = length;
				}
				trig = true;
				indexB++;
				if(length1 != length){
					trig = false;
					indexB = 0;
					length = 0;
				}
			}else{
				trig = false;
				indexB = 0;
				indexA = 0;
				length = 0;
			}
			if(trig && indexB == LB.get(0).length()){
				return true;
			}
		}
		return false;
	}
	public static String recalTo(List<String> LA , List<String> LB){
		//Aの続きから検索を再開したい。
		List<String> AA = LA;
		int index = 0;
		while(true){
			if(AA.isEmpty()){
				break;
			}
			if(matchList(LA, LB, index)){
				return "Yes";
			}
			index++;
			if(LA.get(0).length() <= index){
				LA.remove(0);
				index = 0;
			}
		}
		return "No";
	}
}

Measured memory_bytes: 18384
N, C, K = map(int,input().split())
T = []
for _ in range(N):
    T.append(int(input()))
T.sort()

ans = 0
i = 0
while i < N:
    t = T[i] + K
    j = 0
    while i + j < N and T[i+j] <= t and j < C:
        j += 1
    ans += 1
    i += j
print(ans)

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

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

typedef pair<int, int> Pi;
typedef tuple<int, int, int> Ti;
typedef vector<int> vint;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int n, t;
int sx, sy;
bool mas[55][55][55][55];
map<int, int> mp;
int D;

bool used[4][55][55][1010];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
string ds = "NESW";
using T4 = tuple<int, int, int, int>;
bool in(int x, int y) {
  return 0<=x&&x<=50&&0<=y&&y<=50;
}
void bfs() {
  set<Pi> ans;
  queue<T4> que;
  memset(used, false, sizeof(used));
  rep(i, 4) {
    int nx = sx + dx[i], ny = sy + dy[i];
    if(!in(nx, ny) || !mas[sx][sy][nx][ny]) continue;
    que.emplace(nx, ny, i, 1);
    used[i][ny][nx][1] = true;
  }
  while(!que.empty()) {
    int x, y, dir, dist;
    tie(x, y, dir, dist) = que.front(); que.pop();
    //cout<<x<<" "<<y<<" "<<dir<<" "<<dist<<endl;
    if(dist > D) break;
    rep(i, 4) {
      if(i == (dir+2)%4) continue;
      int nx = x + dx[i], ny = y + dy[i];
      if(!in(nx, ny) || !mas[x][y][nx][ny]) continue;
      if(mp.count(dist)) {
	if(dir != mp[dist] && i != mp[dist]) continue;
	if(used[i][ny][nx][dist+1]) continue;
	que.emplace(nx, ny, i, dist+1);
	used[i][ny][nx][dist+1] = true;
	if(dist == D) ans.emplace(x, y);
      } else {
	if(used[i][ny][nx][dist+1]) continue;
	que.emplace(nx, ny, i, dist+1);
	used[i][ny][nx][dist+1] = true;
      }
    }
  }
  for(Pi p : ans) cout << p.first << " " << p.second << endl;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  memset(mas, false, sizeof(mas));

  cin >> n >> sx >> sy >> t;
  rep(i, n) {
    int ax, ay, bx, by;
    cin >> ax >> ay >> bx >> by;
    if(ax == bx) {
      if(ay > by) swap(ay, by);
      reps(y, ay, by) mas[ax][y][ax][y+1] = mas[ax][y+1][ax][y] = true;
    } else {
      if(ax > bx) swap(ax, bx);
      reps(x, ax, bx) mas[x][ay][x+1][ay] = mas[x+1][ay][x][ay] = true;
    }
  }
  D = 0;
  rep(i, t) {
    int d; char c;
    cin >> d >> c;
    D += d;
    mp[D] = ds.find(c);
  }

  bfs();

  return 0;
}

Measured memory_bytes: 24080
#include <iostream>
#include <limits.h>
using namespace std;

int a[5001] = {0};
int S[5001] = {0};

int main() {
  int n;
  while(cin >> n) {
  if(n == 0) break;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

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

  int maxsum = INT_MIN;
  int sum;
  for(int i = 0; i <= n-1; i++){
    for(int j = i + 1; j <= n;j++) {
      sum = S[j] - S[i];
      if(sum > maxsum)
	maxsum = sum;
    }
  }
  cout << maxsum << endl;
  }
}

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

int c_i(char x){
  if(x=='1')
    return 1;
  if(x=='2')
    return 2;
  if(x=='3')
    return 3;
  if(x=='4')
    return 4;
  if(x=='5')
    return 5;
  if(x=='6')
    return 6;
  if(x=='7')
    return 7;
  if(x=='8')
    return 8;
  if(x=='9')
    return 9;
  if(x=='0')
    return 0;
}

int main() {
  string S;
  cin>>S;
  vector<int> X(S.size()-2);
  for(int i=0;i<S.size()-2;i++){
    int a=c_i(S.at(i));
    int b=c_i(S.at(i+1));
    int c=c_i(S.at(i+2));
    int A=100*a+10*b+c;
    int B;
    if(A>753)
      B=A-753;
    else
      B=753-A;
    X.at(i)=B;
  }
  sort(X.begin(),X.end());
  cout<<X.at(0)<<endl;
}


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

int a[109];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int t = 1, ans = 0;
	cin >> a[0];
	for (int i = 1; i < n; i++) {
		cin >> a[i];
		if (a[i] != a[i - 1]) {
			ans += t / 2;
			t = 0;
		}
		t++;
	}
	ans += t / 2;
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
a,b,c,x=[int(input()) for _ in range(4)]
cnt=0
for i in range(a+1):
    total=0
    for j in range(b+1):
        k=(x-(500*i+100*j))//50
        if k<=c and k>=0 : 
            total=500*i+100*j+50*k
            if total==x:cnt+=1
print(cnt)

Measured memory_bytes: 3188
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define P(x) cerr << #x << "=" << x << endl

const int MOD = 998244353;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int bc(int n) { return n ? bc((n-1)&n)+1 : 0; }

const int N = 301;
int i, j, k, m, n, rn, bn;
string s;
int a[N][N], b[N][N], used[N], ans2;
ll ans;

void add(int& x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

void solve() {
    F0(i, m) F0(j, n) cin >> a[i][j];

    int ind = 0;
    CL(0, used);
    F0(j, n) {
        F0(i, m) if (a[i][j] && !used[i]) {
            for (int k = i + 1; k < m; k++) if (a[k][j] && !used[k]) {
                F0(l, n) a[k][l] ^= a[i][l];
            }
            ind++;
            used[i] = 1;
            break;
        }
    }
    ans = 0;
    F0(i, ind) {
        ans = (ans * 2 + 1) % MOD;
    }
    F0(i, m - ind + n - 1) ans = (ans * 2) % MOD;
    cout << ans << endl;
}

int main() {
    //freopen("x.in", "r", stdin);
    while (cin >> m >> n) {
        solve();
    }
    return 0;
}


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

int main() {
    string s;
    cin>>s;
    int ss=s.size(),half=ss/2,count=0;
    for(int i=0;i<half;i++){
        if(s[i]!=s[ss-i-1]) count++;
    }
    cout << count << endl;
    return 0;

}


Measured memory_bytes: 3624
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
#include <array>
#include <string>
#include <queue>
#include <cmath>
#include <iterator>
#include <math.h>
#include <cstdio>
#include <map>
#include <set>
#include <unordered_map>

using namespace std;
using lli = long long int;
using ulli = unsigned long long int;

int main(void){
    vector<string> blue;
    vector<string> red;
    int N,M;
    int answer = 0;
    int s;
    string stk;
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> stk;
        blue.push_back(stk);
    }
    cin >> M;
    for(int i=0;i<M;i++){
        cin >> stk;
        red.push_back(stk);
    }
    for(int i=0;i<N;i++){
        stk = blue[i];
        s = count(blue.begin(),blue.end(),stk) - count(red.begin(),red.end(),stk);
        answer = max(answer,s);
    }
    cout << answer << endl;
    return 0;
}


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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    string s;
    cin >> s;

    if (s.find("RRR") != std::string::npos) {
        print(3);
    } else if (s.find("RR") != std::string::npos) {
        print(2);
    } else if (s.find("R") != std::string::npos) {
        print(1);
    } else {
        print(0);
    }

    return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>
int main()
{
	int sx, sy, tx, ty;
	int i;
	scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
	for(i = 0; i < ty - sy; i++){
		printf("U");
	}
	for(i = 0; i < tx - sx; i++){
		printf("R");
	}
	for(i = 0; i < ty - sy; i++){
		printf("D");
	}
	for(i = 0; i < tx - sx + 1; i++){
		printf("L");
	}
	for(i = 0; i < ty - sy + 1; i++){
		printf("U");
	}
	for(i = 0; i < tx - sx + 1; i++){
		printf("R");
	}
	printf("D");
	printf("R");
	for(i = 0; i < ty - sy + 1; i++){
		printf("D");
	}
	for(i = 0; i < tx - sx + 1; i++){
		printf("L");
	}
	printf("U\n");
	return 0;
}

Measured memory_bytes: 128
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()
    num_list = i_list()

    num_list.sort()

    print(num_list[n-1] - num_list[0])

if __name__ == '__main__':
    main()


Measured memory_bytes: 77040
N = int(input())

def yaku(n):
    c = 0
    for i in range(1,n+1,2):
        if n % i == 0:
            c += 1
    if c == 8:
        return True
    else:
        return False

count = 0
for i in range(1,N+1,2):
    if yaku(i):
        count += 1

print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <map>

using namespace std;

int main() {
    int N;
    cin >> N;
    map<long long int, int> mp;
    for(int n=0; n<N; n++) {
        long long int A;
        cin >> A;
        
        mp[A]++;
    }
    
    int ans=0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        if(itr->second%2) {
            ans++;
        }
    }
    
    cout << ans << endl;


    return 0;
    
}

Measured memory_bytes: 6528
/*
********************
Author : Sahil Kundu
********************
*/
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb(i) push_back(i)
#define pp() pop_back()
#define f first
#define s second
#define mk(l,r) make_pair(l,r)
#define all(vc) vc.begin(),vc.end()
#define bg(vc) vc.begin()
#define ed(vc) vc.end()
#define ms(i,j) memset(i,j,sizeof i)
#define w(t) while(t--)
const ll MAX=1e5+5;
const ll INF=2e18;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t=1;
    //cin>>t;
    w(t)
    {
        ll n,k;
        cin>>n>>k;
        ll ans=0;
        ll mp[n+1]={0};
        for(int i=1;i<=n;i++)
        {
            mp[i]=(mp[i-1]+i)%mod;
        }
        for(int i=k;i<=n;i++)
        {
            ans=(ans+mp[n])%mod;
            ans=(ans-mp[n-i]+mod)%mod;
            ans=(ans-mp[i-1]+mod)%mod;
            ans=(ans+1)%mod;
        }
        cout<<(ans+1)%mod<<"\n";
    }
}
/*ll msb(ll x)
{
	ll k=(ll)log2(x);
	return (ll)(pow(2,k));
}
#define gc getchar_unlocked
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}*/

Measured memory_bytes: 5160
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define res(n) resize(n)
#define rev(v) reverse(v.begin(),v.end())
#define sor(v) sort(v.begin(),v.end())
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define ve vector
#define pq priority_queue
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;



int main()
{
    int A,B;
    cin >> A >> B;
    cout << max(A+B,max(A-B,A*B)) << endl;

    return 0;
}


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

if B-A<=2:
  print(K+1)
else:
  if (K-(A-1))%2!=0:
    print(A+(K-(A-1))//2*(B-A)+1)
  else:
    print(A+(K-(A-1))//2*(B-A))

Measured memory_bytes: 3060
use std::io::*;
use std::str::*;

fn read<T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s.by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

pub fn main() {
    let stdin = stdin();
    let mut stdin = stdin.lock();

    let n: u32 = read(&mut stdin).unwrap();
    let mut cards: Vec<u32> = (0..n).map(|_x| read(&mut stdin).unwrap()).collect();

    cards.sort();
    cards.reverse();

    let alice: u32 = cards
        .iter()
        .enumerate()
        .filter(|x| x.0 % 2 == 0)
        .fold(0, |acc, x| acc + x.1);
    let bob: u32 = cards
        .iter()
        .enumerate()
        .filter(|x| x.0 % 2 != 0)
        .fold(0, |acc, x| acc + x.1);

    println!("{:?}", alice - bob);
}


Measured memory_bytes: 4476
#include<stdio.h>
int main(){
  int a[3],i,j,temp;
  for(i=0;i<3;i++){
    scanf("%d",&a[i]);
  }
  for(i=0;i<3;i++){
    for(j=0;j<3-i-1;j++){
      if(a[j]>a[j+1]){
	temp=a[j];
	a[j]=a[j+1];
	a[j+1]=temp;
      }
    }
  }
  for(i=0;i<3;i++){
    printf("%d",a[i]);
    if(i<2){
      printf(" ");
    }
  }
  printf("\n");
  return(0);
}

Measured memory_bytes: 600
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e10;
//const ll MOD = 1e9 + 7;
const ll MOD = 998244353;


int main(){
	string S;
	int w;
	cin >> S >> w;
	int len = S.length();
	int pos = 0;
	while (pos < len){
		cout << S[pos];
		pos += w;
	}
	cout << endl;
}

Measured memory_bytes: 256
n=int(input())
pri=[2]
for i in range(3,n+1):
    flag=1
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            flag=0
            break
    if flag==1:
        pri.append(i)
l=len(pri)
cnt=[0]*l
for i in range(2,n+1):
    x=i
    for j in range(l):
        while x%pri[j]==0:
            cnt[j]+=1
            x=x//pri[j]
s=1
for j in range(l):
    s*=(cnt[j]+1)
    s%=(10**9+7)
print(s)


Measured memory_bytes: 3188
N, K = map(int, input().split())

inputs = []
priority_queue = []
queue = []
sets = set()

for _ in range(N):
    key, value = map(int, input().split())
    inputs.append((value, key))

inputs.sort(reverse=True) # valueで降順のソートをかけてる

for i in range(K):
    value, key = inputs[i]
    if key in sets:
        queue.append(value)
    else:
        priority_queue.append(value)
        sets.add(key)

sum_priority_queue = sum(priority_queue)
sum_queue = sum(queue)
kinds = len(sets)
ans = sum_priority_queue + sum_queue + kinds ** 2
for i in range(K, N):
    if not queue:
        break
    value, key = inputs[i]
    if key in sets:
        continue
    sets.add(key)
    sum_queue -= queue.pop()
    sum_priority_queue += value
    kinds += 1
    ans = max(ans, sum_priority_queue + sum_queue + kinds ** 2)

print(ans)


Measured memory_bytes: 19836
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

vector<ll> pickdiv(ll n){
    vector<ll> res;
    for(ll i=1; i*i <=n;i++){
        if(n%i)continue;
        res.emplace_back(i);
        ll q = n/i;
        if(q != i){
            res.emplace_back(q);
        }
    }
    return res;
}

int main(){
    ll N,M;
    cin >> N >> M;
    auto v = pickdiv(M);
    sort(v.begin(), v.end(), greater<ll>());
    //vector<ll> a(N);
    ll ans;
    rep(i,v.size()){
        if(v[i] * N > M) continue;
        //ll tmp = M - (v[i]*N);
        //ll cnt = tmp/v[i];
        //a = vector<ll>(N, v[i]);
        //v[0] += tmp;
        ans = v[i];
        break;
    }
    cout << ans <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
const int maxn=2010;
int n,d[maxn],cnt[maxn][maxn];
long long ans;
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) read(d[i]);
	sort(d+1,d+n+1);
	for (int i=n;i>=1;i--) {
		for (int j=1;j<maxn;j++) cnt[i][j]=cnt[i+1][j];
		for (int j=d[i];j<maxn;j++) cnt[i][j]++;
	}
	for (int i=1;i<=n;i++) {
		for (int j=i+1;j<=n;j++)
			ans+=cnt[j+1][d[i]+d[j]-1];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 16000
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
string s[n];
int p[n];
vector<pair<pair<string,int>,int>> vec;

for(int i=0;i<n;i++){
 cin>>s[i]>>p[i];
 vec.push_back(make_pair(make_pair(s[i],-1*p[i]),i+1));
}

sort(vec.begin(),vec.end());
for(int i=0;i<n;i++){
 cout<<get<1>(vec[i])<<endl;
}
}


Measured memory_bytes: 256
import copy
SD = list(input())
T = list(input())

Possible = []
for TSD in range(0,len(SD)-len(T)+1):
    SDCopy = copy.deepcopy(SD)
    String = SDCopy[TSD:TSD+len(T)]
    Flag = True
    for TST in range(0,len(T)):
        if String[TST]!='?' and String[TST]!=T[TST]:
            Flag = False
            break
    if Flag:
        SDCopy[TSD:TSD+len(T)] = T
        Possible.append(''.join(['a' if TSC=='?' else TSC for TSC in SDCopy]))
if Possible:
    print(sorted(Possible)[0])
else:
    print('UNRESTORABLE')

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

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

    int A;
    bool flag = true;
    for (int i = 0; i < N; i++)
    {
        cin >> A;
        if (A % 2 == 0)
        {
            if (A % 3 != 0 && A % 5 != 0)
            {
                flag = false;
            }
        }
    }
    if (flag)
    {
        cout << "APPROVED" << endl;
    }
    else
    {
        cout << "DENIED" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> pr;
typedef vector<ll> vc;
typedef unordered_map<ll,ll> umap;
#define pb emplace_back
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;

int main() {
    // your code goes here
    ll s,w;
    cin >> s >> w;
    if(w>=s) cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;
}

Measured memory_bytes: 3632
n = input()
# print(len(n))
ans = 0
for i in range(1, len(n)):
    if i % 2 == 1:
        ans += 9 * 10**(i - 1)

if len(n) % 2 == 1:
    ans += int(n) - (10**(len(n) - 1) - 1)
print(ans)



Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e2+20;
const ll mod=1e9+7;
ll n,c,a[N],b[N];
ll dp[N][N];
ll p[N][N],pre[N][N];
int main()
{
	p[0][0]=1;//i^j
	for(ll i=1;i<=400;i++)
	{
		p[i][0]=1;
		pre[i][0]=1;
		for(ll j=1;j<=400;j++)
		{
			p[i][j]=(p[i][j-1]*i)%mod;		
		}
	}
	//pre[i][j]  1^j+...i^j
	for(ll i=1;i<=400;i++)
		for(ll j=0;j<=400;j++)
			pre[i][j]=(pre[i-1][j]+p[i][j])%mod;
	while(cin>>n>>c)
	{
		for(int i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		for(int i=1;i<=n;i++)
			scanf("%I64d",&b[i]);
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=c;j++)
			{
				for(int x=0;x<=j;x++)
				{
					ll t=(pre[b[i]][x]-pre[a[i]-1][x]+mod)%mod;
					dp[i][j]=(dp[i][j]+dp[i-1][j-x]*t)%mod;
				}
			}
		}
		cout<<dp[n][c]<<endl;	
	}
	return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
	ll n;
	cin>>n;
	ll arr[n];
	ll dp[n];
	ll i=0;
	// input 
	for(i=0;i<n;i++)cin>>arr[i];
	// end_input
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(i=2;i<n;i++)
	{
		dp[i]=min(abs(arr[i]-arr[i-1])+dp[i-1],abs(arr[i]-arr[i-2])+dp[i-2]);
	}
	cout<<dp[n-1];

}


Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;

const unsigned long long B = 100000007;

bool contain(string a, string b){
    int al = a.length();
    int bl = b.length();
    if(al > bl) {
        return false;
    }

    unsigned long long t = 1;
    for(int i = 0; i < al; i++){
        t *= B;
    }

    unsigned long long ah = 0;
    unsigned long long bh = 0;
    for(int i = 0; i < al; i++) {
        ah = ah * B + a[i];
        bh = bh * B + b[i];
    }

    for(int i = 0; i + al <= bl; i++){
        if(ah == bh) {
            return true;
        }
        if(i + al < bl){
            bh = bh * B + b[i + al] - b[i] * t;
        }
    }
    return false;
}

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

    bool one_or_above = false;
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j < N; j++){
            if(S[i] == S[j]){
                one_or_above = true;
            }
        }
    }

    if(!one_or_above){
        cout << 0 << endl;
        return 0;
    }


    int left = 1;
    int right = N / 2 + 1;
    while(left + 1 < right){
        int mid = (left + right) / 2;
        bool valid = false;
        for(int i = 0; i <= N - mid * 2; i ++){
            if(contain(S.substr(i, mid), S.substr(i + mid, N - i - mid))){
                valid = true;
            }
        }
        if(valid){
            left = mid;
        } else {
            right = mid;
        }
    }
    cout << left << endl;
    return 0;
}

Measured memory_bytes: 384
H, N = map(int,input().split())
A = []
B = []
dp = [None for i in range(2*10**4)]
dp[0] = 0
for i in range(N):
    tmp_A, tmp_B = map(int,input().split())
    A.append(tmp_A)
    B.append(tmp_B)
for i in range(2*10**4):
    for j in range(N):
        if i-A[j]<0:
            pass
        elif dp[i-A[j]]!=None:
            if dp[i]==None:
                dp[i]=dp[i-A[j]]+B[j]
            else:
                dp[i]=min(dp[i],dp[i-A[j]]+B[j])

ans = 10**16
for i in range(H,2*10**4):
    if dp[i]!=None:
        if dp[i]<ans:
            ans = dp[i]
print(ans)

Measured memory_bytes: 43688
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> graph;
    static boolean[] seen;
    static int[] depth;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String res = "IMPOSSIBLE";
        graph = new ArrayList<>();
        Queue<Integer> que = new ArrayDeque<>();
        int n = sc.nextInt(), m = sc.nextInt();
        seen = new boolean[n];
        depth = new int[n];
        for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for(int i = 0; i < m; i++) {
            int a = Integer.parseInt(sc.next())-1, b = Integer.parseInt(sc.next())-1;
            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        int v = 0;
        que.offer(0);
        depth[0] = 0;
        while(que.size() > 0 && depth[v] < 2) {
            v = que.poll();
            for(int a : graph.get(v)) {
                if(a == n-1) res = "POSSIBLE";
                if(seen[a]) continue;
                que.offer(a);
                depth[a] = depth[v] + 1;
                seen[a] = true;
            }
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 116588
def merge(A,left,mid,right):
    INF = 10**9
    n1 = mid - left
    n2 = right - mid
    #L[0…n1], R[0…n2]を生成
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append(INF)
    R.append(INF)
    i = 0
    j = 0
    c = 0
    for k in range(left,right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return c

def mergeSort(A,left,right):
    if left+1 < right:
        mid = (left+right)//2
        cL = mergeSort(A,left,mid)
        cR = mergeSort(A,mid,right)
        return merge(A,left,mid,right)+cL+cR
    return 0

N = int(input())
S = list(map(int,input().split()))
c = mergeSort(S,0,N)
print(' '.join(map(str,S)))
print(c)



Measured memory_bytes: 66584
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 
int binomialCoeff(int n, int k) 
{ 
	int C[n + 1][k + 1]; 
	int i, j; 


	for (i = 0; i <= n; i++) 
	{ 
		for (j = 0; j <= min(i, k); j++) 
		{ 
			
			if (j == 0 || j == i) 
				C[i][j] = 1; 

			else
				C[i][j] = C[i - 1][j - 1] + 
						C[i - 1][j]; 
		} 
	} 

	return C[n][k]; 
}
 
void solve()
{
    string s , t ;
    cin>>s>>t ;
    int ans = 0 ;
    rep(i , s.size()){
    	if(s[i]!=t[i]){
    		ans++;
    	}
    }
    cout<<ans<<endl;
    
}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3928
import numpy as np
argList = list(map(int, input().split())) 
heights = list(map(int, input().split())) 

#いい展望台フラグ
check = np.array([1]*argList[0])

for n in range(argList[1]):
    #どことどこをつないでいるか
    con = list(map(int, input().split())) 
    #低かったらいい展望台ではない
    if heights[con[0]-1] <= heights[con[1]-1]:
        check[con[0]-1] = 0
    if heights[con[0]-1] >= heights[con[1]-1]:
        check[con[1]-1] = 0
print(np.sum(check))

Measured memory_bytes: 38440
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    vector<ll> v;
    for(ll i=0;i<n;i++){
        ll k;
        cin>>k;
        v.pb(k);
    }
    ll ans=0;
    int swit=1;
    for(ll j=0;j<10000000000;j++){
        if(swit==0){
            break;
        }

        for(ll i=0;i<n;i++){
            if(v[i]%2==0){
                v[i]=v[i]/2;
            }
            else {
                swit=0;
                break;
            }
        }
        if(swit==1)
            ans+=1;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
for j in range(n):
    a = int(input())
    b = list(map(int,input().split()))
    hop = []
    for i in range(a-1):
        hop.append(b[i+1]-b[i])
    hop.sort(reverse = True)
    if hop[0] <= 0:
        print(0,end = " ")
    else:
        print(hop[0],end = " ")
    if hop[-1] >= 0:
        print(0)
    else:
        print(-(hop[-1]))


Measured memory_bytes: 5612
N = gets.to_i
ss, sst = [], Array.new(N){Array.new(N)}
N.times do |i|
    ss[i] = gets.chomp.split('')
end
N.times do |i|
    N.times do |j|
        sst[j][i] = ss[i][j]
    end
end

sum = 0
(0...N).each do |a|
    success = true
    (0...N).each do |i|
        unless ss[i] == sst[(i+a)%N]
            success = false
            break
        end
    end
    if success
        sum += N
    end
    (0...N).each do |i|
        ss[i].rotate!(1)
    end
end
puts sum


Measured memory_bytes: 7676