akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    ll x, y; cin >> x >> y;

    int ans = 0;
    while (x <=y)
    {
        ans++;
        x *=2;
    }
    
    OUT(ans)

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<ll,ll>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

////////// 二項係数(N<=10^7) //////////

ll fac[MAX],finv[MAX],inv[MAX];
// fac[i] i!
// finv[i] i!の逆元
// inv[i] iの逆元

// テーブルを作る前処理
void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(ll i=2; i<MAX; ++i){
    fac[i]=fac[i-1]*i%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

// 二項係数計算
ll COM(ll n,ll k){
  if(n<k) return 0;
  if(n<0 || k<0) return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

//////////////////////////////////////////////////

int main(){
  ll N,K,ans=0;
  cin>>N>>K;
  
  COMinit();
  for(int i=0; i<=min(N-1,K); ++i){
    ans+=COM(N,i)*COM(N-1,i)%MOD;
    ans%=MOD;
  }
  
  co(ans);
  return 0;
}

Measured memory_bytes: 123164
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

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

    public void solve(String[] args) {
        MyScanner scanner = new MyScanner();
        int[] list = new int[3];
        list[0] = scanner.nextInt();
        list[1] = scanner.nextInt();
        list[2] = scanner.nextInt();
        Arrays.sort(list);
        int cost = list[2] - list[1];
        cost += list[1] - list[0];
        System.out.println(cost);
    }

    private class MyScanner {
        String[] s;int i;BufferedReader br;String reg = " ";
        MyScanner () { s = new String[0];i = 0;br = new BufferedReader(new InputStreamReader(System.in)); }
        public String next() {
            try {
                if (i < s.length) return s[i++]; String line = br.readLine();
                while (line.equals("")) {line = br.readLine();}
                s = line.split(reg, 0); i = 0;return s[i++];
            } catch (Exception e) {e.printStackTrace();}
            return null;
        }
        public int nextInt() {
            try {return Integer.parseInt(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public double nextDouble() {
            try {return Double.parseDouble(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
        public long nextLong()  {
            try {return Long.parseLong(next());} catch (Exception e) {e.printStackTrace();}
            return -1;
        }
    }
}


Measured memory_bytes: 21204
import java.io.*; 
import java.util.*; 
  
class Graph { 
    ArrayList<Integer> adjArr[];
  
    @SuppressWarnings("unchecked")
	Graph(int v) {
        adjArr = new ArrayList[v]; 
        for (int i=0; i < v; ++i) 
            adjArr[i] = new ArrayList<Integer>(); 
    } 
  
    // Add directed pair to graph
    void addToGraph(int id, int neighbor) { 
    	adjArr[id].add(neighbor); 
    	}
    
    // Topologically sorts adjacency list graph into a stack
    void topsort(int v, boolean visited[], Stack<Integer> stack) {  
        // Mark current as visited
    	visited[v] = true; 
        int i; 

        Iterator<Integer> it = adjArr[v].iterator(); 
        while (it.hasNext()) { 
            i = it.next(); 
            // Topsort through all unvisited adjacent vertices before adding to stack
            if (!visited[i]) 
                topsort(i, visited, stack); 
        } 
        stack.push(v); 
    }
}

public class Main {
  
    public static void main(String args[]) 
    { 
    	Scanner in = new  Scanner(System.in);

		int totalVertex = in.nextInt();
		Graph adj = new Graph(totalVertex);
		
		int totalConnections = in.nextInt();
		
		int id, neighbor;
		
		for (int i = 0; i < totalConnections; i++) {
			id = in.nextInt();
			neighbor = in.nextInt();
			adj.addToGraph(id, neighbor);
		}
		
		Stack<Integer> stack = new Stack<Integer>();
		
		boolean[] visited = new boolean[totalVertex];
		// Initialize visited array with false
		for(int i = 0; i < totalVertex; i++){
			visited[i] = false;
		}
		
		for(int i = 0; i < totalVertex; i++) {
			if(!visited[i]) {
				adj.topsort(i, visited, stack);
			}
		}
		
		while(!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
    }
}


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

int main() {
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    for (int i = 0; i < m; i++)
    {
        ll a;
        cin >> a;
        ans += a;
    }
    ll remain = n - ans;
    if (remain >= 0)  cout << remain;
    else  cout << -1;
    return 0;
}

Measured memory_bytes: 3624
#include<iostream>

using namespace std;
int n, a[109];

void printCards(){
  for(int i=0;i<n;i++)cout << a[i] << (i<n-1?' ': '\n');
}

void insertSort(){
  printCards();
  for(int i=1;i<n;i++){
    int key = a[i];
    int j=i-1;
    while(j>=0 && a[j] > key){
      a[j+1] = a[j];
      j--;
    }
    a[j+1] = key;
    printCards();
  }
}

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


Measured memory_bytes: 3092
def factorial_mod(n,mod):
    ret = 1
    for i in range(1,n+1):
        ret *= i
        ret %= mod
    return ret
def comb_mod(n,r,mod):
    if r > n or r < 0:
        ret = 0
    else:
        fact_n  = factorial_mod(n, mod)
        fact_r  = factorial_mod(r, mod)
        fact_nr = factorial_mod(n-r, mod)
        ret = fact_n * pow(fact_r, mod-2, mod) * pow(fact_nr, mod-2, mod) % mod
    return ret

n,k = map(int,input().split())
m = 10**9+7
for i in range(1,k+1):
    print(comb_mod(n-k+1, i, m)*comb_mod(k-1, i-1, m)%m)

Measured memory_bytes: 74680
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define clear(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

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

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



int main()
{
	int n, m, p, a, b, uma[16];
	while (cin >> n >> m >> p >> a >> b, n)
	{
		--a, --b;
		for (int i = 0; i < n; ++i)
			cin >> uma[i];
		vector<pint> edge[32];
		for (int i = 0; i < p; ++i)
		{
			int x, y, z;
			cin >> x >> y >> z;
			--x, --y;
			edge[x].push_back(pint(y, z));
			edge[y].push_back(pint(x, z));
		}

		const double INF = 1e19;
		static double dp[1 << 8][32];
		for (int i = 0; i < 1 << n; ++i)
			for (int j = 0; j < 30; ++j)
				dp[i][j] = INF;
		dp[0][a] = 0;
		for (int s = 0; s < 1 << n; ++s)
		{
			for (int i = 0; i < 30; ++i)
			{
				foreach (it, edge[i])
				{
					int to = it->first, len = it->second;
					for (int j = 0; j < n; ++j)
					{
						if (!(s >> j & 1))
							min_swap(dp[s | (1 << j)][to], dp[s][i] + (double)len / uma[j]);
					}
				}
			}
		}
		double res = INF;
		for (int i = 0; i < 1 << n; ++i)
			min_swap(res, dp[i][b]);
		if (res == INF)
			cout << "Impossible" << endl;
		else
			cout << res << endl;
	}
}

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

static const int N=100;
static const int WHITE=0;//未訪問の頂点
static const int GRAY=1;//訪問した頂点
static const int BLACK=2;//２度目の訪問になる頂点

int n, M[N][N];
int color[N],d[N],f[N],tt;
int nt[N];

//uに隣接するvを番号順に取得
int next(int u){
    for (int v=nt[u]; v<n; v++){
        nt[u]=v+1;
        if(M[u][v]) return v;
    }
    return -1;
}

//スタックを用いた深さ優先探索
void dfs_visit(int r){
    for(int i=0; i<n; i++) nt[i]=0;
    
    stack<int> S;
    S.push(r);
    color[r]=GRAY;
    d[r]=++tt;//ｒ頂点の発見時刻
    
    while(!S.empty()){
        int u=S.top();
        int v=next(u);
        if(v!=-1){
            if(color[v]==WHITE){
                color[v]=GRAY;
                d[v]=++tt;
                S.push(v);
            }
        }else{
            S.pop();
            color[u]=BLACK;
            f[u]=++tt;//u頂点の終了時刻
        }
    }
}

void dfs(){
    //初期化
    for (int i=0; i<n; i++){
        color[i]=WHITE;
        nt[i]=0;
    }
    tt=0;
    
    //未訪問のuを始点として深さ優先探索
    for (int u=0; u<n; u++){
        if(color[u]==WHITE) dfs_visit(u);
    }
    for (int i=0; i<n; i++){
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main(){
    int u,k,v;
    cin >> n;
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++) M[i][j]=0;
    }
    
    for (int i=0; i<n; i++){
        cin >> u >> k;
        u--;
        for (int j=0; j<k; j++){
            cin >> v;
            v--;
            M[u][v]=1;
        }
    }
    dfs();
    return 0;
}


Measured memory_bytes: 3144
# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


# 入力速度を速める

class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


# ケーキの美味しさの合計とそのときの組み合わせ
# heapqで比較できるようにltを作る

X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))
# 降順ソート

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1
# 各リストの初項を合計すると美味しさ最大の組み合わせになる
# heapqは最小をheappopするので、
# 符号反転させて、最大が出るようにする
# ただし、print時に再度符号反転必要

d = Data(t, (0, 0, 0))
heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))
# 1,2,3のキャンドルのインデックスの追加量のタプルのリスト
# ループを回し、順番に美味しさの合計が大きい組み合わせの美味しさ合計を出力する
# その後、出力した合計から、
# 1,2,3の形のキャンドルつきのケーキのインデックスのうち
# 一つのインデックスを１増やしたもの（最大3通り）を
# heapqに追加する

st = set()
# ケーキの組み合わせタプルで既出なものを貯めておく集合

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue
        # 1,2,3のインデックスのどれかが用意された種類数を超えていたら、
        # そのインデックスの組み合わせはありえないので、次の候補に移る
        ntpl = (na, nb, nc)
        if ntpl in st: continue
        # 既にheapqに追加済みの組み合わせは、重複追加しないで、次の候補に移る

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1
        # 美味しさの合計は符号反転させる
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
        # heapqに追加済みなので、集合にaddする
   

Measured memory_bytes: 5352
N, W = map(int, input().split())
wv = [tuple(map(int, input().split()))for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if 0 <= j-wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
        dp[i][j] = max(dp[i-1][j], dp[i][j])

print(dp[-1][-1])

Measured memory_bytes: 120940
#include <iostream>
#include<cmath>

using namespace std;

struct coo {
    int x;
    int y;
    int h;
} coo_list[101];

int main(int argc, const char * argv[]) {
    int N;
    int H;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> coo_list[i].x >> coo_list[i].y >> coo_list[i].h;
    }
    int h_i = 0;
    while (coo_list[h_i].h <= 0) h_i++; // if h is 0, we cannot judge the thing at the left of max is below 0 or not
    for (int x_i = 0; x_i < 101; x_i++)
        for (int y_i = 0; y_i < 101; y_i++) {
//            if (x_i == 100 && y_i == 0)
//                cout << "check";
            H = coo_list[h_i].h + abs(y_i - coo_list[h_i].y) + abs(x_i - coo_list[h_i].x);
            if (H < 1)
                continue;
            bool ok_flag = true;
            for(int coo_i = 0; coo_i < N; coo_i++) {
                int hhh = max(H - abs(x_i - coo_list[coo_i].x) - abs(y_i - coo_list[coo_i].y), 0);
                if (coo_list[coo_i].h != hhh) {
                    ok_flag = false;
                    break;
                }
                else
                    continue;
            }
            if (ok_flag == true)
            {
                cout << x_i << ' ' << y_i << ' ' << H << endl;
                return 0;
            }
            else
                continue;
        }
    return 0;
}


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

using namespace std;

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

  vector<int>L(N+1);

  for(int i=0;i<N;i++){
    cin >> L[i];
  }

  vector<int> D(N+1);
  D[0]=0;
  for(int i=1;i<N+1;i++){
    D[i]=D[i-1]+L[i-1];
  }
  int ans=0;
  for(int i=0;i<N+1;i++){
    if(D[i]<=X){
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>


#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;

vector<int> a;


int main(void){
    int n;
    cin >> n;
    a.resize(n);
    for(auto &b: a) cin >> b;
    vector<int> b = a;
    sort(b.begin(), b.end());

    int x = b[n-1];
    int ans = b[0];
    for(int i = 1; i < n-1; ++i){
        if(fabs((double)x/2 - ans) > fabs((double)x/2 - b[i])){
            ans = b[i];
        }
    }

    cout << x << " " << ans << endl;


    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
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;}
const int mod = 1000000007;

int v[3005][3005];
ll dp[3005][3005][5];

int main() {
    int r,c,k;
    cin >> r >> c >> k;
    rep(i,k) {
        int a,b;
        cin >> a >> b;
        a--;b--;
        int c;
        cin >> c;
        v[a][b] = c;
    }
    dp[0][0][1] = v[0][0];
    rep(i,r) rep(j,c) rep(l,4) {
        chmax(dp[i][j+1][l+1],dp[i][j][l]+v[i][j+1]); // 右に移動して選ぶ
        chmax(dp[i][j+1][l],dp[i][j][l]); // 右に移動して選ばない

        chmax(dp[i+1][j][1],dp[i][j][l]+v[i+1][j]); //下に移動して選ぶ
        chmax(dp[i+1][j][0],dp[i][j][l]); // 下に移動して選ばない
    }
    ll ans = 0;
    rep(i,4) chmax(ans,dp[r-1][c-1][i]);
    cout << ans << endl;
}

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  bool flg = false;
  if(a==b && b!=c) flg=true;
  if(a==c && b!=c) flg=true;
  if(b==c && a!=c) flg=true;
  
  if(flg) puts("Yes");
  else puts("No");
}

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

int set(int *arr, int n){
	for(int i = 1; i <= n; i++){
		arr[i] = i;
	}
}

int main(){
	int arr[50];
	int a, b;
	cin >> a >> b;
	set(arr, a);
	int x, y;
	for(int i = 0; i < b; i++){
		scanf("%d,%d", &x, &y);
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}
	for(int i = 1; i <= a; i++){
		cout << arr[i] << endl;
	}
}


Measured memory_bytes: 3140
import sys
 
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0) and (A[j] > v):
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v
 
def shellSort(A, n):
    G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m = len(G)
    for k in range(m):
        insertionSort(A, n, G[k])
    return m, G
 
A = list(map(int, sys.stdin))
n = A[0]
del A[0]
 
cnt = 0
 
m, G = shellSort(A, n)
 
print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))


Measured memory_bytes: 125972
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        HashMap<Long, Integer> map = new HashMap<>();
        map.put(0L, 1);

        long sum = 0;
        for (int i = 1; i < N+1; i++) {
            sum += A[i-1];
            sum %= M;

            if (map.containsKey(sum)) {
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }
        }

        long ret = 0;
        for (long value : map.values()) {
            if (value == 1) {
                continue;
            }

            ret += value * (value - 1) / 2;
        }

        System.out.println(ret);
    }
}

Measured memory_bytes: 54060
N = int(input())
integers = [int(n) for n in input().split()]
absolute_integers = [abs(n) for n in integers]

negatives = [n for n in integers if n < 0]

if 0 in integers:
    result = sum(absolute_integers)
elif len(negatives)%2 == 0:
    result = sum(absolute_integers)
else:
    result = sum(absolute_integers) -2 * min(absolute_integers)

print(result)


Measured memory_bytes: 14412
n = int(input())
b = 1 << (n.bit_length()-1)
if n - b == 0:
  print("No")
else:
  print("Yes")
  print(1, 2)
  print(2, 3)
  print(3, n+1)
  print(n+1, n+2)
  print(n+2, n+3)
  for i in range(4, n, 2):
    print(i, i+1)
    print(i+n, i+n+1)
    print(1+n, i+n)
    print(1+n, i+1)
  if (~n)&1:
    print(n, b+n)
    a = n ^ b ^ 1
    print(n+n, a)

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

namespace TYC
{
	typedef pair<int, int> pii;
	const int N = 3005;

	inline bool operator < (const string &a, const string &b)
	{
		int la = int(a.size()), lb = int(b.size()), l = min(la, lb);
		for (int i = 0; i < l; i++)
			if (a[i] != b[i])
				return a[i] < b[i];
		return la < lb;
	}

	void solve(string &S)
	{
		string ans;
		int len = int(S.size());
		if (S[0] == 'a')
		{
			static int A[N], B[N];
			for (int i = 0, a = 0, b = 0; i < len; i++)
				(S[i] == 'a' ? A[++a] : B[++b]) = i;
			for (int i = 1, c = len >> 1, p = 0; i <= c; i++)
				if (A[i] >= p)
					ans += "ab", p = B[i] + 1;
		}
		else
		{
			while (len)
			{
				ans = max(ans, S); 
				S[0] = '#';
				for (int i = 1; i < len; i++)
					if (S[i] == 'a')
					{
						S[i] = '#';
						break;
					}
				for (int i = 0, j = 0; i < len; i++)
					if (S[i] != '#')
						S[j++] = S[i];
				len -= 2;
				S.resize(len);
			}
		}
		S = ans;
	}

	void work()
	{
		ios::sync_with_stdio(false);
		cin.tie(0);
		static string S[N], Str;
		int n, tot = 1;
		cin >> n >> Str;
		for (int i = 0, c = 0; i < (n << 1); i++)
		{
			S[tot] += Str[i];
			c += Str[i] == 'a' ? 1 : -1;
		   	if (!c)
				++tot;
		}	
		for (int i = 1; i <= tot; i++)
			solve(S[i]);
		string ans;
		for (int i = tot; i; i--)
			ans = max(ans, S[i] + ans);
		cout << ans << '\n';
	}
}

int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 101010
	#define mod 1000000007ll
	typedef long long ll;
	typedef double db;
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
}
using namespace my_std;

