akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n,m;

int main(){
	cin>>n>>m;
	cout<<(n-1)*(m-1)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define P pair<int,int>
#define mk make_pair
using namespace std;
const int N = 1e5 + 10;
int vis[N],h[N];
int main()
{
    int n,m,u,v,sum = 0;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        cin >> h[i];
    for(int i=1;i<=m;i++){
        cin >> u >> v;
        if(h[u] < h[v])
            vis[u] = 1;
        else if(h[u] > h[v])
            vis[v] = 1;
        else
            vis[u] = vis[v] = 1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i] == 0)
            sum++;
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 4412
//Guess The Number

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) int n;cin>>n;vector<int>a(n);rep(i,0,n)cin>>a[i]
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
#define cout15(a) printf("%.15f\n",a)
template<class T>inline bool chmin(T& a,T b,bool f){
if(f==1){if(a>b){a=b;return true;}return false;}
else if(f==0){if(a<b){a=b;return true;}return false;}return false;}
typedef pair<int,int> p;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

int main (){
    int n,m;cin>>n>>m;
    vector<p>a(m);
    rep(i,0,m)cin>>a[i].first>>a[i].second;
    int ans = -1;
    rep(i,0,pow(10,n)){
        bool flag = true;
        string s=to_string(i);
        if(s.size()!=n)continue;
        rep(j,0,m){
            if(s[a[j].first-1]-'0'!=a[j].second)flag=false;
        }
        if(flag){
            cout<<i<<nnn;
            return 0;
        }
    }
    cout<<-1<<nnn;
    return 0;
}

Measured memory_bytes: 256
house = [
    [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]],
    [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]],
    [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]],
    [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]
]

loopnum = gets.to_i
(1..loopnum).each do |num|
    input = gets.split(" ").map do |i| i.to_i end
    house[input[0]-1][input[1]-1][input[2]-1] += input[3]
end

(0..2).each do |i|
    puts " #{house[0][i].join(" ")}"
end
puts "####################"
(0..2).each do |i|
    puts " #{house[1][i].join(" ")}"
end
puts "####################"
(0..2).each do |i|
    puts " #{house[2][i].join(" ")}"
end
puts "####################"
(0..2).each do |i|
    puts " #{house[3][i].join(" ")}"
end

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

int main(){
  int N;
  cin >> N;
  vector<int> A;
  for(int i=0; i<N; i++){
    int a; cin >> a;
    A.push_back(a);
  }
  sort(A.begin(), A.end());
  vector<pair<int, int> > C;
  int tmp = A[0];
  int count=1;
  for(int i=1; i<N; i++){
    if(A[i]==tmp){
      count++;
      continue;
    }
    C.push_back(make_pair(tmp, count));
    tmp=A[i];
    count=1;
  }
  C.push_back(make_pair(tmp, count));
  vector<int> ans;
  int num=C[0].second;
  if(C[0].first+1==C[1].first) num+=C[1].second;
  ans.push_back(num);
  for(int i=1; i<C.size()-1; i++){
    num=C[i].second;
    if(C[i-1].first+1==C[i].first) num+=C[i-1].second;
    if(C[i+1].first-1==C[i].first) num+=C[i+1].second;
    ans.push_back(num);
  }
  num=C[C.size()-1].second;
  if(C[C.size()-2].first+1==C[C.size()-1].first) num+=C[C.size()-2].second;
  ans.push_back(num);
  sort(ans.begin(),ans.end(),greater<int>());
  cout << ans[0] << endl;
  return 0;
}

Measured memory_bytes: 1656
#include<iostream>
using namespace std;
int main(){
  int a,b,c,plus;
  while(cin >> a >> b >> c){
    plus=0;
    if(a>0 && b>0){
      plus++;
    }
    else if(c>0){
      plus++;
    }
    if(plus==0){
      cout << "Close" << endl;
    }
    else{
      cout << "Open" << endl;
    }
  }
}

Measured memory_bytes: 1152
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <list>
#include <string>
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

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

    int start = 0;
    for (int i = 0; i < N; i++)
    {
        if (S[i] == '#')
        {
            start = i;
            break;
        }
    }
    int stop = 0;
    for (int i = N - 1; i >= 0; i--)
    {
        if (S[i] == '.')
        {
            stop = i;
            break;
        }
    }

    int white = 0;
    int black = 0;
    for (int i = start; i <= stop; i++)
    {
        if (S[i] == '.')
            white++;
        else
            black++;
    }

    int ret = min(white, black);
    int cw = 0;
    int cb = 0;
    for (int i = start; i <= stop; i++)
    {
        if (S[i] == '.')
            cw++;
        else
            cb++;

        if (ret > cb + white - cw)
            ret = cb + white - cw;
    }

    cout << ret << endl;
}

void cheatsheet()
{
    // loop
    // vector<int> vec(10);
    vector<int> vecloop;
    REP(i, 10)
    {
        vecloop.push_back(i);
    }

    // swap
    int a = 1;
    int b = 5;
    swap(a, b); // -> a = 5, b = 1

    // sort
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sort(arr, arr + 9, greater<int>()); // 9 8 7 6 5 4 3 2 1

    // lower
    vector<int> vec(arr, end(arr));
    sort(vec.begin(), vec.end());
    cout << lower_bound(vec.begin(), vec.end(), 2)[0]; // 2

    // map
    map<Pll, ll> m;
    m[Pll(10, 100)] = 100;
}

