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

string str;
int chk[26];

int main() {
	cin >> str;

	for (int i = 0; i < str.length(); ++i) {
		chk[str[i] - 'a'] = 1;
	}
	for (int i = 0; i < 26; ++i) {
		if (chk[i] == 0) {
			cout << str << (char)(i + 'a');
			return 0;
		}
	}

	for (int i = str.length() - 1; i >= 0; --i) {
		for (int j = str[i] - 'a' + 1; j < 26; ++j) {
			if (!chk[j]) {
				for (int h = 0; h < i; ++h) {
					cout << str[h];
				}
				cout << (char)(j + 'a');
				return 0;
			}
		}
		chk[str[i] - 'a'] = 0;
	}

	cout << -1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int a,b;
	cin>>a>>b;
	long long int trr[b];
	
	for(long long int i=0;i<b;i++)
	{
		cin>>trr[i];
		a=a-trr[i];
		if(a<=0)
		{
            break;
		}
	}
	if(a<=0)
		cout<<"Yes";
	else
		cout<<"No";
	cout<<"\n";
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long i,n;
	cin>>n;
	long long ans=1;
	for(i=1;i<=n;i++)
	{
		while(ans<=n)
		{
			ans=ans*2;
			if(ans>n)
			{
				cout<<ans/2<<endl;
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll      long long
#define hell    1000000007
#define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb      push_back


int main()
{
	ios;
	ll k=2019,i,j,n,rem=0,ans=0,po=1;
	string s;
	cin>>s;n=s.size();
	map<ll,ll>cnt;
	cnt[0]++;
	for(i=n-1;i>=0;i--){
		rem=(rem+(s[i]-'0')*po)%k;
		ans+=cnt[rem];
		cnt[rem]++;
		po=(po*10)%k;
	}
	cout<<ans;
}

Measured memory_bytes: 3812
#include <iostream>
#include <cstring>

using namespace std;
int main(void){
    int n;
    int maxa = 100000 + 1;
    cin >> n;
    int a[maxa];
    memset(a, 0, sizeof(a));
    
    long long S = 0;
    for (int i = 0; i < n; i ++) {
        int b; cin >> b;
        a[b] += 1;
        S += b;
    }
    int q; cin >> q;
    while (q --) {
        int b, c;
        cin >> b >> c;
        a[c] += a[b];
        S += (c-b)*a[b];
        cout << S << endl;
        a[b] = 0;
    }
    return 0;
}


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

int dp[1001][1001];
int main(){
  int H,W;
  cin >> H >> W;
  memset(dp,0,sizeof(dp));
  string c[1001];
  for(int i=0;i<H;i++){
    cin >> c[i];
  }
  for(int i=0;i<W;i++){
    if(c[0][i]!='#') dp[0][i]=1;
    else break;
  }
  for(int i=0;i<H;i++){
    if(c[i][0]!='#') dp[i][0]=1;
    else break;
  }
  int mod = 1e9+7;
  for(int i=1;i<H;i++){
    for(int j=1;j<W;j++){
      if(c[i][j]=='#'){
        dp[i][j]=0;
      }
      else{
        dp[i][j] = (dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
      }
    }
  }
  cout<<(dp[H-1][W-1]%mod)<<endl;
}


Measured memory_bytes: 5248
#ABC131
N,L = map(int,input().split())
f = 0
k = 0
j = []
for i in range(1,N+1):
    f += L+i-1
for i in range(1,N+1):
    k = L+i-1
    n = f-k
    p = abs(f-n)
    j.append(p)
if f >0:
    print(int(f-min(j)))
else:
    print(int(f+min(j)))


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <numeric>
#include <set>
#define FOR(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
using namespace std;



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

	char N;
	cin >> N;

	switch (N)
	{
	
	case 'A':
		cout << 'T' << endl;
		break;
	case 'C':
		cout << 'G' << endl;
		break;
	case 'G':
		cout << 'C' << endl;
		break;
	case 'T':
		cout << 'A' << endl;
		break;
	default:
		break;
	}

	return 0;
}

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a!=b && a!=c && b!=c) cout << 3 << endl;
    else if(a==b && a==c && b==c) cout << 1 << endl;
    else cout << 2 << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
K, S = map(int, raw_input().split())
ans = 0
for X in xrange(0, K + 1):
    for Y in xrange(0, min(K + 1, S - X + 1)):
        if 0 <= S - (X + Y) <= K:
            ans += 1
print ans



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

int main(){
  string s;
  cin >> s;
  
  int ans = 0;
  int l = 0, r = s.size()-1;
  while(1){
    if(l >= r) break;
    
    char lc = s.at(l), rc = s.at(r);
    if(lc == rc){
      l++, r--;
      continue;
    }
    else if(lc == 'x') l++;
    else if(rc == 'x') r--;
    else{
      ans = -1;
      break;
    }
    
    ans++;
  }
  
  cout << ans << endl;  
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>


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

const double EPS =1e-9;
const long INF =999999999;
const long MOD =1000000007; //10^9+7
#define PI 3.14159265258979

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

int main(void){
	int W,a,b;
	cin>>W>>a>>b;
	cout<<max(0,max(b-(a+W),a-(b+W)))<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	long long ans=0;
	cin>>n;
	if(n%2==1){
		cout<<"0"<<endl;
		return 0;
	}
	n=n/2;
	for(;;){
		n=n/5;
		ans+=n;
		if(n==0){
			break;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int[][] A = new int[N][2];
		for (int i=0;i<N;i++) {
			A[i][0] = i;
			A[i][1] = Integer.parseInt(sc.next());
		}
		Comparator<int[]> comparator = new Comparator<int[]>() {
    		@Override
    		public int compare(int[] o1, int[] o2) {
    			return Integer.compare(o1[1], o2[1]);
    		}
		};
		Arrays.sort(A, comparator);

		int max = A[N-1][1];
		int max_2 = A[N-2][1];
		int[] ans = new int[N];
		for (int i=0;i<N;i++) {
			if (i==N-1) {
				int index = A[i][0];
				ans[index] = max_2;
			} else {
				int index = A[i][0];
				ans[index] = max;
			}
		}
		for (int i=0;i<N;i++) {
			System.out.println(ans[i]);
		}
	}
}

Measured memory_bytes: 75112
use std::io;
//use std::collections::HashMap;
//use std::collections::BinaryHeap;
//use std::collections::HashSet;
//use std::mem; // mem::swap(&mut x,&mut y);
//use std::cmp; // cmp::max,cmp::min

#[allow(dead_code)]
fn read_line() -> String{
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn read_charvec() -> Vec<char>{
    read_line().chars().collect()
}

#[allow(dead_code)]
fn read_ints() -> Vec<i64>{
    let s = read_line();
    let split:Vec<&str> = s.split(" ").collect();
    split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
}

#[allow(dead_code)]
fn read_int() -> i64{
    read_ints()[0]
}

#[allow(dead_code)]
fn reverse(s: &String) -> String{
    s.chars().rev().collect::<String>()
}

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

fn read_lines(n:i64) -> Vec<String>{
    let mut xs = Vec::new();

    for _i in 0..n{
        xs.push(read_line());
    }

    xs
}

fn read_ints2(n:i64) -> Vec<i64>{
    read_lines(n).iter().map(|x| x.parse().unwrap()).collect()
}


fn solve()->bool{
    let nm = read_ints();
    let (n,m) = (nm[0],nm[1]);

    if n == 0 && m == 0{
        return false;
    }

    let xs = read_ints2(n);
    let ys = read_ints2(m);

    let sum_x = xs.iter().fold(0,|s,i|s+i);
    let sum_y = ys.iter().fold(0,|s,i|s+i);

    for x in xs.iter(){
        for y in ys.iter(){
            if sum_x-2*x+2*y - sum_y == 0{
                println!("{} {}",x,y);
                return true;
            }
        }
    }

    println!("-1");

    true
}

fn main(){
    while solve(){}
}



/*
DOCS

let mut h = HashMap::new();
let a = 5;
h.insert(a,true);
match h.get(&a){
    Some(v) => println!("{}",v),
    None    => println!("none"),
}


let mut x = 5;
let mut y = 1;
mem::swap(&mut x,&mut y);


let v = vec![0;2]; // [0,0]

s.chars().nth(i as usize).unwrap();


// priority queue
// https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(5);
heap.push(2);

assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);


let mut vs = heap.into_vec();
vs.reverse();

// 文字列をVec<char>として読み取ってVec<i32>に変換
let xs : Vec<i32> = read_charvec().iter().map(|&c| 
    if c == 'A'{
        0
    }else if c == 'B'{
        1
    }else if c == 'X'{
        2
    }else{
        3
    }
).collect();

// 検索
let i = match xs.iter().find(|&&m| m==0){
    Some(v) => true,
    None => false,
};
*/



Measured memory_bytes: 5032
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n; cin>>n;
    vl as(n + 1); cin>>as;
    vl cs(n + 1);

    if (as[0] > 0) {
        if (n == 0 && as[0] == 1) {
            cout<<1<<endl;
            return 0;
        }
        else {
            cout<<-1<<endl;
            return 0;
        }
    }


    vl ss(n + 1);
    rep(i, n) ss[n - i - 1] = ss[n - i] + as[n - i];

    cs[0] = 1;
    ll cnt = 1;
    rep(i, n) {
        if (as[i + 1] > cs[i] * 2) {
            cout<<-1<<endl;
            return 0;
        }
        cs[i + 1] = min(cs[i] * 2 - as[i + 1], ss[i + 1]);
        cnt += cs[i + 1] + as[i + 1];
    }
    cout<<cnt<<endl;
}

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

int main() {
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	for(int i=0;i<n;i++)
	{
		cin >> h.at(i);
	}
	sort(h.begin(),h.end());
	int ans=1000000000;
	for(int i=0;i<n-k+1;i++)
	{
		int d=h.at(i+k-1) - h.at(i);
		ans = min(ans,d);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
#define lp(i,n) for(int i=0;i<n;i++)
#define lpin(a,i,n) for(int i=0;i<n;i++){cin>>a[i];}

int main(){
  while(1){
    int n;
    cin>>n;
    if(n==0) break;
    int a[200],b[200];
    lp(i,200){
      a[i]=0;
      b[i]=0;
    }
    for(int i=1;i<n;i++){
      int x,y;
      cin>>x>>y;
      {
	if(y==0){
	  a[i]=a[x];
	  b[i]=b[x]-1;
	}
	if(y==1){
	  a[i]=a[x]-1;
	  b[i]=b[x];
	}
	if(y==2){
	  a[i]=a[x];
	  b[i]=b[x]+1;
	}
	if(y==3){
	  a[i]=a[x]+1;
	  b[i]=b[x];
	}
      }
    }
    int amax=0,amin=0,bmax=0,bmin=0;
    lp(i,n){
      amax=max(amax,a[i]);
      amin=min(amin,a[i]);
      bmax=max(bmax,b[i]);
      bmin=min(bmin,b[i]);
    }
    amax-=amin;
    amax++;
    bmax-=bmin;
    bmax++;
    cout<<bmax<<" "<<amax<<endl;
  }
  return 0;
}



Measured memory_bytes: 3080
#include <iostream>
#include <complex>
#include <cstring>
#include <vector>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,n) loop(i,0,n)
#define all(c) (c).begin(), (c).end()
typedef complex<int> P;

const int MAX_M = 1.5e6+10;
const int SIZE = 2000;
int ps[MAX_M/2];
bool isp[MAX_M];
int grid[SIZE][SIZE]={};
P itop[MAX_M];
pair<int,int> dp[SIZE][SIZE];

int cnt_p = 0;

void make_es(){
    fill(isp,isp+MAX_M,true);
    isp[0]=isp[1]=false;
    rep(i,MAX_M){
        if(!isp[i]) continue;
        ps[cnt_p++] = i;
        for(int j=i<<1; j<MAX_M; j+=i){
            isp[j] = false;
        }
    }
}

P const ii(0,1);

int n,m;

pair<int,int> rec(int y, int x){
    if(dp[y][x].first!=-1) return dp[y][x];

    pair<int,int> best(0,0);
    loop(i,-1,2){
        if(grid[y+1][x+i]<=m){
            auto t = rec(y+1,x+i);
            best = max(t,best);
        }
    }

    pair<int,int> res(0,0);
    if(isp[grid[y][x]]){
        res.first = 1;
        res.second = grid[y][x];
    }
    if(best.first != 0){
        res.first += best.first;
        res.second = best.second;
    }

    dp[y][x] = res;
    return res;
}

int main(){
    make_es();
    P p(SIZE/2,SIZE/2);
    P dir(0,1);
    for(int i=1; i<MAX_M; i++){
        grid[p.real()][p.imag()] = i;
        itop[i]=p;
        p+=dir;
        P q = p+dir*ii;
        if(grid[q.real()][q.imag()] == 0){
            dir*=ii;
        }
    }

    while(cin>>m>>n, n+m){
        auto t = make_pair(-1,-1);
        rep(i,SIZE)rep(j,SIZE) dp[i][j] = t;
        auto u = itop[n];
        auto ans = rec(u.real(), u.imag());
        cout << ans.first << " " << ans.second << endl;
    }
}

Measured memory_bytes: 60652
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

// Problem link : https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_b

struct ticket {
	int x, y, c;
};

int main() {
	int A, B, M;
	cin >> A >> B >> M;
	vector < int > a (A), b (B);
	vector < ticket > tickets (M);
	for (int i = 0; i < A; i++) {
		cin >> a[i];
	}
	for (int j = 0; j < B; j++) {
		cin >> b[j];
	}
	for (int i = 0; i < M; i++) {
		cin >> tickets[i].x >> tickets[i].y >> tickets[i].c;
	}
	ll answer = 1e13;
	for (int i = 0; i < M; i++) {
		answer = min (answer, (ll) a[tickets[i].x - 1] + b[tickets[i].y - 1] - tickets[i].c);
	}
	int mina = a[0], minb = b[0];
	for (int i = 0; i < A; i++) {
		mina = min (mina, a[i]);
	}
	for (int i = 0; i < B; i++){
		minb = min (minb, b[i]);
	}
	answer = min (answer, (ll)mina + minb);
	cout << answer << endl;
	return 0;
}


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

#define MAX 20002

typedef struct Tuple {
    int start_index;
    int area;
} Tuple;

int main(void) {
    int len;
    char input[MAX];
    scanf("%s", &input);
    len = strlen(input);
    
    int st1[MAX];
    Tuple st2[MAX];
    
    int st1_p = 0, st2_p = 0;
    int sum = 0;
    
    for (int i=0; i<len; i++) {
        if (input[i] == '\\') st1[st1_p++] = i;
        else if (input[i] == '/') {
            if (st1_p == 0) continue;
            int start = st1[--st1_p];
            int area = i - start;
            while (st2_p > 0 && st2[st2_p-1].start_index > start) {
                Tuple pop = st2[--st2_p];
                area += pop.area;
                sum -= pop.area;
            }
            Tuple t = {start, area};
            st2[st2_p++] = t;
            sum += area;
        }
    }
    
    printf("%d\n%d", sum, st2_p);
    for (int i=0; i<st2_p; i++) {
        printf(" %d", st2[i].area);
    }
    printf("\n");
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const ll siz = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll maxx = 1e9;
const ll MAXX = 1e17;
const ll base = 31;

char c;
int cnt1, cnt2;

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen ("IN_2.INP", "r", stdin);
//    freopen ("OUT_2.OUT", "w", stdout);
    for (int i = 1; i <= 3; i++)
    {
        cin >> c;
        if (c == 'A') cnt1++;
        else cnt2++;
    }
    (cnt1 == 3 || cnt2 == 3) ? cout << "No" : cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 100000000;
const int MAX_N = 50;
using namespace std;
int main() {
	int X;
	cin >> X;
	int max_v = 0;
	for (int i = 1; i <= 31; i++) {
		for (int j = 2; j <= 10; j++) {
			if ((int)pow(i, j) <= X) {
				max_v = max((int)pow(i, j), max_v);
			}
		}
	}
	cout << max_v << endl;
}


Measured memory_bytes: 256
# code festival 2017 qc
# 方針：全ての項の積が奇数＝全てのBiが奇数の数を求め、
# 3^nから引く

n = gets.to_i
a = gets.split.map &:to_i
cnt = 1
a.each do |a|
  cnt *= 2 if a.even?
end

ans = 3**n - cnt
puts ans

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
ll read(){
	char ch=getchar(); ll x=0; int op=1;
	for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;
	for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
#define N 100005
int n,m,cnt,head[N],dep[N],l[N],r[N],val[N],vis[N]; bool flag;
struct edge{ int to,nxt; }e[N<<1];
void adde(int x,int y){
	e[++cnt].to=y; e[cnt].nxt=head[x]; head[x]=cnt;
}
void ins(int x,int y){ adde(x,y); adde(y,x); }
void dfs(int u,int pr){
	for (int i=head[u],v; i; i=e[i].nxt) if ((v=e[i].to)!=pr){
		dep[v]=dep[u]+1; dfs(v,u);
	}
}
void dfs2(int u,int pr){
	if (vis[u]) l[u]=r[u]=val[u];
	else l[u]=-inf,r[u]=inf;
	for (int i=head[u],v; i; i=e[i].nxt) if ((v=e[i].to)!=pr){
		dfs2(v,u);
		l[u]=std::max(l[u],l[v]-1); r[u]=std::min(r[u],r[v]+1);
	}
	if (l[u]>r[u]){ puts("No"); exit(0); }
}
void getans(int u,int pr){
	if (!vis[u]){
		if (l[u]<=val[pr]+1 && val[pr]+1<=r[u]) val[u]=val[pr]+1;
		else val[u]=val[pr]-1;
	}
	for (int i=head[u],v; i; i=e[i].nxt) if ((v=e[i].to)!=pr) getans(v,u);
}
int main(){
	n=read();
	rep (i,1,n-1){
		int x=read(),y=read(); ins(x,y);
	}
	dfs(1,0);
	m=read();
	rep (i,1,m){
		int x=read(),y=read();
		vis[x]=1,val[x]=y;
		if (i==1) flag=(y&1)^(dep[x]&1);
		else if ((y&1)^(dep[x]&1)!=flag){ puts("No"); exit(0); }
	}
	dfs2(1,0);
	if (!vis[1]) val[1]=l[1],vis[1]=1; getans(1,0);
	puts("Yes"); rep (i,1,n) printf("%d\n",val[i]);
	return 0;
}

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

int main(){
    int h, w, k;
    cin >> h >> w >> k;

    char m[6][6];

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> m[i][j];
        }
    }

    int cnt = 0;
    for(int i=0;i<(1<<h);i++){
        for(int j=0;j<(1<<w);j++){
            int tmp = 0;
            for(int ii=0;ii<h;ii++){
                for(int jj=0;jj<w;jj++){
                    if( (i & (1 << ii)) && (j & (1 << jj)) && m[ii][jj] == '#' ) {
                        tmp++;
                    }
                }
            }
            if (tmp == k) {
                cnt++;
            }
        }
    }

    cout << cnt << endl;
 
    return 0;
}


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

int main()
{
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    char c = 'a';
    while (1)
    {
        if (c == 'a')
        {
            if (sa.empty())
            {
                cout << "A";
                return 0;
            }
            c = sa[0];
            sa.erase(sa.begin());
        }
        else if (c == 'b')
        {
            if (sb.empty())
            {
                cout << "B";
                return 0;
            }
            c = sb[0];
            sb.erase(sb.begin());
        }
        else
        {
            if (sc.empty())
            {
                cout << "C";
                return 0;
            }
            c = sc[0];
            sc.erase(sc.begin());
        }
    }
}

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

int main() {
  int N,K;
  cin >> N >> K;
  int dist=0;

  for(int i =0; i < N; i++){
    int x;
    cin >> x;
    if(x<K-x){
      dist+=x*2;
    }else{
      dist+=(K-x)*2;
    }
  }
  cout << dist <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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;
const int INF=1001001001;

int modpow(int x,int n){
  if(n==0){return 1;}
  int64_t sum=modpow(x,n/2);sum%=mod;
  sum*=sum;sum%=mod;
  if(n%2!=0){sum*=x;}sum%=mod;
  return sum;
}

int choose(int n,int a){
  int64_t up=1,down=1;
  for(int i=0;i<a;i++){
    up*=n-i;
    up%=mod;
    down*=i+1;
    down%=mod;
  }
  int64_t s=up*modpow(down,mod-2);
  s%=mod;
  return s;
}

int main() {
  int64_t n,a,b;
  cin>>n>>a>>b;
  int ans=modpow(2,n)-1;
  ans-=choose(n,a);if(ans<0){ans+=mod;}
  ans-=choose(n,b);if(ans<0){ans+=mod;}
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 3572
package main

import(
  "fmt"
)

func main() {
  var x, y, z int
  fmt.Scanf("%d %d %d", &x, &y, &z)
  sum := (x/y) * z
  if x%y > 0 {
    sum += z
  }
  
  fmt.Println(sum)
  return
}

Measured memory_bytes: 1832
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int K;
int S;
int dp[7501];
int s[7502];
int main(){
  int Lj4PdHRW, i;
  rd(K);
  rd(S);
  for(i=0;i<(K+1);i++){
    dp[i] = 1;
  }
  for(Lj4PdHRW=0;Lj4PdHRW<(2);Lj4PdHRW++){
    for(i=0;i<(3*K+1);i++){
      s[i+1] = s[i] + dp[i];
    }
    for(i=0;i<(3*K+1);i++){
      if(i-K-1>=0){
        dp[i] = s[i+1]- s[i-K];
      }
      else{
        dp[i] = s[i+1];
      }
    }
  }
  wt_L(dp[S]);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// int K, S;
// int dp[7501], s[7502];
// {
//   rd(K,S);
//   rep(i,K+1) dp[i] = 1;
//   rep(2){
//     rep(i,3K+1) s[i+1] = s[i] + dp[i];
//     rep(i,3K+1) dp[i] = s[i+1] if[i-K-1>=0, - s[i-K]];
//   }
//   wt(dp[S]);
// }


Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

A, B = map(int, raw_input().split())
print max(A + B, A - B, A * B)

Measured memory_bytes: 2812
#include<bits/stdc++.h>
const int maxn=8e2+10;
using namespace std;
char a[maxn][maxn];
int stmp[maxn][maxn];
int direction[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,k;
int ans=99999999;
bool check(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m&&stmp[x][y]==0&&a[x][y]=='.')
    {
       return 1;
    }
    return 0;
}
queue<pair<int,int> >po;
int main()
{
    cin>>n>>m>>k;
    int sx,sy;
    getchar();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%c",&a[i][j]);
            if(a[i][j]=='S')
            {
                sx=i;
                sy=j;
            }
        }
        getchar();
    }
    stmp[sx][sy]=1;
    po.push(make_pair(sx,sy));
    while(!po.empty())
    {
        int x=po.front().first;
        int y=po.front().second;
        ans=min(ans,min(min(x,n-x-1),min(y,m-y-1)));
        po.pop();
        for(int i=0;i<4;i++)
        {
            int xx=x+direction[i][0];
            int yy=y+direction[i][1];
            if(check(xx,yy)&&stmp[x][y]<=k)
            {
               stmp[xx][yy]=stmp[x][y]+1;
               po.push(make_pair(xx,yy));
               int iii=0;
            }
        }
    }
    int anss;
    anss=1+(ans+k-1)/k;cout<<anss<<endl;
    return 0;
}

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

int num = 1;
vector<int> A;

// S[i] を c に書きかえる
void update(int i, char c) {
  i += num - 1;
  A.at(i) = 1 << (c - 'a');  // ビットフラグ
  while (i > 0) {
    i = (i - 1) / 2;
    A.at(i) = A.at(i*2 + 1) | A.at(i*2 + 2);
  }
}

// 「区間 [a, b) でどの文字が登場するか」を保持したビットフラグを返す
int query(int a, int b, int k, int l, int r) {
  if (r <= a || b <= l) return 0;
  if (a <= l && r <= b) return A.at(k);
  else {
    int c1 = query(a, b, 2*k+1, l, (l+r)/2);
    int c2 = query(a, b, 2*k+2, (l+r)/2, r);
    return c1 | c2;
  }
}

int main() {
  int N; cin >> N;
  string S; cin >> S;
  num = 1;
  while (num < N) num *= 2;
  A = vector<int>(2*num - 1, 0);  // 完全二分木
  for (int i = 0; i < N; i++) update(i, S.at(i));

  int Q; cin >> Q;
  for (int i = 0; i < Q; i++) {
    int com; cin >> com;
    if (com == 1) {
      int idx; cin >> idx; idx--;
      char c; cin >> c;
      update(idx, c);
    }
    if (com == 2) {
      int left, right; cin >> left >> right;
      left--;
      int bit = query(left, right, 0, 0, num);
      int cnt = 0;
      for (int i = 0; i < 26; i++) {
        if ((bit >> i) & 1) cnt++;  // i 番目のビットが立っている
      }
      cout << cnt << endl;
    }
  }
}

Measured memory_bytes: 4996
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e5 + 7, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
int main()
{
int n,array1[N],i,counter=0;
scanf("%d",&n);
for(int i=0;i<n;++i){
    scanf("%d",&array1[i]);
}
sort(array1,array1+n);
for(i=0;i<n-1;++i){
    counter+=array1[i+1]-array1[i];
}
printf("%d",counter);


    return 0;
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

vector<int> pls(200010, 0);
int a[200010];
int main()
{
    int n;
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    for (int i = 0; i < n; i++) {
        if (i - a[i] >= 0)
            ans += pls[i - a[i]];
        if (i + a[i] <= n)
            pls[i + a[i]]++;
    }
    printf("%lld", ans);
}

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

using namespace std;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")

#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"

#define sz(a) ((int)(a).size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define tr(c, it) for (auto it = (c).begin(); (it) != (c).end(); it++)
#define pres(c, val) ((c).find(val) != (c).end())      //
#define cpres(c, val) (find(all(c), val) != (c).end()) //

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define forb(i, a, b) for (int i = (b); i >= (a); i--)
#define fo(i, n) forf(i, 0, n)
#define fob(i, n) forb(i, 0, n - 1)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;

const int INF = 9e18;
// const int N = 1e9 + 7;
const int N = 998244353;
const double eps = 1e-9;

const auto start_time = std::chrono::high_resolution_clock::now();

void zark() {
	#ifdef ZARK
		auto end_time = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double> diff = end_time - start_time;
		cerr << "Time Taken: " << diff.count() << "s\n";
	#endif
}

#ifdef ZARK
  #include "/home/aranjan/Desktop/CP/header.h"
  #else
  #define debug(args...) 42
#endif
 
/* ------------------ Actual Coding Starts ------------------ */

void solve() {
	string s;
	cin >> s;
	for(char &c: s) {
		if(c == '?') c = 'D';
	}
	cout << s << endl;
}

int32_t main() {
	fastio;
	#ifdef ZARK
		freopen("input.in", "r", stdin);
	#endif

	// freopen("txt.in", "r", stdin);
	// freopen("txt.out", "w", stdout);
	// cout << fixed << setprecision(10);

	solve();
	zark();
	return 0;
}

Measured memory_bytes: 3744
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [0 for j in range(S + 1)]
dp[0] = 1
for i in range(N):
    for j in reversed(range(S + 1)):
        dp[j] = (2*dp[j])%mod if j < A[i] else (2*dp[j] + dp[j-A[i]])%mod
print(dp[S])

Measured memory_bytes: 68760
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
for i in range(n):
  ans += b[a[i] - 1]
  
for i in range(n-1):
  if a[i+1] == a[i] + 1:
    ans += c[a[i]-1]
  
  

print(ans)


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

int main(){
	int a,b,ans=0;
	cin>>a>>b;
	for(int i=a;i<=b;i++){
		if(i/10000==i%10&&(i/1000)%10==(i%100)/10) ans++;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
from copy import deepcopy
h, w, k = map(int, input().split())
c = [list(input()) for i in range(h)]
ans = 0
for i in range(1 << h):
    for j in range(1 << w):
        t = deepcopy(c)
        for x in range(h):
            for y in range(w):
                if (i >> x & 1) or (j >> y & 1):
                    t[x][y] = "."
        p = 0
        for x in range(h):
            for y in range(w):
                if t[x][y] == "#":
                    p += 1
        if p == k:
            ans += 1
print(ans)


Measured memory_bytes: 73500
#include <cstdio>

char S[101010];

int main(){
	scanf("%s", S);

	bool app[26];
	for (int i = 0; i < 26; ++i) {
		app[i] = false;
	}
	for (int i = 0; S[i] != '\0'; ++i) {
		app[S[i] - 'a'] = true;
	}
	for (int i = 0; i < 26; ++i) {
		if (!app[i]) {
			printf("%c\n", (char)(i + 'a'));
			return 0;
		}
	}
	puts("None");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
using namespace std;

int main()
{
	int H, W;
	cin >> H >> W;

	vector<vector<char>> m;
	for (auto i = 0; i < H; ++i)
	{
		vector<char> w;
		auto isExist = false;
		for (auto j = 0; j < W; ++j)
		{
			char a;
			cin >> a;
			w.push_back(a);
			if (a == '#')
			{
				isExist = true;
			}
		}
		if (isExist)
		{
			m.push_back(w);
		}
	}

	vector<int> c;
	for (auto i = 0; i < W; ++i)
	{
		for (auto j = 0; j < m.size(); ++j)
		{
			if (m[j][i] == '#')
			{
				c.push_back(i);
				break;
			}
		}
	}

	for (auto i = 0; i < m.size(); ++i)
	{
		for (auto j = 0; j < c.size(); ++j)
		{
			cout << m[i][c[j]];
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 256
n=int(input())
a_list=list(map(int,input().split()))
ans=0
tmp=a_list[0]
for i in range(n-1):
    if tmp>a_list[i+1]:
        #print(tmp,ans)
        ans+=tmp-a_list[i+1]
    else:
        #ans+=tmp-a_list[i]
        tmp=a_list[i+1]
print(ans)


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

int main() {
    int N, X;
    cin >> N >> X;
    vector<ll> a(N);
    vector<ll> Xs;
    rep(i, N) { cin >> a[i]; }
    ll ans = 0;

    rep(i, N - 1) {
        ll x = X;
        ll p1 = a[i], p2 = a[i + 1];
        if (p1 + p2 > x) {
            ll diff = p1 + p2 - x;
            a[i + 1] = max((ll)0, p2 - diff);
            ans += min(p2, diff);
            diff -= ans;
            Xs.push_back(diff);
        } else {
            Xs.push_back(0);
        }
    }

    rep(i, N - 1) {
        ll x = Xs[i];
        ll p1 = a[i], p2 = a[i + 1];
        if (x <= 0)
            continue;
        else {
            ans += min(p1, x);
        }
    }

    cout << ans << endl;
}

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

using namespace std;


int main(){
    unsigned int x;
    
    cin >> x ;
    bitset<32> x_bit(x);
    bitset<32> x_bit2(x);
    bitset<32> x_bit3(x);
    
    cout << x_bit << "\n";
    cout << x_bit.flip() << "\n";
    cout << (x_bit2 <<= 1) << "\n";
    
    cout << (x_bit3 >>= 1) << "\n";
    return 0;   
}



Measured memory_bytes: 3156
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

vvl G;
vl visited;
vl ans;

void dfs(ll v) {
    visited[v] = 1;
    for(auto u : G[v]) {
        if(visited[u]) {
            continue;
        }
        ans.pb(u);
        dfs(u);
        break;
    }
}

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

    G.resize(n);
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        a--;  b--;
        G[a].pb(b);
        G[b].pb(a);
    }

    visited.resize(n);
    dfs(0);

    reverse(all(ans));
    ans.pb(0);
    dfs(0);

    out(ans.size());
    rep(i, ans.size()) {
        cout << ans[i] + 1 << " ";
    }
    
    cout << endl;
    re0;
}

Measured memory_bytes: 10868
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
 
#define DEBUG(X) std::cout << #X << " : " << X << std::endl
#define Mp(X, Y) std::make_pair(X, Y)

typedef long long ll;

long long nextInt()
{
    long long num = 0;
    char c;
    bool flag = false;	
    while ((c = std::getchar()) == ' ' || c == '\r' || c == '\t' || c == '\n');
    if (c == '-')
        flag = true;
    else
        num = c - 48; 
    while (std::isdigit(c = std::getchar()))
        num = num * 10 + c - 48;
    return (flag ? -1 : 1) * num;
}

int getGcd(int x, int y)
{
	if (y == 0)
		return x;
	return getGcd(y, x % y);
}

int a[100201] = { 0 };

int main(int argc, char **argv)
{
	int n = nextInt(), T = nextInt();
	for (int i = 1; i <= n; i++)
	{
		a[i] = nextInt();
		a[i] = std::abs(T - a[i]);
	}
	int ans = a[1];
	for (int i = 1; i <= n; i++)
		ans = getGcd(ans, a[i]);
	std::cout << ans << std::endl;
#ifdef __EDWARD_EDIT
	std::cin.get();
	std::cin.get();
#endif
	return 0;
}

Measured memory_bytes: 888
// Harshad Number
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, X;
    int su = 0;
    cin >> N;
    X = N;
    while (X > 0) {
        su += X % 10;
        X /= 10;
    }
    if (N % su == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int n;
string s;

bool check(int x) {
    map<string, int> v;
    for(int i = 1; i <= n + 1 - x; i++) {
        string a = s.substr(i - 1, x);
        if(v[a]) {
            if(i - v[a] >= x) return true;
        }
        else v[a] = i;
    }
    return false;
}

int main() {
    cin >> n >> s;
    int l = 0, r = n;
    while(l <= r) {
        int m = (l + r) >> 1;
        if(check(m)) l = m + 1;
        else r = m - 1;
    }
    cout << r << endl;
}


Measured memory_bytes: 6660
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  while(1){
    cin>>n;
    if(n==0)break;
    vi a(10,0);
    rep(i,n){
      int c;
      cin>>c;
      a[c]++;
    }
    rep(i,10){
      if(a[i]==0){
        cout<<"-"<<endl;
        continue;
      }
      rep(j,a[i])
        cout<<"*";
      cout<<endl;
    }
  }
}

Measured memory_bytes: 2968
fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: u64 = s.trim().parse().unwrap();
    let mut ans = 0;
    let mut a = 1;
    while a * a + a < n {
        if (n - a) % a == 0 {
            ans += (n - a) / a;
        }
        a += 1;
    }
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define debugP int debug_point; cin>>debug_point;
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/


int main(){
    ll n,q;
    string s;
    cin>>n>>q>>s;
    vector<pair<ll,ll>>a(q);
    vec(b,n);
    rep(i,q){
        cin>>a[i].first>>a[i].second;
    }
    ll ans=0;
    rep(i,s.size()-1){
        if(s[i]=='A'&&s[i+1]=='C'){
            b[i+1]=1+b[i];
        }else{
            b[i+1]=b[i];
        }
    }
    rep(i,q){
        ll cnt=0;
        op(-b[a[i].first-1]+b[a[i].second-1]);
    }
    return 0;
}

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

namespace lec10C
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                string  x = Console.ReadLine();
                string  y = Console.ReadLine();
                int output = LCSsolve(x, y);
                Console.WriteLine(output);
            }

            Console.ReadLine();

        }

        static int LCSsolve(string x, string y)
        {
            int m = x.Length;
            int n = y.Length;
            int[,] arr = new int[m + 1, n+1] ;

            for (int i = 1; i <= m; i++)
            {
                arr[i, 0] = 0;
            }

            for (int j = 0; j <= n; j++)
            {
                arr[ 0 , j] = 0;
            }

            for (int i = 1; i <= m; i++)
            {
                for (int  j = 1; j <= n; j++)
                {
                    if (x[i-1] == y[j-1])
                    {
                        arr[i, j] = arr[i - 1, j - 1] + 1;
                    } else if ( arr[i-1 , j ] >= arr[i, j - 1])
                    {
                        arr[i, j] = arr[i-1,j];
                    }
                    else
                    {
                        arr[i, j] = arr[i,j-1];
                    }
                }
            }

            return arr[m,n];
        }

    }
}



Measured memory_bytes: 32980
H,W=map(int,input().split());M=[input()for _ in"_"*H];D=[[0]*-~W for _ in"_"*-~H]
for i in range(H):
  for j in range(W):
    a=b=999
    if i>0:a=D[i][j+1]+(M[i-1][j]>M[i][j])
    if j>0:b=D[i+1][j]+(M[i][j-1]>M[i][j])
    D[i+1][j+1]=min(a,b,999*(i+j>0))
print(D[-1][-1]+(M[0][0]<".")) 

Measured memory_bytes: 9068
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000001
typedef long long ll;
typedef vector<int> arr;
typedef vector<ll> longarr;
typedef vector<longarr> longmat;

ll solve(int n, ll W, longarr w, arr v) {
	ll maxval = n * 1000;
	longmat dp(n + 1, longarr( maxval + 1, inf ));

	for (int i = 0; i < n; ++i) {dp[i][0] = 0;}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= maxval; ++j) {
			ll x = dp[i - 1][j];
			ll y = (j >= v[i - 1]) ? (w[i - 1] + dp[i - 1][j - v[i - 1]]) : inf;
			dp[i][j] = min(x, y);
		}
	}
	int ans;
	for (int i = maxval; i >= 0; --i) {
		if (dp[n][i] <= W) {ans = i; break;}
	}
	return ans;
}

int main() {
//#ifndef ONLINE_JUDGE
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//#endif
	int n; ll W;
	cin >> n;
	cin >> W;
	longarr w(n, 0);
	arr v(n, 0);
	for (int i = 0; i < n; ++i) {
		cin >> w[i] >> v[i];
	}
	cout << solve(n, W, w, v);

}

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

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976
const double PI = 3.1415926535897932;

int main()
{
    int n,k; cin >> n >> k;
    int h[n];
    rep(i,n) cin >> h[i];
    sort(h,h+n);
    int ans = inf;
    rep(i,n-k+1){
        ans = min(ans,h[i+k-1]-h[i]);
    }
    cout << ans<< endl;
}


Measured memory_bytes: 640
from itertools import permutations

N = int(input())
XY = [0 for _ in range(N)]
for i in range(N):
  xy = list(map(int,input().split()))
  XY[i] = xy
  
nums =[i for i in range(N)]
pers = permutations(nums,N)
distance = 0
count = 0
for i in pers:
  count += 1
  for j in range(N-1):
    distance += ((XY[i[j]][0]-XY[i[j+1]][0])**2 + (XY[i[j]][1]-XY[i[j+1]][1])**2)**0.5
    
print(distance/count)
      

Measured memory_bytes: 9468
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second

void cinv(vector<ll> &v){
    for(ll i=0;i < v.size();i++){
            cin >> v.at(i);
    }
}//vector入力用の関数

using data = pair<ll,vector<ll>>;

int main(){
    ll A,B,C,k;
    cin >> A >> B >> C >> k;
    vector<ll> o(A),s(B),t(C);

    cinv(o);cinv(s);cinv(t);
    sort(o.begin(),o.end(),greater<ll>());
    sort(s.begin(),s.end(),greater<ll>());
    sort(t.begin(),t.end(),greater<ll>());

    priority_queue<data> q;
    
    set<data> ch;

    ll ze = 0;

    q.push(data(o[0]+s[0]+t[0],{ze, ze, ze}));

    ll flag = 0;

    while(flag<k){
        data x = q.top();
        q.pop();
        cout << x.fi << endl;
        flag++;
        
        if(ch.count(data(o[x.se.at(0) + 1]+s[x.se.at(1)]+t[x.se.at(2)],{x.se.at(0) +1,x.se.at(1),x.se.at(2)}))== 0 && x.se.at(0)+1<A){//set.count
            q.push(data(o[x.se.at(0) + 1]+s[x.se.at(1)]+t[x.se.at(2)],{x.se.at(0) +1,x.se.at(1),x.se.at(2)}));
            ch.insert(data(o[x.se.at(0) + 1]+s[x.se.at(1)]+t[x.se.at(2)],{x.se.at(0) +1,x.se.at(1),x.se.at(2)}));
        }
        if(ch.count(data(o[x.se.at(0)]+s[x.se.at(1)+1]+t[x.se.at(2)],{x.se.at(0),x.se.at(1)+1,x.se.at(2)}))==0 && x.se.at(1)+1<B){//set.count
            q.push(data(o[x.se.at(0)]+s[x.se.at(1)+1]+t[x.se.at(2)],{x.se.at(0),x.se.at(1)+1,x.se.at(2)}));
            ch.insert(data(o[x.se.at(0)]+s[x.se.at(1)+1]+t[x.se.at(2)],{x.se.at(0),x.se.at(1)+1,x.se.at(2)}));
        }
        if(ch.count(data(o[x.se.at(0)]+s[x.se.at(1)]+t[x.se.at(2)+1],{x.se.at(0),x.se.at(1),x.se.at(2)+1}))==0 && x.se.at(2)+1<C){//set.count
            q.push(data(o[x.se.at(0)]+s[x.se.at(1)]+t[x.se.at(2)+1],{x.se.at(0),x.se.at(1),x.se.at(2)+1}));
            ch.insert(data(o[x.se.at(0)]+s[x.se.at(1)]+t[x.se.at(2)+1],{x.se.at(0),x.se.at(1),x.se.at(2)+1}));
        }        
    }
}
/*解法1 全探索だと間に合わない→途中まで探索して残った候補と残りで探索するor枝刈り*/


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;



int main(){
  string a, b;
  cin >> a >> b;
  string ans = "ok";
  int ketaa = a.size();
  int ketab = b.size();
  if (ketaa != ketab) {
    if (ketaa > ketab) ans = "GREATER";
    else ans = "LESS";
  } else {
    rep(i, ketaa){
      if (a[i] == b[i]) continue;
      else {
        if (a[i] > b[i]) ans = "GREATER";
        else ans = "LESS";
        break;
      }
    }
  }
  if (ans == "ok") ans = "EQUAL";
  cout << ans << endl;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.par = [-1]*(n+1)
        self.sizes=[1]*(n+1)

    # 検索
    def find(self, x):
        if self.par[x]<0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        d1=self.par[x]
        d2=self.par[y]
        if d1<=d2:
            self.par[y]=x
            self.sizes[x]=self.sizes[x]+self.sizes[y]
            if d1==d2:
                self.par[x]=self.par[x]-1
        else:
            self.par[x]=y
            self.sizes[y]=self.sizes[x]+self.sizes[y]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    #サイズ
    def size(self,x):
        return self.sizes[find(x)]

    #木の数
    def number(self):
        count=0
        for i in self.par[1:]:
            if i<0:
                count=count+1
        return count
        
N,M=map(int,input().split())
U=UnionFind(N)
for i in range(M):
    X,Y,Z=map(int,input().split())
    U.union(X,Y)
print(U.number())


Measured memory_bytes: 73432