int n,X;
int a[sz];

ll dp[233][sz][2];

int main()
{
	read(n,X);
	rep(i,1,n) read(a[i]);
	sort(a+1,a+n+1,[](const int &x,const int &y){return x>y;});
	dp[0][X][1]=1;
	rep(i,1,n) 
	{
		rep(j,0,X) dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])*(n-i)%mod;
		rep(j,0,X) (dp[i][j%a[i]][1]+=dp[i-1][j][0]+dp[i-1][j][1])%=mod;
	}
	ll ans=0;
	rep(i,0,X) (ans+=dp[n][i][1]*i%mod)%=mod;
	cout<<ans;
	return 0;
}

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

public class Test
{
	public static void Main()
	{
		var s = Console.ReadLine().Split(' ');
		var a = int.Parse(s[0]);
		var b = int.Parse(s[1]);
		var k = int.Parse(s[2]);
		var e = null as IEnumerable<int>;
		if(b - a < k)
			e = Enumerable.Range(a, b - a + 1);
		else
			e = Enumerable.Range(a, k)
				.Union(Enumerable.Range(b - k + 1, k));
		foreach(var i in e)
		{
			Console.WriteLine(i);
		}
	}
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;

int main(){
    string S; cin >> S;
    if(S[2] == S[3] && S[4] == S[5]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
// ABC164-D
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

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

    string s;
    cin>>s;
    int l=s.size();
    vector<int> r(2019,0);
    r[0]=1; //a=0のとき
    int mod=2019;
    ll now=0;
    ll ten=1;
    rep(i,l){
        int num=s[l-(i+1)]-'0'; 
        now+=num*ten%mod;
        now%=mod;
        r[now]+=1;
        ten*=10;
        ten%=mod;
    }
    ll ans=0;
    rep(i,2019){
        ans+=r[i]*(r[i]-1)/2;
    }
    cout<<ans<<endl;
    return 0;
}

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

int N;
int a[10000000];
int main() {
	cin >> N;
	int num = 0;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		num += a[i];
	}
	int ans = 0;
	double n = 100;
	double avarage = (double)num / (double)N;
	for (int i = 0; i < N; i++) {
		if (n > abs(a[i] - avarage)) {
			ans = i;
			n = abs(a[i] - avarage);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 764
K, N = map(int, input().split())
A = list(map(int, input().split()))
A.append(K)
B = 0
x = 1

for a in A:
  if A[x] == K:
    break
  elif A[x] - a > B:
    B = A[x] - a
  
  x += 1

C = K + A[0] - A[N-1]

if C == B:
  print(K - B)
elif C > B:
  print(K - C)
elif B > C:
  print(K - B)
  

Measured memory_bytes: 26444
s = list(input())
k = int(input())
lis = []
n = 1
for i in range(len(s)-1):
    if s[i] == s[i + 1]:
        n += 1
    else:
        lis.append(n)
        n = 1
lis.append(n)
if len(lis) == 1:
    print(len(s) * k // 2)
else:
    if s[0] == s[len(s) - 1]:
        if len(lis) >= 2:
            m = lis[0] // 2
            m = m + lis[len(lis)-1]//2
            m = m + (lis[0] + lis[len(lis)-1]) // 2 * (k - 1)
        if len(lis) >= 3:
            for i in range(len(lis) - 2):
                m = m + lis[i + 1] // 2 * k
        print(m)
    else:
        m = 0
        for i in range(len(lis)):
            m = m + lis[i] // 2 * k
        print(m)


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	final static long MOD = 1000000007L;
 
	public static void main(String[] args) {
		Reader in = new Reader();
		char[] s1 = in.next().toCharArray();
		char[] s2 = in.next().toCharArray();
		int n = s1.length;
		int m = s2.length;
		int[][] dp = new int[n+1][m+1];
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(s1[i]==s2[j]) dp[i+1][j+1] = dp[i][j]+1;
				else dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
			}
		}
		/*
		for(int i = 0; i<=n; i++) {
			for(int j = 0; j<=m; j++)
				System.out.print(dp[i][j]+" ");
			System.out.println();
		}
		*/
		int len = dp[n][m];
		int idx = 0;
		char[] ans = new char[len];
		int i = n; 
		int j = m;
		while(idx<len) {
			if(s1[i-1]==s2[j-1]) {
				ans[idx++] = s1[i-1];
				i--;
				j--;
			}else if(dp[i-1][j]>dp[i][j-1]) i--;
			else j--;
		}
		for(i = ans.length-1; i>=0; i--) System.out.print(ans[i]);
	}
 
	static class Reader {
		static BufferedReader br;
		static StringTokenizer st;
		private int charIdx = 0;
		private String s;
 
		public Reader() {
			this.br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		public int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public char nextChar() {
			if (s == null || charIdx >= s.length()) {
				if (st == null || !st.hasMoreTokens())
					try {
						readLine();
					} catch (Exception e) {
					}
				s = st.nextToken();
				charIdx = 0; 
			}
			return s.charAt(charIdx++);
		}
 
		public long[] nl(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
		public char[] nca() {
			return next().toCharArray();
		}
 
		public String[] nS(int n) {
			String[] a = new String[n];
			for (int i = 0; i < n; i++)
				a[i] = next();
			return a;
		}
 
		public int nextInt() {
			if (st == null || !st.hasMoreTokens())
				try {
					readLine();
				} catch (Exception e) {
				}
			return Integer.parseInt(st.nextToken());
		}
 
		public double nextDouble() {
			if (st == null || !st.hasMoreTokens())
				try {
					readLine();
				} catch (Exception e) {
				}
			return Double.parseDouble(st.nextToken());
		}
 
		public Long nextLong() {
			if (st == null || !st.hasMoreTokens())
				try {
					readLine();
				} catch (Exception e) {
				}
			return Long.parseLong(st.nextToken());
		}
 
		public String next() {
			if (st == null || !st.hasMoreTokens())
				try {
					readLine();
				} catch (Exception e) {
				}
			return st.nextToken();
		}
 
		public static void readLine() {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
			}
		}
	}
}

Measured memory_bytes: 83128
import sys
from itertools import accumulate
 
N, Q = map(int, input().split())
S = input()
 
t = [0] * N
 
for i in range(1, N):
    s = S[i-1:i+1]
    if s == 'AC':
        t[i] += 1

T = list(accumulate(t))
 
for i in range(Q):
    l, r = map(int, input().split())
    print(T[r-1] - T[l-1])

Measured memory_bytes: 8692
#include<stdio.h>
int main()
{
	int a,b,c,k,p,q,m=0;
	int i;
	scanf("%d%d%d%d",&a,&b,&c,&k);
	if(a>=b&&a>=c){
		p=a;
		q=b+c;
	}else if(a<=b&&b>=c){
		p=b;
		q=a+c;
	}else{
		p=c;
		q=a+b;
	}
	for(i=0;i<k;i++){
		p*=2;
	}
	printf("%d\n",p+q);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
  int h, w;
  
  while(1){
    scanf("%d %d", &h, &w);
    if(h==0 && w==0){
      break;
    }
    for(int i = 0; i < w; i++){
      printf("#");
    }
    printf("\n");
    for(int i = 0; i < h-2; i++){
      for(int j = 0; j < w; j++){
	if(j == 0 || j == w-1){
	  printf("#");
	}else{
	  printf(".");
	}
      }
      printf("\n");
    }
    for(int i = 0; i < w; i++){
      printf("#");
    }
    printf("\n\n");
  }
} 


Measured memory_bytes: 3132
#include<stdio.h>
int main( ){
  int i,j,N;
  int A[100],v;

  scanf("%d",&N);
  if(N<1 && N>100){
    printf("N value is over\n");
  }
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
 for(i=0;i<N;i++){
   if(i > 0){
     printf(" ");
   }
   printf("%d",A[i]);
 }
 printf("\n");
 
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while((j>=0)&&(A[j]>v)){
	A[j+1]=A[j];
	j--;
    }
	A[j+1]=v;
  
	for(j=0;j<N;j++){
	  if(j > 0){
	    printf(" ");
	  }
	    printf("%d",A[j]);
	  }
	
	printf("\n");
	}
  
 
  return 0;
}
      
      



Measured memory_bytes: 2052
import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)

Measured memory_bytes: 40348
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
		sc.close();
		long ans = 1;
		if (k <= a) {
			ans += k;
		} else {
			if (a < b - 1) {
				ans = a;
				k -= (a - 1);
				int tmp = k / 2;
				ans += ((long)(b - a)*(long)tmp);
				tmp = k % 2;
				ans += tmp;
			}
			else {
				ans += k;
			}
		}
		System.out.println(ans);
	}

}


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