Measured memory_bytes: 640
N = int(input())
a = [map(int,input().split()) for i in range(N)]
arr = [[[0 for i3 in range(10)] for i2 in range(3)] for i1 in range(4)]
for b,f,r,v in a:
    arr[b-1][f-1][r-1] += v
i=1
for bl in arr:
    for fl in bl:
        print(' '+' '.join(map(str,fl)))
    if i != len(arr):
        print('#'*20)
    i += 1

Measured memory_bytes: 7712
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <math.h>
#include <stdio.h>
#define INF 1000000000
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long int ll;
using namespace std;

int main() {

	int n, d; cin >> n >> d;
	int ans = d * 2 + 1;
	if(n % ans != 0) { cout << n / ans + 1 << endl; }
	else cout << n / ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
// *テンプレート*
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
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; }
const long long MOD = 1000000007;
const long long INF = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
map<int, int> mp;
using Graph = vector<vector<int>>; 
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, c, k; cin >> n >> c >> k;
	vector<int>t(n); rep(i, n)cin >> t[i];
	sort(t.begin(), t.end());
	int ans = 0, cnt = 0, time = 0;
	rep(i, n) {
		int T = t.at(i);
		if (cnt == c || time < T) {
			ans++;
			cnt = 0;
			time = T + k;
		}
		cnt++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<queue>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;

const int MOD = 1e9+7;
ll dp[62][3];
ll N;

ll dfs(int keta, int diff) {
	if (keta == -1) return 1;
	ll& ret = dp[keta][diff];
	if (ret >= 0) return ret;
	if ((1ll<<keta) > N) return ret = dfs(keta-1, diff);
	ret = 0;
	int digit = (N>>keta)&1;
	// 両方 0
	ret += dfs(keta-1, min(2*diff+digit, 2));
	// 片方 1
	if (2*diff+digit >= 1) ret += dfs(keta-1, min(2*diff+digit-1, 2));
	// 片方 1
	if (2*diff+digit >= 2) ret += dfs(keta-1, min(2*diff+digit-2, 2));
	ret %= MOD;
	return ret;
}

int main() {
	cin >> N;
	memset(dp, -1, sizeof(dp));
	cout << dfs(60, 0) << endl;
	return 0;
}


Measured memory_bytes: 256
def selectionSort(A,N):
    count=0
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j] < A[minj]:
                minj = j
        A[i],A[minj] = A[minj],A[i]
        if i != minj:
            count +=1
    return A,count

N = int(input())
A = list(map(int,input().split()))
A,count = selectionSort(A,N)
print(" ".join(map(str,A)))
print("%d"%(count))



Measured memory_bytes: 5600
#include<iostream>

using namespace std;