int main(){
 int n,k;
  cin>>n>>k;
  vector<int> A(n);
  for(int i=0;i<n;i++)
    cin>>A[i];
  sort(A.begin(),A.end());
  int sum=0;
  for(int i=0;i<k;i++){
    sum+=A[i];
  }
  printf("%d\n",sum);
}

Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  int n,m;
  cin >> n >> m;
  bool red[n];
  int sum[n];
  rep(i,n) red[i]=false;
  red[0]=true;
  rep(i,n) sum[i]=1;
  //  white[0]=0;

  int x,y;
  rep(i,m){
    cin >> x >> y;
    x--;y--;
    sum[x]--;
    sum[y]++;
    if(red[x]==true) red[y]=true;
    if(sum[x]==0) red[x]=false;
  }
  int c=0;
  rep(i,n) if(red[i]==true) c++;
  cout << c << endl;

  return 0;

}


Measured memory_bytes: 768
#include<stdio.h>
#define N 2000
    int A[N],n;
int isSolved(int i,int k){
    int res;
    if(k==0) return 1;
    if(i>=n) return 0;
    res = isSolved(i+1,k) || isSolved(i+1,k-A[i]);
    return res;
}
int main(){
    int i,q,k;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&k);
        if(isSolved(0,k)==1) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

vector<ll> ss;

void dfs(ll s, int cnt){
    if (cnt==10) return;
    cnt++;
    ss.push_back(s);
    ll sita = s%10;
    ll tmp = s*10;
    if (sita == 9){
        dfs(tmp+8, cnt);
        dfs(tmp+9, cnt);
    }else if (sita == 0){
        dfs(tmp, cnt);
        dfs(tmp+1, cnt);
    }else{
        dfs(tmp+sita, cnt);
        dfs(tmp+sita+1, cnt);
        dfs(tmp+sita-1, cnt);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x;
    cin >> x;
    rep(i, 9){
        dfs(i+1, 0);
    }
    sort(ss.begin(), ss.end());
    // ss.erase(unique(ss.begin(), ss.end()), ss.end());
    cout << ss[x-1] << endl;
    return 0;
}

Measured memory_bytes: 2420
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] line = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
		String[] peaple = sc.nextLine().split("", 0);
		int lim = line[1] + line[2];
		int ab_con = 0;
		int b_con = 0;

		for (int i = 0; i < line[0]; i++) {
			//cはじく
			if (peaple[i].equals("c")) {
				System.out.println("No");
			} else if(peaple[i].equals("a")){
				//a
				if (ab_con <lim) {
					System.out.println("Yes");
					ab_con++;
				}else {
					System.out.println("No");
				}
			} else if(peaple[i].equals("b")) {
				//b
				if (ab_con <lim && b_con < line[2]) {
					System.out.println("Yes");
					ab_con++;
					b_con++;
				}else {
					System.out.println("No");
				}
			}
		}
	}
}