int main() {
	int n, ans = 0;

	cin >> n;

	for (int i = 1; i <= n; i += 2) {
		int c = 0;
		for (int j = 1; j <= i; j++) {
			if (i%j == 0) {
				c++;
			}
		}
		if (c == 8) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main(void) {
  string str;
  string com_str = "keyence";

  cin >> str;
  int correct = 0;

  int j=0;
  for(int i=0; i<str.length(); i++) {
    if (str[i] == com_str[j]) {
      j++;
      if (j >= com_str.length()) {
        correct = 1;
        break;
      }
    } else {
      break;
    }
  }

  int k=com_str.length();
  for(int i=str.length(); i>0; i--) {
    if(str[i-1] == com_str[k-1]) {
      k--;
      if (k <= 0) {
        correct = 1;
        break;
      }
    } else {
      k=i;
      break;
    }
  }

  if (str == com_str || correct == 1 || k == j) {
    cout << "YES" << endl;
  } else {
    str.erase(str.begin()+j, str.begin()+k);
    if (str == com_str) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }

  return 0;

}


Measured memory_bytes: 256
n, m, r = gets.strip.split.map(&:to_i)
r = gets.strip.split.map(&:to_i)
 
roads = Array.new(n+1) { [10**8]*(n+1) }
 
readlines.each do |line|
  a, b, c = line.strip.split.map(&:to_i)
  roads[b][a] = roads[a][b] = c
end
 
 
(n+1).times do |via|
  (n+1).times do |s|
    s_via = roads[s][via]
    (n+1).times do |g|
      via_center = s_via + roads[via][g]
      roads[g][s] = roads[s][g] = via_center if roads[s][g] > via_center
    end
  end
end
def recursive_roads_check(current, cost, remains, roads)
  return cost if remains.empty?

  remains.map {|next_town|
    next_remains = remains.dup - [next_town]
    next_cost = 0
    next_cost = cost + roads[current][next_town] if current
    recursive_roads_check(next_town, next_cost, next_remains, roads)
  }.min
end

#roads.each {|r|p r}

p recursive_roads_check(nil, 0, r, roads)



Measured memory_bytes: 4092
import java.util.*;

class Graph {
	private int totalVertex;
	private LinkedList<LinkedList<Integer>> adjList;
	private LinkedList<Boolean> visited;
	private ArrayList<Integer>dist;
	public Graph() {
		totalVertex = 0;
		visited = new LinkedList<Boolean>();
		dist = new ArrayList<Integer>();
	}
	public void loadAdjList() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjList = new LinkedList<LinkedList<Integer>>();
		for(int i = 0; i < totalVertex; i ++) {
			LinkedList<Integer> tmp = new LinkedList<Integer>();
			in.nextInt();
			int degree = in.nextInt();
			for(int j = 0; j < degree; j ++) {
				int idx2 = in.nextInt() - 1;
				tmp.add(idx2);
			}	
			adjList.add(tmp);
		}
		in.close();
	}
	public int nextUnvisited() {
        for(int i = 0; i < visited.size(); i ++) {
            if(visited.get(i) == false) {
            	return i;
            }
        }
        return -1;
    }
	public void preWalk() {
        visited.clear();
        dist.clear();
        for(int i = 0; i < totalVertex; i ++) {
        	visited.add(false);
        	dist.add(0);
        }
    }
	public void walk() {
        preWalk();
        BFS(0);
    }
	public boolean ifVisited(int v) {
		if (v >= 0 && v < totalVertex)
			return visited.get(v);
		else
			return true;
	}
	public void setVisited(int v) { visited.set(v, true); }
	
	public void BFS(int v) {
		int distance = 0;
		LinkedList<Integer> queue = new LinkedList<Integer>();
		setVisited(v);
		queue.add(v);
		dist.set(v, distance);
		while (queue.size() != 0) {
			v = queue.poll();
			Iterator<Integer> i = adjList.get(v).listIterator();
			while (i.hasNext()) {
				int n = i.next();
				if (!visited.get(n)) {
					visited.set(n, true);
					dist.set(n, dist.get(v) + 1);
					queue.add(n);
				}
			}
		}
	}
	
	public void displayEnum() {
		for (int i = 0; i < totalVertex; i++) {
			if (visited.get(i) == false) {
				System.out.print((i + 1) + " " + -1 + "\n");
			} else {
				System.out.print((i + 1) + " " + dist.get(i) + "\n");
			}
		}
    }
}

public class Main {
	public static void main(String[] args) {
		Graph g = new Graph();
		g.loadAdjList();
		g.walk();
		g.displayEnum();
	}
}


Measured memory_bytes: 28432
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int n, k = 0;
    cin >> n;
    int v[100000];
    for (int i = 0; i < n; i++)
        cin >> v[i];
    if (!prev_permutation(v, v + n)) {
        ++k;
        next_permutation(v, v + n);
    }
    for (int j = k; j < 3; j++) {
        for (int i = 0; i < n; i++) {
            cout << v[i];
            if (i != n - 1)cout << " ";
        }
        cout << endl;
        if (!next_permutation(v, v + n))
            break;
    }
}


Measured memory_bytes: 3116
using System;
using System.IO;
using System.Collections.Generic;
namespace I_am_the_green_coder{
    class Inonoa{
        // なんか入力用の関数作ったけどまだテストしてないので使う前に確かめて
        static void Main(){
            long[] nk = ILongs();
            long n = nk[0];
            long k = nk[1];

            long combi = n-k+1;
            for(long i=0;i<k;i++){
                if(i==0){
                    Console.WriteLine(combi);
                    continue;
                }

                if(n-k-i+1<1){
                    Console.WriteLine(0);
                    continue;
                }
                
                combi *= (k-i) * (n-k+1-i);
                combi %= MOD;
                long b = Modinv((i+1)*i,MOD);
                combi *= b;
                combi %= MOD;

                Console.WriteLine(combi);
            }
        }

        static readonly long MOD = 1000000007;