Measured memory_bytes: 61620
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N = ini()


def solve():
    k = 26
    a = k
    p = k
    l = 1
    while a < N:
        p *= 26
        a += p
        l += 1
    b = 1
    x = N - 1
    name = [None] * l
    for i in range(l):
        c = x % 26
        name[l - 1 - i] = chr(ord("a") + c)
        x //= 26
        x -= 1
    return "".join(name)


print(solve())


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

void solve()
{
    int x;
    cin>>x;
    cout<<!x<<endl;
}



main()
{
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
     
     int t;
     t=1;
     while(t--)
     {
         solve();
     }

}




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

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

	if (N % 4 == 0 || N % 7 == 0) {
		cout << "Yes" << endl;
	}
	else {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (4 * i + 7 * j == N) {
					cout << "Yes" << endl;
					return 0;
				}

			}
		}

		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=998244353;
int n;
LL ans,A,B,K,fac[500010],inv[500010];
LL pw(LL x,LL y){
	LL t=1;
	for (;y;y>>=1){
		if (y&1) t=t*x%MO;
		x=x*x%MO;
	}
	return t;
}
LL C(int x,int y){
	return fac[x]*inv[y]%MO*inv[x-y]%MO;
}
int main(){
	fac[0]=1;
	FOR(i,1,500000) fac[i]=fac[i-1]*i%MO;
	inv[500000]=pw(fac[500000],MO-2);
	FORD(i,499999,0) inv[i]=inv[i+1]*(i+1)%MO;
	cin>>n>>A>>B>>K;
	FOR(i,0,n){
		LL t=K-A*i;
		if (t<0) continue;
		if (t%B!=0) continue;
		LL j=t/B;
		if (j<0 || j>n) continue;
		(ans+=C(n,i)*C(n,j))%=MO;
	}
	ans=(ans%MO+MO)%MO;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 8064
import collections

n = input()
nums = list(map(int, input().split()))
odd = nums[0::2]
even = nums[1::2]
odd_c = collections.Counter(odd)
even_c = collections.Counter(even)


if odd_c.most_common(1)[0][0] == even_c.most_common(1)[0][0]:
    if len(odd_c) >= 3 and len(even_c) >= 3:
        odd_first_count = len(odd) - odd_c.most_common(1)[0][1]
        even_first_count = len(even) - even_c.most_common(1)[0][1]
        odd_second_count = len(odd) - odd_c.most_common(2)[1][1]
        even_second_count = len(even) - even_c.most_common(2)[1][1]
        if odd_first_count + even_second_count < odd_second_count + even_first_count:
            print(odd_first_count + even_second_count)
            exit()
        else:
            print(odd_second_count + even_first_count)
            exit()
    odd_next_most = 0
    even_next_most = 0
    if len(odd_c) >= 2:
        odd_next_most = odd_c.most_common(2)[1][1]
    if len(even_c) >= 2:
        even_next_most = even_c.most_common(2)[1][1]
    if odd_next_most > even_next_most:
        print(len(odd) - odd_next_most + len(even) - even_c.most_common(1)[0][1])
    else:
        print(len(odd) - odd_c.most_common(1)[0][1] + len(even) - even_next_most)
else:
    odd_change = len(odd) - odd_c.most_common(1)[0][1]
    even_change = len(even) - even_c.most_common(1)[0][1]
    print(odd_change + even_change)


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

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

  vector<int> a(n);
  int64_t sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  sort(a.begin(), a.end());
  int minimum = a.front();
  int maximum = a.at(n - 1);
  cout << minimum << " " << maximum << " " << sum << endl;
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

int main() {
    int H, W;
    cin>>H>>W;
    vector<string> grid(H);

    for (int i = 0; i < H; ++i) {
        cin>>grid[i];
    }
    /*
    vector<vector<int>> dp(H,vector<int>(W,(int)1e8));

    dp[0][0]=(grid[0][0]=='#')?1:0;

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if(i==0&&j==0) continue;
            int cmp1=(i>0)?dp[i-1][j]:1e8;
            int cmp2=(j>0)?dp[i][j-1]:1e8;
            dp[i][j]=(grid[i][j]=='#')?1:0;
            dp[i][j]+=min(cmp1,cmp2);
        }
    }
    if(dp[H-1][W-1]<2) {
        cout << dp[H - 1][W - 1] << endl;
        return 0;
    }
     */

    vector<vector<int>> dp2(H,vector<int>(W,(int)1e8));

    dp2[0][0]=(grid[0][0]=='#')?1:0;

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if(i==0&&j==0) continue;
            int cmp1=(i>0)?dp2[i-1][j]:1e8;
            cmp1+=(i>0&&grid[i-1][j]!=grid[i][j])?1:0;
            int cmp2=(j>0)?dp2[i][j-1]:1e8;
            cmp2+=(j>0&&grid[i][j-1]!=grid[i][j])?1:0;
            dp2[i][j]=min(cmp1,cmp2);
        }
    }
    int ans=dp2[H-1][W-1];
    //cout<<dp2[H-1][W-1]<<endl;
    if(ans==0){
        if(grid[0][0]=='#'||grid[H-1][W-1]=='#') cout<<1<<endl;
        else cout<<ans/2<<endl;
    }else if(ans==1){
        cout<<1<<endl;
    }else{
        cout<<(ans+1)/2<<endl;
    }
    //cout<<dp2[H-1][W-1]/2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using ll = unsigned long long;
using namespace std;

int main(void) {
    string s;
    cin >> s;

    if(s[0]!='A') {
        cout << "WA" <<endl;
        return 0;
    }

    if (!('a'<=s[1] && 'z' >= s[1])) {
        cout << "WA" <<endl;
        return 0;
    }

    if (!('a'<=s[s.size()-1] && 'z' >= s[s.size()-1])) {
        cout << "WA" <<endl;
        return 0;
    }

    bool foundC = false;
    for(size_t i = 2; i < s.size(); ++i) {

        if(s[i] == 'C') {
            if(foundC) {
                cout << "WA" << endl;
                return 0;
            } else {
                foundC = true;
            }
        } else {
            if (!('a'<=s[i] && 'z' >= s[i])) {
                cout << "WA" << endl;
                return 0;
            }
        }
    }
        
    cout << (foundC ? "AC":"WA") << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = INT32_MAX;
const ll INFL = INT64_MAX;
const int mod = 1e9 + 7;

template <typename T>
void print_vec(vector<T> v) {
  for (T i : v) cout << i << " ";
  cout << endl;
}

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> m(h);
  rep(i, h) cin >> m[i];

  vector<vector<int> > width(h, vector<int>(w));
  rep(i, h) {
    rep(j, w) {
      if (m[i][j] == '#') continue;
      width[i][j] = 1;
      if (j > 0) width[i][j] += width[i][j - 1];
    }
    for (int j = w - 1; j > 0; j--) {
      if (m[i][j - 1] == '#' || m[i][j] == '#') continue;
      width[i][j - 1] = width[i][j];
    }
  }

  vector<vector<int> > height(h, vector<int>(w));
  rep(j, w) {
    rep(i, h) {
      if (m[i][j] == '#') continue;
      height[i][j] = 1;
      if (i > 0) height[i][j] += height[i - 1][j];
    }
    for (int i = h - 1; i > 0; i--) {
      if (m[i - 1][j] == '#' || m[i][j] == '#') continue;
      height[i - 1][j] = height[i][j];
    }
  }

  int ans = 0;
  rep(i, h) rep(j, w) ans = max(ans, height[i][j] + width[i][j] - 1);

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

Measured memory_bytes: 35712
#include <stdio.h>

#define x 100000

int main(){

  int n,q,S[x],T[x],left,right,mid;
  int i,j,c=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  } 
  for(i=0;i<q;i++){

    left=0;
    right = n;  

    while(left<right){

      mid = (left + right)/2;

      if(S[mid]==T[i]){
	c++;
	break;
      }
      else if(T[i]<S[mid]){
	right = mid;
      }
      else if(T[i]>S[mid]) left = mid + 1;
    }
    
  }
  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define fo(i, n) for (int i = 0; i < n; i++)
#define Fo(i, k, n) for (int i = k; k < n ? i < n : i > n; k < n ? i += 1 : i -= 1)
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int>> pipii;
typedef priority_queue<pii, vector<pii>, greater<pii>> minpq;
typedef priority_queue<pii> maxpq;
//const double PI = acos(-1);
const int mod =1000000007;

// ----------------------DEBUG TEMPLATE--------------------------
void __print(int x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v))
        cerr << ", ";
    _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif
// ----------------------DEBUG TEMPLATE--------------------------


int solve(vi& weight,vi& val,int N,int W){

    int maxVal = N*1000;
    int dp[N+1][maxVal+1];

    for(int i =0;i <=maxVal;i++){
        dp[1][i]=INT_MAX;
        dp[0][i]=0;
    }
    dp[1][0]=0;
    dp[1][val[1]]=weight[1];

    for(int i =1;i <=N;i++){
        dp[0][i]=INT_MAX;
    }

    for(int i =2;i<= N;i++){
        for(int j = 1;j<=maxVal;j++){
            dp[i][j] = min(weight[i] + dp[i-1][j-val[i]],dp[i-1][j]);
        }
    }
    int ans=INT_MIN;
    for(int i =1;i<=maxVal;i++){
        if(dp[N][i]<=W){
            ans =i;
        }
    }
    return ans;


}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N,W;
    cin>>N>>W;
    vector<int>weight(N+1),val(N+1);
    for(int i =1;i <=N;i++){
        cin>>weight[i]>>val[i];
    }
    cout<<solve(weight,val,N,W)<<endl;


}
    

Measured memory_bytes: 82524
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=110;
int C[maxn],A[maxn][maxn];
int n,m;
int T;
vector<vector<int>> V;
vector<int> v;
int S[maxn];
void dfs(int size,int u)
{
    if(v.size()==size)
    {
        V.push_back(v);
        return ;
    }
    for(int i=u;i<n;i++)
    {
        v.push_back(i);
        dfs(size,i+1);
        v.pop_back();
    }
}
int main()
{
    int x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)
    {
        cin>>C[i];
        for(int j=0;j<m;j++)
            cin>>A[i][j];
    }
    for(int i=1;i<=n;i++)
        dfs(i,0);
    int res=1e9;
    for(int i=0;i<V.size();i++)
    {
        memset(S,0,sizeof(S));
        int cost=0;
        for(int j=0;j<V[i].size();j++)
        {
            for(int k=0;k<m;k++)
                S[k]+=A[V[i][j]][k];
            cost+=C[V[i][j]];
        }
        bool flag=true;
        for(int k=0;k<m;k++)
            if(S[k]<x) flag=false;
        if(flag)
            res=min(res,cost);
    }
    if(res==1e9)
        cout<<-1<<endl;
    else
        cout<<res<<endl;
}

Measured memory_bytes: 3892