        static long Modinv(long  a,  long m) {
    long b = m; long u = 1;long v = 0;
    long tmp;
    while (b>0) {
        long t = a / b;
        a -= t * b;
        tmp = a; a = b; b = tmp;
        u -= t * v;
        tmp = v; v = u; u = tmp;
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

        ///<summary>a_1, a_2, a_3, ...みたいなの</summary>
        static long[] ILongs(){
            string[] s = Console.ReadLine().Split();
            long[] re = new long[s.Length];
            for(long i=0;i<s.Length;i++){
                re[i] = long.Parse(s[i]);
            }
            return re;
        }

        ///<summary>xooxoxoxxoxo...みたいなの</summary>
        static char[] IChars(){
            return Console.ReadLine().ToCharArray();
        }

        ///<summary>n m とかをちょっとはやくかくだけ</summary>
        static string[] IStrings(){
            return Console.ReadLine().Split();
        }

        ///<summary>n行の入力を取ったり</summary>
        static long[][] ILongLongs(long n){
            long[][] re = new long[n][];
            for(long i=0;i<n;i++){
                string[] s = Console.ReadLine().Split();
                re[i] = new long[s.Length];
                for(long j=0;j<s.Length;j++){
                    re[i][j] = long.Parse(s[j]);
                }
            }
            return re;
        }

        static char[][] ICharsChars(long n){
            char[][] re = new char[n][];
            for(long i=0;i<n;i++){
                re[i] = Console.ReadLine().ToCharArray();
            }
            return re;
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;

int main(){
    ll N;cin>>N;
    ves W(N);rep0(i,N){cin>>W[i];}
    set<str> S;rep0(i,N){S.insert(W[i]);}
    if(W.size()!=S.size()){cout<<"No"<<endl;return 0;}
    rep0(i,N-1){
        ll a=W[i].size();
        char s=W[i][a-1];
        if(s!=W[i+1][0]){cout<<"No"<<endl;return 0;}
    }
    cout<<"Yes"<<endl;
}
      

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

int main()
{
	char inputS[100];
	scanf("%s", &inputS);

	for (int i = 0; i < strlen(inputS); i++)
	{
		inputS[i] = 'x';
	}

	printf("%s \n", inputS);
	return 0;
}


Measured memory_bytes: 128
from sys import stdin
##  input functions for me
def ria(sep = ''):
    if sep == '' :
        return list(map(int, input().split())) 
    else: return list(map(int, input().split(sep)))
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

## main ##
N = ri()
H = ria()

cnt = 0
ma = 0
for i in range(N):
    if (H[i] >= ma ): cnt += 1
    ma = max(ma, H[i])

print(cnt)

    





Measured memory_bytes: 3064
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
#from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1
def find(a,i):
	if i==a[i]:
		return a[i]
	a[i]=find(a,a[i])
	return a[i]
def union(a,x,y):
	xs=find(a,x)
	ys=find(a,y)
	if xs!=ys:
		if rank[xs]<rank[ys]:
			xs,ys=ys,xs
		a[ys]=xs
		rank[xs]+=1			

while t>0:
	t-=1
	n,m=mi()
	a=[i for i in range(n+1)]
	rank=[0]*(n+1)
	for i in range(m):
		x,y=mi()
		union(a,x,y)
	d=[0]*(n+1)	
	for i in range(1,n+1):	
		a[i]=find(a,i)
		d[a[i]]+=1
	print(max(d))	

	



Measured memory_bytes: 94220
using System;
using System.Collections.Generic;
using System.Linq;

namespace atcoder {
    class Program {
        static void Main (string[] args)
        {
            ABC139.Lower();
        }
    }

    class ABC139
    {
        public static void Lower()
        {
            int n = int.Parse(Console.ReadLine());
            var hight = Input.getIntArray();
            int point = 0;
            int max = 0;
            int tmp = 0 ;
            int i = 0;

            while(i<n-1)
            {
                if(hight[i]>=hight[i+1])
                {
                    tmp++;    
                    
                    if(tmp > max)
                    {
                        max = tmp;
                    }
                }
                else
                {
                    tmp=0;
                }
                
                i++;
            }

            Console.WriteLine(max);
        }    
    }

    class Input {
        public static int[] getIntArray () {
            string[] s = Console.ReadLine ().Split (' ');
            int[] num = s.Select (x => int.Parse (x)).ToArray ();
            return num;
        }
        public static long[] getLongArray () {
            string[] s = Console.ReadLine ().Split (' ');
            long[] num = s.Select (x => long.Parse (x)).ToArray ();
            return num;
        }
        public static string[] getStringArray (int n) {
            var s = new string[n];
            for (int i = 0; i < n; i++) {
                s[i] = Console.ReadLine ();
            }
            return s;
        }
    }
}

Measured memory_bytes: 28252
n,l=map(int,input().split())
a =[]
for i in range(1,n+1):
  a.append(l+i-1)
b =10**10
for i in range(n):
    d = abs(sum(a)-(sum(a[:i])+sum(a[i+1:])))
    if b>d:
        c = sum(a[:i])+sum(a[i+1:])
        b = d
print(c)

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

using namespace std;

#define lp(i,n) for(int i = 0; i <n;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define SZ(v) ((int)((v).size()))
typedef long long ll;

const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;

void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int a[N];
int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    int n;
    scanf("%d",&n);
    bool f=true;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n-2;i>=0;i--){
        if(a[i]>a[i+1]){
            if(a[i]-1>a[i+1]){
                puts("No");
                f=false;
                break;
            }else{
                a[i]--;
            }
        }
    }
    if(f)puts("Yes");
    return 0;
}

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

signed main(void)
{
	int n, l, out_l, out_r;
	string s;
	cin >> n >> s;

	l = out_l = out_r = 0;
	rep(i, n)
	{
		if (s[i] == ')')
		{
			if (out_r > 0)
				out_r--;
			if (l == 0) 
				out_l++;
			else
				l--;
		}
		else if(s[i] == '(')
		{
			l++;
			out_r++;
		}
	}
	rep(i, out_l)
		cout << '(';
	cout << s;
	rep(i, out_r)
		cout << ')';
	cout << endl;
}


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


int main() {
    long long a, b;
    cin >> a >>b;

    if (a > 0 && b > 0) {
        cout << "Positive" << endl;
        return 0;
    }

    if (a < 0 && b > 0) {
        cout << "Zero" << endl;
        return 0;
    }

    if (abs(a - b) % 2 == 0) {
        cout << "Negative" << endl;
    } else if (abs(a - b) % 2 == 1) {
        cout << "Positive" << endl;
    }

}

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

const int N = 2004;

int n, x, y, ans[N];
bool vis[N];

void bfs(int start) {
    memset(vis, false, sizeof vis);

    vis[start] = vis[0] = vis[n + 1] = true;

    queue<pair<int, int>> qu;

    qu.push({start, 0});

    while (qu.empty() == false) {
        int u = qu.front().first, dis = qu.front().second;
        qu.pop();

        vector<int> adj = {u - 1, u + 1};

        if (u == x) {
            adj.push_back(y);
        } else if (u == y) {
            adj.push_back(x);
        }

        for (int v : adj) {
            if (vis[v] == false) {
                vis[v] = true;
                qu.push({v, dis + 1});
                ans[dis + 1]++;
            }
        }
    }
}

int main() {
    cin >> n >> x >> y;

    for (int i = 1; i <= n; i++) {
        bfs(i);
    }

    for (int i = 1; i < n; i++) {
        cout << ans[i] / 2 << endl;
    }

    return 0;
}



Measured memory_bytes: 3584
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		long n=sc.nextLong();
		long m= sc.nextLong();
		long l=0;
		long price=0;
		Map<Long,Long> map = new HashMap<>();
		for(int i=0;i<n;i++) {
				long key= sc.nextLong();
				long value = sc.nextLong();
				if(map.containsKey(key)) {
			map.put(key,value+map.get(key));
				}else {
					map.put(key,value);
				}
		}
		List<Long> sortedKeys = new ArrayList(map.keySet());
		Collections.sort(sortedKeys);
	
		for( long nkey: sortedKeys) {
			long k=map.get(nkey);
			m-=k;
			if(m>0) {
			l+=k*nkey;
			}else{
				l+=nkey*(m+k);
				System.out.println(l);
				break;
			}


		}
    }

}


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

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

//#define doutnl(args...) cout<<args
#define doutnl(...)
#define dout(args...) doutnl(args<<endl;)
#define dprintl(args...) dout("D:"<<__LINE__<<": " args)
#define dv(v) <<#v<<"="<<(v)<<"; "
typedef long long ll;

vector<pair<ll,ll> > ts;

int n;
int main(){
	while(true){
		ts.clear();
		cin>>n;
		if(n==0) break;
		REP(i,n){
			ll m,a,b;
			cin>>m>>a>>b;
			ts.push_back(pair<ll,ll>(a,m));
			ts.push_back(pair<ll,ll>(b,-m));
			
		}
		sort(ts.begin(),ts.end());
		ll w=0;
		bool flag=false;
		REP(i,ts.size()){
			w+=ts[i].second;
			if(i!=ts.size()-1&&ts[i].first!=ts[i+1].first){
				dprintl(dv(i)dv(ts[i].first)dv(ts[i].second)dv(w));
				if(w>150){flag=true;break;}
			}
		}
		cout<<(flag?"NG":"OK")<<endl;
	}
		
	return 0;
}

Measured memory_bytes: 1208
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }

using namespace std;

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

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */
int dp[100010];
int main(){
    int n, q;
    string s;
    cin >> n >> q >>s;
    reps(i, n -1){
        if(s[i-1] == 'A' && s[i] == 'C'){
            dp[i] = dp[i-1] + 1;
        }else{
            dp[i] = dp[i-1];
        }
    }
    int l,r;
    rep(i, q){
        cin >> l >> r;
        cout << dp[r-1] - dp[l-1] << endl;
    }

}



Measured memory_bytes: 1472
N,K,*A=map(int,open(0).read().split())
for _ in range(K):
  B=[0]*(N+1)
  for i in range(N):
    B[max(0,i-A[i])]+=1
    B[min(N,i+A[i]+1)]-=1
  for i in range(N):B[i+1]+=B[i]
  if A==B:break
  A=B
print(*A[:-1])

Measured memory_bytes: 162276
#include <iostream>
 using namespace std;
  int main(){
   int A,B,C,D;
    cin>>A>>B>>C>>D;
     int X=(A+D-1)/D;
      int Y=(C+B-1)/B;
       cout<<(X>=Y?"Yes":"No")<<"\n";

      return 0;
  }


Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<double> dvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    set<string> st;
    rep(i,10){
        rep(j,10){
            rep(k,10){
                vector<bool> ok(3,0);
                rep(l,n){
                    if(s[l]-'0'==i&&!ok[0]){
                        ok[0]=1;
                        continue;
                    }else if(s[l]-'0'==j&&ok[0]&&!ok[1]){
                        ok[1]=1;
                        continue;
                    }else if(s[l]-'0'==k&&ok[0]&&ok[1]&&!ok[2]){
                        ok[2]=1;
                        continue;
                    }
                }
                if(ok[0]&&ok[1]&&ok[2]){
                    string t;
                    t+=to_string(i);
                    t+=to_string(j);
                    t+=to_string(k);
                    st.insert(t);
                }
            }
        }
    }
    cout<<st.size()<<endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
#define INF 2147483647

struct edge{
	int to,cost;
};
int V,E; 

vector <edge> G[100010];

multimap <int,int> l;


ll d[500010];


void dijkstra(int s){
	fill(d,d+V,INF);
	d[s] = 0;
	
	l.insert(make_pair(0,s));
	
	while(l.size() > 0){
		int p = l.begin()->first;
		int v = l.begin()->second;
		l.erase(l.begin());
		
		if(d[v] < p) continue;
		
		for(int i = 0;i < G[v].size(); i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				l.insert(make_pair(d[e.to], e.to));
			}
		}
	}
}


int main(){
	
	int r;
	cin >> V >> E >> r;
	for(int i = 0;i < E; i++){
		 edge e;
		int from;
		cin >> from >> e.to >> e.cost;
		G[from].push_back(e);
	}
	
	dijkstra(r);
	
	for(int i = 0;i < V; i++){
		if(d[i] != INF) cout << d[i] << endl;
		else cout << "INF" <<endl;
	}
	return 0;
} 


Measured memory_bytes: 15876
s = list(map(int, input().split()))

sunuke = []
ans = 0
for n in range(s[0]):
  sunuke.append(0)
for n in range(s[1]):
  d = input()
  a = list(map(int, input().split()))
  for n2 in a:
    sunuke[n2-1] += 1
for n in sunuke:
  if n == 0:
    ans += 1
print(ans)

Measured memory_bytes: 9188
#include <iostream>
#include <string>
#define ll long long
using namespace std;

ll mod=1000000007, dp[10010][110][2];

int main() {
	string K;
	int D;
	cin >> K >> D;
	dp[0][0][0]=1;
	for(int i=0; i<K.size(); ++i){
	    for(int j=0; j<D; ++j){
	        for(int r=0; r<10; ++r){
	            dp[i+1][(j+r)%D][1]=(dp[i+1][(j+r)%D][1]+dp[i][j][1])%mod;
	            if(r<K[i]-'0') dp[i+1][(j+r)%D][1]=(dp[i+1][(j+r)%D][1]+dp[i][j][0])%mod;
	            if(r==K[i]-'0') dp[i+1][(j+r)%D][0]=(dp[i+1][(j+r)%D][0]+dp[i][j][0])%mod;
	        }
	    }
	}
	cout << (dp[K.size()][0][0]+dp[K.size()][0][1]+mod-1)%mod << endl;
	return 0;
}


Measured memory_bytes: 17408
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}
  
  

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



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

using namespace std;

const int N = 100007;
vector<int> len;
vector<vector<int>> ed;

int dfs(int u) {
  if (len[u] != 0) return len[u];
  else if (ed[u].empty()) return 0;
  for (int v : ed[u]) {
    len[v] = dfs(v);
    len[u] = max(len[u], 1 + len[v]);
  }
  return len[u];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  len = vector<int>(n + 1, 0);
  ed = vector<vector<int>>(n + 1, vector<int>());
  int u, v;
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    ed[u].push_back(v);
  }
  int mx = 0;
  for (int u = 1; u <= n; u++) {
    if (len[u] == 0) {
      dfs(u);
    }
    mx = max(mx, len[u]);
  }
  printf("%d\n", mx);
  return 0;
}

Measured memory_bytes: 8192
#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<string>
using namespace std;
#define nl endl
#define in cin
#define out cout
#define ll long long
//sort(y,y+j, greater<int>());
ll x[1000000];
int main()
{
    ll a,b,c,d,e,i,j,k=0,n,sq,mul,r;
    char s[10000];
    in>>a;d=0;e=0;
    for(i=0;i<a;i++)
    {
        in>>b>>c;
        if(b==c)
        {
            d++;
        }
        else
        {
            d=0;
        }
        k=max(k,d);
    }
    //out<<k<<nl;
    if(k>2)out<<"Yes"<<nl;
    else out<<"No"<<nl;
}


Measured memory_bytes: 3620
# ABC125C - GCD on Blackboard
from fractions import gcd


def segfunc(x, y):  # modify for each case
    return gcd(x, y)


class SegmentTree:
    def __init__(
        self,
        init_val: "initial value: Array or str",
        ide_ele: "identity element corresponding init_val" = 0,
    ):
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.ide_ele = ide_ele
        self.tree = self._build(init_val)

    def _build(self, init_val: "Array or str"):
        tree = [self.ide_ele] * (2 * self.size)

        for idx, val in enumerate(init_val):  # set
            # modify val if needed (e.g. str -> ord())            
            tree[idx + self.size - 1] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[2 * idx + 1], tree[2 * idx + 2])
        return tree

    def update(self, idx: int, val):
        idx += self.size - 1
        # modify val if needed as same as in _build()
        self.tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.tree[idx] = segfunc(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, left: int, right: int):
        if left >= right:
            return self.ide_ele

        left += self.size
        right += self.size
        ret = self.ide_ele
        while left < right:
            if left & 1:
                ret = segfunc(ret, self.tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                ret = segfunc(ret, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


def main():
    N, *A = map(int, open(0).read().split())
    seg = SegmentTree(A)
    ans = 0
    for i in range(N):
        ans = max(ans, gcd(seg.query(0, i), seg.query(i + 1, N)))
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 16140
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())
#define DEBUG

using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;
typedef pair<long,long> pr;
typedef map<double,pr> mp;
typedef long long LL;


LL A, B;


int main ()
{
    cin >> A >> B;
    if (A > 2 && B > 2){
        cout << A * B - A * 2 - B * 2 + 4;
    }
    else if(A == 2 || B == 2){
        cout << 0;
    }
    else if(A == 1 && B == 1){
        cout << 1;
    }
    else {
        cout << A * B - 2;
    }
    return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())
x = tx - sx
y = ty - sy

lst = []
lst.append("U" * y)
lst.append("R" * x)
lst.append("D" * y)
lst.append("L" * (x + 1))
lst.append("U" * (y + 1))
lst.append("R" * (x + 1))
lst.append("D")
lst.append("R")
lst.append("D" * (y + 1))
lst.append("L" * (x + 1))
lst.append("U")
print("".join(lst))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fr(i,a) for(i=0;i<a;i++)
#define pb push_back
using namespace std;
main()
{
	unsigned long long x,y,a,b,c,i,p,s=0;
	vector<unsigned long long>red,grn,no;
	cin>>x>>y>>a>>b>>c;
	fr(i,a){
		cin>>p;
		red.pb(p);
	}
	fr(i,b){
		cin>>p;
		grn.pb(p);
	}
	fr(i,c){
		cin>>p;
		no.pb(p);
	}
	sort(red.begin(),red.end(),greater<unsigned long long>());
	sort(grn.begin(),grn.end(),greater<unsigned long long>());
	sort(no.begin(),no.end(),greater<unsigned long long>());
	vector<unsigned long long>ans(no.begin(),no.end());
	fr(i,y){
		ans.pb(grn[i]);
	}
	fr(i,x){
		ans.pb(red[i]);
	}
	sort(ans.begin(),ans.end(),greater<unsigned long long>());
	fr(i,x+y) s+=ans[i];
	cout<<s<<'\n';
}

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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  long long k;
  cin >> n >> k;
  vector<int> a(n), f(n);
  for(int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i < n; ++i) {
    cin >> f[i];
  }
  sort(a.rbegin(), a.rend());
  sort(f.begin(), f.end());

  auto ok = [&] (long long M) {
    multiset<int> s(f.begin(), f.end());
    long long needed = 0;
    for(int i = 0; i < n; ++i) {
      int x = a[i], y = f[i];
      needed += max(0LL, x - M / y);
    }
    return needed <= k;
  };

  long long lo = 0, hi = 1e13;
  while(lo != hi) {
    long long mid = (lo + hi) / 2;
    if(ok(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  cout << lo << '\n';
}

Measured memory_bytes: 14276
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

ll mod = 1e9 + 7;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m;
    cin >> n >> m;
    vll s(n), t(m);
    REP(i, n) cin >> s[i];
    REP(i, m) cin >> t[i];

    ll k = min(n, m);
    // s の i, t の j 文字目まで使う部分列の個数
    vvll dp(n + 1, vll(m + 1));
    dp[0][0] = 1;
    REP(i, n + 1){
        REP(j, m + 1){
            if(i) dp[i][j] += dp[i - 1][j];
            if(j) dp[i][j] += dp[i][j - 1];
            if(i && j && s[i - 1] != t[j - 1]) dp[i][j] += mod - dp[i - 1][j - 1];
            dp[i][j]%=mod;
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

Measured memory_bytes: 31616
#include <iostream>
#include <vector>

int main() {
    int N, W;
    std::cin >> N >> W;
    std::vector<int> weight(N+1);
    std::vector<long> value(N+1);
    for(int i = 1; i <= N; ++i) {
        std::cin >> weight[i] >> value[i];
    }
    std::vector<std::vector<long>> dp (N+1, std::vector<long>(W+1));
    for(int i = 0; i <= N; ++i) {
        dp[i][0] = 0;
    }
    for(int i = 0; i <= W; ++i) {
        dp[0][i] = 0;
    }
    for(int j = 1; j <= W; ++j) {
        for(int i = 1; i <= N; ++i) {
            if(j-weight[i] >= 0) {
                dp[i][j] = std::max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    std::cout << dp[N][W] << "\n";
    return 0;
}

Measured memory_bytes: 83192
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int A_price = int.Parse(input[0]);
        int B_price = int.Parse(input[1]);
        int AB_price = int.Parse(input[2]);
        int X = int.Parse(input[3]);
        int Y = int.Parse(input[4]);

        int a; int b;
        int cost; int minCost = 0;

        for(int ab=0; ab <= Math.Max(X, Y)*2; ab+=2){
            a = Math.Max(X - ab / 2, 0);
            b = Math.Max(Y - ab / 2, 0);

            cost = ab * AB_price + a * A_price + b * B_price;
            if(minCost==0 || cost < minCost){
                minCost = cost;
            }
        }

        Console.WriteLine(minCost);
    }
}

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

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

    vector<long long> X(M);
    for (int i = 0; i < M; i++)
        cin >> X[i];
    sort(X.begin(), X.end());

    vector<long long> Y(M-1);
    for (int i = 0; i < M-1 ; i++)
        Y[i] = X[i+1] - X[i];

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

    long long ans =0;
    while(M > N)
    {
        
        for (int i = 0; i < Y.size() - (N-1) ; i++)
            ans+= Y[i];
        cout << ans << endl;
        return 0;

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

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

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

using LL = long long int;
using LD = long double;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

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

	int n;
	while (cin >> n) {
		if (n == 0) break;

		map<int, LL> mp;
		queue<int> que;
		vb d(4001);
		for (int i = 0; i < n; i++) {
			int e;
			LL p, q;
			cin >> e >> p >> q;

			if (!d[e]) {
				que.push(e);
				d[e] = true;
			}

			mp[e] += p * q;
		}

		queue<int> ans;
		while (!que.empty()) {
			if (mp[que.front()] >= 1000000) {
				ans.push(que.front());
			}
			que.pop();
		}

		if (ans.empty()) {
			cout << "NA" << endl;
		} else {
			while (!ans.empty()) {
				cout << ans.front() << endl; ans.pop();
			}
		}
	}
	return 0;
}

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

int main(){
  int n,d;
  cin >> n >> d;
  int x,y;
  int count=0;
  for(int i=0;i<n;i++){
    cin >> x >> y;
    if(sqrt(pow(x,2)+pow(y,2)) <= d){
      count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional>
#include <map>
#include <set>

#define INF 1000000000;
#define MOD 1000000007;
typedef long long ll;
using namespace std;

int main()
{
    int N; cin >> N;
    ll ans = 0;
    if (N % 2 == 0) {
        ans = N;
    }
    else {
        ans = N * 2;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
import itertools
import heapq

V, E, R = [int(_) for _ in input().split()]
r = [int(_) - 1 for _ in input().split()]  # 0-indexed
G = {}
for i in range(V):
    G[i] = {}
    G[i][i] = 0

for _ in range(E):
    s, t, c = [int(_) for _ in input().split()]
    s -= 1  # 0-indexed
    t -= 1  # 0-indexed
    G[s][t] = c
    G[t][s] = c

INF = float('inf')

Ds = []
for r_index in range(R):
    que = []
    d = 0
    i = r[r_index]
    D = [INF] * V
    D[i] = 0
    used = [False] * V
    used[i] = True

    while True:
        for j in G[i].keys():
            heapq.heappush(que, (d + G[i][j], j))
        v = -1
        while que:
            d, j = heapq.heappop(que)
            if not used[j]:
                v = j
                break
        if v == -1:
            break
        else:
            used[v] = True
            D[v] = d
            i = v
    Ds += [D]
ans = INF
for array in itertools.permutations(range(R), R):
    d = 0
    for i in range(R - 1):
        d += Ds[array[i]][r[array[i + 1]]]
    ans = min(ans, d)
print(ans)

Measured memory_bytes: 10684
#include<bits/stdc++.h>
using namespace std;
int n,ans;
//1~9 100~999 10000~99999 100000
int main(){
	cin>>n;
	if(n<=9){printf("%d",n);return 0;}
	ans+=9;
	if(n<=999){printf("%d",ans+max(0,n-100+1));return 0;}
	ans+=900;
	if(n<=99999){printf("%d",ans+max(0,n-10000+1));return 0;}
	ans+=90000;
	printf("%d",ans);
} 

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

candidates = []
even = []
odd = []
for i in range(1, N+1):
    if i % K == 0:
        even.append(i)
        continue
    
    if K % 2 == 0 and i % (K // 2) == 0:
        odd.append(i)
        continue
    
count = len(even) ** 3

if K % 2 == 0:
    count += len(odd) ** 3
    
print(count)

Measured memory_bytes: 11036
#include <stdio.h>
#include <string.h>
 
int main(void){
  char s[1001], order[8], ch[1001];
  int i, j, n, x, y;
 
  scanf("%s\n%d", s, &n);
 
  for(i=0;i<n;i++){
    scanf("%s %d %d", order, &x, &y);
     
    if(!strcmp(order, "reverse")){
      for(j=x;j<=y;j++)
        ch[y-j] = s[j];
      for(j=x;j<=y;j++)
        s[j] = ch[j-x];
    }
 
    if(!strcmp(order, "replace")){
      scanf("%s", ch);
      for(j=0;ch[j]!='\0';j++)
        s[x+j] = ch[j];
    }
 
    if(!strcmp(order, "print")){
      for(j=x;j<=y;j++)
        printf("%c", s[j]);
      printf("\n");
    }
  }
 
  return 0;
}


Measured memory_bytes: 2112
n=input()
if int(n[-1]) == 2 or int(n[-1]) == 4 or int(n[-1]) == 5 or int(n[-1])==7 or int(n[-1])==9:
    print('hon')
elif int(n[-1]) == 3:
    print('bon')
else:
    print('pon')

Measured memory_bytes: 9180