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

struct Record {
  int tid, pid, time;
  bool correct;
};

struct Team {
  Team() {
    penalty = 0;
  }
  set<int> solved;
  map<int, int> WA;
  int penalty;
};

// Solved Problems, Penalty, Team ID
typedef tuple<int, int, int> Score;

int main() {
  int M, T, P, R;
  while (cin >> M >> T >> P >> R && M) {
    vector<Record> records(R);
    for (int i = 0; i < R; i++) {
      int m, t, p, j;
      cin >> m >> t >> p >> j;
      records[i].pid = --p;
      records[i].tid = --t;
      records[i].time = m;
      records[i].correct = (j == 0);
    }

    vector<Team> teams(T);
    for (Record r : records) {
      if (teams[r.tid].solved.find(r.pid) != teams[r.tid].solved.end()) {
        continue;
      } else if (r.correct) {
        teams[r.tid].solved.insert(r.pid);
        teams[r.tid].penalty +=
          teams[r.tid].WA[r.pid] * 20 + r.time;
      } else {
        teams[r.tid].WA[r.pid]++;
      }
    }

    vector<Score> team_result(T);
    for (int i = 0; i < T; i++) {
      get<0>(team_result[i]) = -teams[i].solved.size();
      get<1>(team_result[i]) = teams[i].penalty;
      get<2>(team_result[i]) = -i;
    }

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

    for (int i = 0, len = team_result.size(); i < len; i++) {
      Score s = team_result[i];
      if (i > 0) {
        Score p = team_result[i - 1];
        cout << 
          (get<0>(p) == get<0>(s) && get<1>(p) == get<1>(s)?"=":",");
      }
      cout << -get<2>(s)+1;
    }
    cout << endl;
  }
}

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

int main()
{
  int a, b ;
  cin >> a >> b ;
  for(int i = 1 ; i <= 3 ; i++)
  {
    if(i != a && i != b)
    {
      cout << i << endl ;
    }
  }
  
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

bool used[100000][2];
int64_t dp[100000][2];
int32_t N;
int64_t A[100000];
int64_t func(int i, bool rev)
{
	int64_t m = (rev ? -1 : 1);
	if (i == N - 1) {
		return  m * A[i];
	}
	auto& memo = dp[i][rev];
	if (used[i][rev]) { return memo; }
	used[i][rev] = true;

	return memo = std::max(m * A[i] + func(i + 1, false), -1 * m * A[i] + func(i + 1, true));
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 0; i < N; i++)
	{
		in >> A[i];
	}
	out << func(0, false);

	return 0;
}
#endif


Measured memory_bytes: 9088
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string S;
    int ans = 0;

    cin >> S;

    for (int i = 0; i < 100; i++)
    {
        if (S[i + 2] != '\0')
        {
            ans++;
        }
        else
        {
            cout << S[0] << ans << S[i + 1] << endl;
            return 0;
        }
    }

    cout << S << endl;

    return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> l(N);
    vector<int> r(N);
    for (int i = 0; i< N;i++){
        cin >> l[i] >> r[i];
    }

    int spactator = 0;
    for (int i = 0; i < N; i++){
        spactator += r[i] - l[i] + 1;
    }

    cout << spactator << endl;
}


Measured memory_bytes: 256
import sys

def main():
    input = sys.stdin.readline
    D, G = map(int, input().split())
    P = [tuple(map(int, input().split())) for i in range(D)]

    #x問解いて獲得できるスコアの最大値を求める
    def calc_max_score(x):
        max_score = 0
        for compl in range(1<<D):
            s = 0
            p = x
            solved = [False] * D
            for i in range(D):
                if compl & 1:
                    p -= P[i][0]
                    if p < 0: break
                    s += P[i][0] * (i+1) * 100 + P[i][1]
                    solved[i] = True
                compl >>= 1
            if p < 0: continue
            for i in range(D-1, -1, -1):
                if solved[i] == False:
                    count = min(P[i][0], p)
                    p -= count
                    s += count * (i+1) * 100
                if p <= 0: break
            max_score = max(max_score, s)
        return max_score

    under = 0
    r = 1000 * 10 + 10**7
    while r - under > 1:
        m = (under + r) // 2
        if calc_max_score(m) >= G: r = m
        else: under = m
    print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 42864
primes = set(range(3, 10**5, 2))
primes.add(2)
cumsum = [0] * (10**5 + 2)

for i in range(3, 10**5):
    if i in primes:
        for not_prime in range(i+i, 10**5, i):
            primes.discard(not_prime)


count = 0
for num in range(1, 10**5, 2):
    if num in primes:
        if (num+1)//2 in primes:
            count += 1

    cumsum[num] = count
    cumsum[num+1] = count

q = int(input())
for i in range(q):
    left, right = map(int, input().split())
    res = cumsum[right] - cumsum[left-1]
    print(res)

Measured memory_bytes: 7788
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;
const int MAXM=MAXN-1;

int n;
int ghead[MAXN],gnxt[2*MAXM],gto[2*MAXM],deg[MAXN];

int sz[MAXN],par[MAXN];
void dfs(int at) {
	sz[at]=1; for(int x=ghead[at];x!=-1;x=gnxt[x]) if(gto[x]!=par[at]) { int to=gto[x]; par[to]=at; dfs(to); sz[at]+=sz[to]; }
}

bool solve() {
	if(n%2==1) return true;
	par[0]=-1; dfs(0);
	REP(at,n) {
		int cnt=0;
		if((n-sz[at])%2==1) ++cnt;
		for(int x=ghead[at];x!=-1;x=gnxt[x]) if(gto[x]!=par[at]) { int to=gto[x]; if(sz[to]%2==1) ++cnt; }
		if(cnt>=2) return true;
	}
	return false;
}

void run() {
	scanf("%d",&n); REP(i,n) ghead[i]=-1;
	REP(i,n-1) {
		int a,b; scanf("%d%d",&a,&b); --a,--b;
		gnxt[2*i+0]=ghead[a],ghead[a]=2*i+0,gto[2*i+0]=b;
		gnxt[2*i+1]=ghead[b],ghead[b]=2*i+1,gto[2*i+1]=a;
	}
	printf("%s\n",solve()?"First":"Second");
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 305;
typedef long long ll;
int n,k,MOD,f[MAXN][MAXN],c[MAXN][MAXN],s[MAXN][MAXN];
inline int add(int x,int a)
{
    return x+a>=MOD?x+a-MOD:x+a;
}
inline void inc(int &x,int a)
{
    x+=a;
    if(x>=MOD)x-=MOD;
}
inline int mul(int x,int a)
{
    return (ll)x*a%MOD;
}
inline void init()
{
    c[0][0]=1;
    for(int i=1;i<=300;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j)
            c[i][j]=add(c[i-1][j-1],c[i-1][j]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&MOD);
    init();
    for(int i=0;i<=k;++i)f[1][i]=1,s[1][i]=k-i+1;
    for(int i=2;i<=n+1;++i){
        for(int j=0;j<=k;++j){
            for(int l=1;l<i;++l)
                inc(f[i][j],mul(f[i-l][j],mul(c[i-2][l-1],s[l][j+1])));
        }
        for(int j=k;j>=0;--j)
            inc(s[i][j],add(s[i][j+1],f[i][j]));
    }
    printf("%d\n",f[n+1][0]);
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll num(vector<ll> &R){
	ll N = R.size();
	vector<ll> perm(N, 0);
    REP(i, N) perm[i] = i+1;
	bool flag = true;
	ll res = 1;
	while(flag){
		bool ok = true;
		REP(i, N){
			if(R[i] != perm[i]) ok = false;
		}
		if(ok) return res;
		flag= next_permutation(perm.begin(), perm.end());
		res++;
	}
	return res;
}

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

    ll N;
    cin >> N;
    vector<ll> P(N), Q(N);
    REP(i, N) cin >> P[i];
    REP(i, N) cin >> Q[i];

    
	ll x = num(P);
	ll y = num(Q);
	cout << abs(x-y) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define lop(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int h, a;
	cin >> h >> a;
	float ans = ((ceil((float)h / (float) a)));
	cout << ans;

}

Measured memory_bytes: 3668
#include<iostream>

//関数の宣言
bool Input(int& h, int& w);
void Output(int h, int w);

int main()
{
	int h;
	int w;

	while (Input(h, w)){

		Output(h, w);

		std::cout << '\n';
	}

}
//入力関数
bool Input(int& h, int& w){
	std::cin >> h;
	std::cin >> w;

	if (h == 0 && w == 0){
		return false;
	}
	else{
		return true;
	}
}

//出力関数
void Output(int h, int w){
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			if (i % 2 == 1){
				if (j % 2 == 1){
					std::cout << '#';
				}
				else{
					std::cout << '.';
				}
			}
			else{
				if (j % 2 == 1){
					std::cout << '.';
				}
				else{
					std::cout << '#';
				}
			}
		}
		std::cout << '\n';
	}
}


Measured memory_bytes: 3052
#include<stdio.h>

int main()
{
    int len,a,b,c,num[3];
    int p1=0,p2=0,tmp=0;
    
    len=scanf("%d %d %d",&a,&b,&c);
    
    if(a>b)
    {
        if(b>c)
        {num[0]=a;num[1]=b;num[2]=c;}
        else
        {
            if(a>c)
            {num[0]=a;num[1]=c;num[2]=b;}
            else
            {num[0]=c;num[1]=a;num[2]=b;}
        }
    }
    else
    {
        if(a>c)
        {num[0]=b;num[1]=a;num[2]=c;}
        else
        {
            if(b>c)
            {num[0]=b;num[1]=c;num[2]=a;}
            else
            {num[0]=c;num[1]=b;num[2]=a;}
        }
    }
    
    p1 = num[0] - num[1];
    num[2] = num[2] + p1;
    tmp = num[0] - num[2];
    
    if(tmp % 2 == 0)
    {
        p2 = tmp / 2;
    }
    else
    {
        p1 = p1 + 1;
        tmp = tmp + 1;
        p2 = tmp / 2;
    }
    
    printf("%d\n",p1 + p2);
    
    return 0;
}


Measured memory_bytes: 128
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,K = map(int,input().split())

    d = []
    A = []
    for i in range(K):
        d.append(int(input()))
        A.append(list(map(int,input().split())))

    have = set([])

    for i in range(K):
        have = have | set(A[i])

    all = set([i for i in range(1,N+1)])

    trick = all - have

    print(len(trick))



main()


Measured memory_bytes: 9208
a=[]
n=int(input())
for i in range(2**n):
    a.append(int(input()))
while len(a)>1:
    t=[]
    for i in range(0,len(a),2):
        x,y=a[i],a[i+1]
        if x==y:
            t.append(x)
        else:
            t.append(abs(x-y))
    a=t
print(*t)

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

int main() {
	int n,w;
	long long int a[101][2];
	long long int dp[101][100001];
	memset(dp,0,sizeof(dp));
	scanf("%d%d",&n,&w);
	for(int i=0;i<n;i+=1){
	    scanf("%lld%lld",&a[i][0],&a[i][1]);
	}
	for(int i=1;i<=n;i+=1){
	    for(int j=1;j<=w;j+=1){
	        if(j-a[i-1][0]>-1){
	            dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1][0]]+a[i-1][1]);
	        }
	        else{
	            dp[i][j]=dp[i-1][j];
	        }
	    }
	}
	printf("%lld",dp[n][w]);
	return 0;
}


Measured memory_bytes: 79104
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int N = scan.nextInt();
        String S = scan.next();
        String T = scan.next();

        StringBuilder builder = new StringBuilder();

        for(int i = 0; i < N; i++) {
            builder.append(S.charAt(i));
            builder.append(T.charAt(i));
        }

        os.println(builder.toString());
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<bitset>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define LONG_INF 9223372036854775807
#define INF 1000000000LL
#define EPS 1e-10
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define dump(a) rep(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define all(v) v.begin(),v.end()
#define pb push_back


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

    int N;
    cin >> N;
    vector<int> x(N);
    rep(i, N) cin >> x[i];

    bool app=true;
    rep(i, N){
        if(x[i]%2==0){
            if((x[i]%3!=0) && (x[i]%5!=0)){
                app=false;
                break;
            }
        }
    }

    if(app==true) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
using namespace std;

int rate(int r){
    if(r < 400)return 0;
    if(r < 800)return 1;
    if(r < 1200)return 2;
    if(r < 1600)return 3;
    if(r < 2000)return 4;
    if(r < 2400)return 5;
    if(r < 2800)return 6;
    if(r < 3200)return 7;
    return 8;
}

int main(){
    int n, ans=0;
    cin >> n;
    vector<int> a(n), cnt(9, 0);
    rep(i, n){
        cin >> a.at(i);
        cnt.at(rate(a.at(i)))++;
    }
    rep(i, 8)if(cnt.at(i) > 0)ans++;
    if(ans == 0)cout << ans+1 << " " << ans+cnt.at(8);
    else cout << ans << " " << ans+cnt.at(8);
}  

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

int main(){
	ll N,K;
	cin >> N >> K;
	vector<int> A(N+1);
	for(int i=0; i<N; i++)cin >> A[i];
	int c = 1, l = 0;
	vector<int> s;
	vector<int> ord(N+1,-1);
	{
		int v = 1;
		while(ord[v] == -1){
			ord[v] = s.size();
			s.push_back(v);
			v = A[v-1];
		}
		c = s.size() - ord[v];
		l = ord[v];
	}

	if(K < l)cout << s[K] << endl;
	else {
		K -= l;
		K %= c;
		cout << s[l+K] << endl;
	}



	return 0;
}



Measured memory_bytes: 5884
#include<stdio.h>
int main()
{
    int N,i;
    float a,c=0;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    {
        if(i%2!=0)
        {
            c++;
        }
    }
    a=c/N;
    printf("%.6f",a);
}

Measured memory_bytes: 2184
#include<iostream>
using namespace std;
int main(){
  int n,a,b,count;
     int  A[10],B[10];
     count=0;
     for(int j=0;;j++){
       A[j]=0;
       B[j]=0;
    cin >> n;
    if(n==0)break;
    
    for(int i=0;i<n;i++){
      
      cin >> a >> b;
      if(a>b){
	A[j]+=a+b;
      }
      else if(a<b){
	B[j]+=a+b;
      }
      else if(a==b){
	A[j]+=a;
	B[j]+=b;
      }
      
    }cout << A[j] << " " << B[j] << endl;
    }
      for(int i=0;i<n;i++){
    cout << A[i] << " " << B[i] << endl;
    }
  return 0;
}

Measured memory_bytes: 1160
import java.util.*;

class Main {

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int w=0, k=0;
		int ws[] = new int[10], ks[] = new int[10];
		for(int i=0; i<10; i++) ws[i] = in.nextInt();
		for(int i=0; i<10; i++) ks[i] = in.nextInt();
		Arrays.sort(ks);
		Arrays.sort(ws);
		for(int i=0; i<3; i++) w += ws[9-i];
		for(int i=0; i<3; i++) k += ks[9-i];
		System.out.println(w + " " + k);
	}
	
}

Measured memory_bytes: 12000
f ::[Int]->Int->Int->[Int]
f [] _ _=[]
f (x:xs) old len=let len2=len + (abs(x-old))
                 in len2: f xs x len2

f2 ::[Int]->[Int]->Int->Int->[Int]
f2 [] _ _ _=[]
f2 (x:[]) _ len old=[len+(abs old)]
f2 (x:x2:xs) (y:y2:ys) len old=let len2=len+ (abs (x2-old))+y
                                   len3=len+ (abs (x-old))
                               in len2 : f2 (x2:xs) (y2:ys) len3 x
main = do
       e<-getLine
       e2<-getLine
       let xs=map read (words e2)::[Int]
           zs=tail $ reverse $ [read "0"::Int] ++ (f (reverse xs) 0 0)
       mapM_ putStrLn $ map show $ f2 xs zs 0 0

Measured memory_bytes: 54652
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let n = get_line().parse::<i64>().unwrap();

    let target = n % 10;

    if target == 2 || target == 4 || target == 5 || target == 7 || target == 9 {
        println!("hon");
    } else if target == 0 || target == 1 || target == 6 || target == 8 {
        println!("pon");
    } else {
        println!("bon");
    } 
}


Measured memory_bytes: 2092
#include <stdio.h>

//int judge(int * ,int );

int main()
{

    int i, j, m, n;
    int a[100005], b[50005];
    int le, mid, ri, key = 0;
    int cnt = 0, flag = 0;
    int num, tmp;

    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        scanf("%d", &a[i]);
    }

    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &b[i]);
    }

    /*
 
  for(i=0;i<m;i++){
 
      for(j=m-1;j >= i+1;j--){     
	if(a[j-1] > a[j]){
	  tmp = a[j-1];
	  a[j-1]=a[j];
	  a[j]=tmp;
	
	}
      }
  
    }
  */

    for (j = 0; j < n; j++)
    {
        le = 0;
        ri = m;
        key = b[j];

        //   printf("あああ\n");
        while (le < ri)
        {
            mid = (le + ri) / 2;

            if (key == a[mid])
            {
                cnt++;
                //	printf("あああhoge\n");
                break;
            }

            if (key > a[mid])
            {
                le = mid + 1;
                //	printf("いいいhoge\n");
                continue;
            }

            if (key < a[mid])
            {
                ri = mid;
                //  printf("うううhoge\n");
                continue;
            }
            mid = (le + ri) / 2;
        }
    }

    printf("%d\n", cnt);

    return 0;
}



Measured memory_bytes: 2288
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
const int INF = 1LL<<30;

char s[20][1010];
int h,w,k;

int cnt[11];
int solve(vector<int> grp){
    int res=0;
    int x=0;

    while(x<w){
        rep(c,11) cnt[c]=0;

        int nxt=x;
        for(int xx=x;xx<w;xx++){
            bool ng=false;
            rep(y,h){
                if(s[y][xx]=='1'){
                    cnt[grp[y]]++;
                    if(k<cnt[grp[y]]) ng=true;
                }
            }
            if(ng) break;
            nxt=max(nxt,xx+1);
        }

        if(nxt==x) return INF;
        x=nxt;

        res++;
    }

    return res-1;
}

int main() {
    cin>>h>>w>>k;
    rep(i,h){
        rep(j,w){
            cin>>s[i][j];
        }
    }

    
    int ans=INF;
    for(int bit=0;bit<(1<<h-1);bit++){
        vector<int> grp;
        int g=1,cnt=0;
        rep(i,h-1){
            grp.push_back(g);
            if(bit & (1<<i)){
                g++,cnt++;
            }
        }
        grp.push_back(g);

        ans=min(ans,solve(grp)+cnt);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#define rep(i,n) for(int i=0;i<((int)(n)); i++)
int n;
int dat[15][15];

int win[2][15];

int dfs(int i,int j){
	//printf("%d %d\n",i,j);
	if(j>=n){
		/*
		rep(i,n){
			printf("%d : %d %d\n",i,win[0][i],win[1][i]);
		}
		*/
		rep(i,n){
			if(win[0][i]!=win[1][i])return 0;
		}
		return 1;
	}
	int ti,tj;
	ti=i+1; tj=j;
	if(ti>=tj){
		ti=0; tj=j+1;
	}
	//printf("%d %d\n",ti,tj);
	if(dat[i][j])return dfs(ti,tj);
	int res=0;
	rep(t,2){
		win[t][i]++;
		win[1-t][j]++;
		if(win[t][i]*2<=n && win[1-t][j]*2<=n){
			res += dfs(ti,tj);
		}
		win[t][i]--;
		win[1-t][j]--;
	}
	return res;
}

int main(){
	for(;;){
		int m;
		scanf("%d%d",&n,&m);
		memset(dat,0,sizeof(dat));
		memset(win,0,sizeof(win));
		if(n==0)break;
		rep(i,m){
			int a,b;
			scanf("%d%d",&a,&b); a--; b--;
			dat[a][b]=dat[b][a]=1;
			win[0][a]++;
			win[1][b]++;
		}
		printf("%d\n",dfs(0,1));
	}
}


Measured memory_bytes: 2680
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define prin(num) cout << num << endl
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100005
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PA;
typedef map<ll, ll> Map;

int main(void) {
    ll N;
    cin >> N;
    string s;
    
    if(N==0) prin(0);
    
    while(N!=0) {
        if(N&1) {
            s='1'+s;
            N--;
        }else
            s='0'+s;
        N/=(-2);
    }
    
    cout << s << endl;
    
    
}

Measured memory_bytes: 256
rec = 0
rho = 0

while True:
    try:
        a, b, c  = map(int, input().split(','))
        if a == b:
            rho += 1
        else:
            if a**2 + b**2 - c**2 == 0:
                rec +=1
                
    except EOFError:
        break

print(rec)
print(rho)


Measured memory_bytes: 5596
//
//  main.cpp
//  zero
//
//  Created by 叶金炜 on 2019/4/2.
//  Copyright © 2019 okstal. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <string>
#define pi acos(-1)
using namespace std;
int main()
{
    string s;
    string s1="replace";
    string s2="reverse";
    string s3="print";
    int x,y;
    cin>>s;
    int n;
    cin>>n;
    while (n--) {
        string a;
        cin>>a;
        cin>>x>>y;
        if(a==s1)
        {
            string b;
            cin>>b;
            s.replace(x, y-x+1, b);
        }
        else if(a==s2)
        {
            string a2=s;
            int p=y;
            for(int i=x;i<=y;i++)
            {
                s[i]=a2[p];
                p--;
            }
        }
        else if(a==s3)
        {
            for(int i=x;i<=y;i++)
                printf("%c",s[i]);
            printf("\n");
        }
    }
    return 0;
}



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

int main(){
  int N;
  cin >> N;
  long long l[N],r[N],sum = 0;
  for(int i = 0;i < N;i++){
    cin >> l[i] >> r[i];
    sum += (r[i] - l[i] + 1);
  }

  cout << sum <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n;
  cin >> n;
  vector<vector<int>> a(n,vector<int>(n-1));
  rep(i,n){
    rep(j,n-1){
      cin >> a[i][j];
      a[i][j]--;
    }
    reverse(a[i].begin(), a[i].end()); //vectorは前から削除すると遅いので、reverseして試合が早いものを後ろにしておく。
  }
  vector<P> q; //queue.
  
  //試合が出来るかどうか確認するラムダ式
  auto check = [&](int i){
    if(a[i].size() == 0) return;
    int j = a[i].back(); //ベクターの後ろから対戦相手を取得。
    if(a[j].back() == i){ //jの次の対戦相手が自分だったら
      P p(i,j);
      if (p.second < p.first) swap(p.first, p.second); //1 vs 2, 2 vs 1が同じものとして扱われるように必ず左側が小さくなるようにしておく。（重複削除の準備）
      q.push_back(p); //queueに追加。
    }
  };
  
  rep(i,n){
    check(i);
  }
  int day = 0;
  while (q.size() > 0){
    day++;
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());

    vector<P> prevQ;
    swap(prevQ, q);
    for (P p : prevQ){
      int i = p.first, j = p.second;
      a[i].pop_back();//末尾削除
      a[j].pop_back();//末尾削除
    }
    for (P p : prevQ){
      int i = p.first, j = p.second;
      check(i);
      check(j);
    }
  }
  
  rep(i,n){ //全ての試合が行われたかどうかチェックする
    if(a[i].size() != 0){
      puts("-1"); //されていなければ-1を出力して終了
      return 0;
    }
  }
  cout << day << endl;
  
  return 0;
}

Measured memory_bytes: 4224
#include<stdio.h>

int en;
int on;
int N;

void input(){
	int i, t;
	en = 0;
	on = 0;
	scanf("%d", &N);
	for( i = 0; i < N; i++ ){
		scanf("%d", &t);
		if( t % 2 == 0 ){
			en++;
		}else{
			on++;
		}
	}
	return;
}

int main(){
	input();
	if( on % 2 == 0 || (on == 1 && en == 0) ){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}


Measured memory_bytes: 128
Q,H,S,D=map(int,input().split())
N=int(input())

one=min (4*Q,2*H,S)
if N==1:
    print(one)
else :
    if 2*one<=D:
        print(N*one)
    else:
        if N%2==0:
            print((N//2)*D)
        else:
            print((N//2)*D+one)

Measured memory_bytes: 9152
#include <iostream>
#include <vector>
#include <string>

using namespace std;

template<typename U>
int editDistance(const U& S, const U& T){
    int n = S.size();
    int m = T.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, max(n, m)));
    dp[0][0] = 0;
    for(int i=0;i<=S.size();i++){
        for(int j=0;j<=T.size();j++){
            if(i < S.size()){
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
            }
            if(j < T.size()){
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
            }
            if(i < S.size() && j < T.size()){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + (S[i] == T[j] ? 0 : 1));
            }
        }
    }
    return dp[n][m];
}

int main(){
    string s, t;
    while(cin >> s >> t){
        cout << editDistance(s, t) << endl;
    }
}


Measured memory_bytes: 6872
#include<stdio.h>

int main(){

int N,M,X;
int counter_a=0,counter_b=0;
scanf("%d%d%d",&N,&M,&X);
int A[M];
for (int i = 0; i < M; i++)
{
  scanf("%d",&A[i]);
  if (A[i]>X)
  {
   counter_a++; 
  }else if (A[i]<X)
  {
   counter_b++;
  }
}

counter_a < counter_b ? printf("%d",counter_a):printf("%d",counter_b);

return 0;

}


Measured memory_bytes: 1708
N, K = map(int, input().split())
footing = list(map(int, input().split()))


dp = [10 ** 10] * N
dp = dp + [10 ** 10] * 1000
dp[0] = 0

footing = footing + [0] * 1000
# give
'''
for i in range(N-1):
    for k in range(1, K+1):
        if dp[i+k] > dp[i] + abs(footing[i+k] - footing[i]):
            dp[i+k] = dp[i] + abs(footing[i+k] - footing[i])

print(dp[N-1])
'''
# get
for i in range(1,N):
    for j in range(1,min(K+1, i+1)): 
        dp[i] = min(dp[i],dp[i-j] + abs(footing[i]-footing[i-j])) 

print(dp[N-1])


Measured memory_bytes: 54112
#include <bits/stdc++.h>
#define modd 1000000007
using namespace std;
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl
#define scan(char_array) scanf("%[^\n]s",&char_array);
typedef long long int ll;
ll pow2[400001];
int main()
{
    pow2[0]=1;
    for(int i=1;i<=400000;i++)
    {
        pow2[i] = pow2[i-1]*2;
        pow2[i] = pow2[i]%modd;
        //cout<<pow2[i]<<endl;
    }
    ll ans=0;
    ll n;
    cin>>n;
    ll c[n];
    for(int i=0;i<n;i++)
    {
        cin>>c[i];
    }
    sort(c,c+n);
    for(ll i=0;i<n;i++)
    {
        ans = (ans + (n+1-i)*c[i])%modd;
        //dbg2(ans,i);
    }
    ans = (ans*pow2[2*(n-1)])%modd;
    cout<<ans<<"\n";
}

Measured memory_bytes: 4992
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <fstream>
#include <iostream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int cnt[26] = {};
  string s;
  while (getline(cin, s)) {
    for (size_t i = 0; i < s.size(); ++i) {
      if (!isalpha(s[i])) continue;
      if (isupper(s[i])) {
        s[i] = (char) tolower(s[i]);
      }
      ++cnt[s[i] - 'a'];
    }
  }

  for (int i = 0; i < 26; ++i) {
    cout << (char) (i + 'a') << " : " << cnt[i] << '\n';
    //if (i != 25) cout << '\n'; 
  }

  return 0;
}


Measured memory_bytes: 3212
n = [int(i) for i in input().split()]
seven = 0
five = 0
if n[0] == 5:
    five += 1
if n[0] == 7:
    seven += 1
if n[1] == 5:
    five += 1
if n[1] == 7:
    seven += 1
if n[2] == 5:
    five += 1
if n[2] == 7:
    seven += 1
if five == 2 and seven == 1:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 61852
import java.math.BigDecimal;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int d = a / b;
		int r = a % b;
		double f = (double)a / b;
		System.out.println(d + " " + r + " " + BigDecimal.valueOf(f).toPlainString());

	}

}

Measured memory_bytes: 26620
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>
#include <set>
//#include <bits/stdc++.h>
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
using namespace std;
#define ALL(X) X.begin(),X.end()
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
const int MOD=1000000007;
//const int MOD=998244353;
const int INTMAX=2147483647;
const ll LLMAX=9223372036854775807;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b;
    cin>>a>>b;
    if(a<0 && b<0){
        if((a-b+1)%2==0)cout<<"Positive"<<endl;
        else cout<<"Negative"<<endl;
    }
    else if(a>0 && b>0){
        cout<<"Positive"<<endl;
    }else{
        cout<<"Zero"<<endl;
    }
    
    return 0;
}


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

#define MAXN 200010
#define ll long long
#define mod 1000000007

using namespace std;

int n, ans;

string s[MAXN], str[MAXN];
map<string, int> m;
set<string> st;

bool cmp(string x, string y) {
	return x < y;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		m[s[i]]++;
		st.insert(s[i]);
	}
	int maxn = 0;
	for (int i = 1; i <= n; i++) {
		maxn = max(maxn, m[s[i]]);
	}
	for (int i = 1; i <= n; i++) {
		if (m[s[i]] == maxn && st.count(s[i])) {
			st.erase(s[i]);
			str[++ans] = s[i];
		}
	}
	sort(str + 1, str + ans + 1, cmp);
	for (int i = 1; i <= ans; i++) {
		cout << str[i] << endl;
	}
	
	return 0;
} 

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

const int MAX_N = 1e5+10;
int N, M;
int p[MAX_N];
int x[MAX_N], y[MAX_N];
int par[MAX_N];

int look(int x)
{
	if(x == par[x]) return x;
	else return par[x]=look(par[x]);
}

void comb(int x, int y)
{
	int a=look(x), b=look(y);
	if(a!=b){
		par[a]=b;
	}
}

void solve()
{
	for(int i=1;i<=N;++i) par[i]=i;
	for(int i=0;i<M;++i){
		comb(x[i], y[i]);
	}
	int ans = 0;
	for(int i=1;i<=N;++i){
		if(i == p[i] || (look(i)==look(p[i]))) ans++;
	}
	cout << ans << '\n';
} 

int main()
{
	cin >> N >> M;
	for(int i=1;i<=N;++i) cin >> p[i];
	for(int i=0;i<M;++i) cin >> x[i] >> y[i];
	solve();
	return 0;
}

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

ans = 0
count = 0
for i in range(1, N + 1):
    tmp = 0
    j = i
    while j % 2 == 0:
        j //= 2
        tmp += 1
    
    if tmp >= count:
        count = tmp
        ans = i
    
print (ans)

Measured memory_bytes: 2940
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX

#include <bits/stdc++.h>
#define db(x) cout << (x) << '\n';
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<double,ll> pdi;
typedef pair<ld,ld> pdd;
typedef pair<double,ll> pdi;
typedef pair<double,pii> pdp;
typedef pair<string,ll> psi;
typedef pair<ll,string> pls;
typedef pair<string,string> pss;
typedef pair<ll,pii> pip;
typedef pair<pii,pii> ppp;
typedef complex<ld> point;
typedef pair<point,int> ppi;
#define mod (int)(1e9+7)
#define eps (1e-9)
#define oo (ll)(0x3f3f3f3f)
#define pi acos(-1)
#define MAXN (ll)(1e3+5)

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

    int n;
    cin >> n;
    n%=1000;
    n=1000-n;
    if(n==1000)
        n=0;
    db(n)

    return 0;
}


Measured memory_bytes: 3636
import math

n = int(input())
ret = 0

for m in range(1, n+1):
    if m * m > n:
        break
    val1 = m * (m + (n//m)) * ((n//m) + 1 - m)
    ret += val1

sq = int(math.sqrt(n))
if (sq + 1) ** 2 <= n:
    sq += 1
val3 = sq * (sq + 1) * (2 * sq + 1) // 6
ret -= val3


print(ret)


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

int main(){
    int h,w;
    cin>>h>>w;
    vector<string> str(h);
    for(int i=0;i<h;i++){
        cin>>str[i];
    }
    for(int r=0;r<h;r++){
        for(int c=0;c<w;c++){
            if(str[r].at(c)=='.'){
                int tmp=0;
                if(r!=0&&c!=0)if(str[r-1].at(c-1)=='#')tmp++;//左上
                if(r!=0)if(str[r-1].at(c)=='#')tmp++;//上
                if(r!=0&&c!=w-1)if(str[r-1].at(c+1)=='#')tmp++;//右上
                if(c!=w-1)if(str[r].at(c+1)=='#')tmp++;//右横
                if(r!=h-1&&c!=w-1)if(str[r+1].at(c+1)=='#')tmp++;//右下
                if(r!=h-1)if(str[r+1].at(c)=='#')tmp++;//下
                if(r!=h-1&&c!=0)if(str[r+1].at(c-1)=='#')tmp++;//左下
                if(c!=0)if(str[r].at(c-1)=='#')tmp++;//左横
                str[r].at(c)=tmp+'0';
            }
        }
    }
    for(int i=0;i<h;i++){
        cout<<str[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3572
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = 1e9;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> a(M), key(M);
  rep(i, M) {
    int b;
    cin >> a[i] >> b;
    rep(j, b) {
      int tmp;
      cin >> tmp;
      tmp--;
      key[i] |= 1<<tmp;
    }
  }
  vector<int> dp(1<<N, INF);
  dp[0] = 0;
  rep(i, 1<<N) {
    rep(j, M)
      chmin(dp[i|key[j]], dp[i]+a[j]);
  }
  int ans = dp.back();
  if (ans == INF)
    ans = -1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repm(i, m, n) for (int i = m; i < (n); i++)
#define eps (1e-7)
#define inf (1e9)
#define pi (acos(-1))
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

    int a, b, c;
    cin >> a >> b >> c;
    int x;
    cin >> x;

    int count = 0;
    rep(i, a + 1)
    {
        int a_ = i * 500;
        rep(j, b + 1)
        {
            int b_ = j * 100;
            //cout << "b__ : " << b__ << endl;

            rep(k, c + 1)
            {
                int c_ = k * 50;
                //cout << "c__ : " << c__ << endl;

                if (a_ + b_ + c_ == x)
                {
                    count++;
                    break;
                }
            }
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)

const int MAX = 2000005;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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;
    }
}

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

ll g(int p,int q){
  ll res = 0;
  for(int i=1;i<=p+1;i++){
    res = (res+COM(i+q,q))%MOD;
  }
  return res;
}

 
int main() {
  COMinit();
  int r1,r2,c1,c2;
  cin >> r1 >> c1 >> r2 >> c2;
  ll a,b,c,d;
  a = g(r2,c2);
  b = g(r2,c1-1);
  c = g(r1-1,c2);
  d = g(r1-1,c1-1);
  ll ans = ((a+d)%MOD-(b+c)%MOD+MOD)%MOD;
  cout << ans << endl;
  
  
  return 0;
}





Measured memory_bytes: 47104
void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <functional>
#include <map>
#include <string>

using namespace std;

typedef pair<int, int> pii;
int dp[100000];
int Q,N;
vector<int> ans;

void solve() {
	string s;
	cin >> N >> Q >> s;
	dp[0] = 0;
	for (int i = 1; i < N; i++) {
		if (s[i] == 'C' && s[i - 1] == 'A')dp[i] = dp[i - 1] + 1;
		else dp[i] = dp[i - 1];
	}
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		ans.push_back(dp[r-1] - dp[l-1]);
	}
	for (auto itr = ans.begin(); itr != ans.end(); itr++) {
		cout << *itr << endl;
	}
	return;
}

Measured memory_bytes: 1912
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 0x7fffffff
#define mod 998244353
#define eps 1e-20
ll read()
{
    ll tmp=0; char c=getchar(),f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
    for(;'0'<=c&&c<='9';c=getchar())tmp=tmp*10+c-'0';
    return tmp*f;
}
using namespace std;
struct edge{
	int to,w,nxt;
}e[400010];
int fir[100010],vis[100010]={0};
int q[100010];
ll dist[100010];
int n,m,tot=0;
void add(int x,int y,int z){e[tot].to=y; e[tot].w=z; e[tot].nxt=fir[x]; fir[x]=tot++;}
int bfs(int s)
{	
	int h=1,t=1,i;
	q[1]=s; vis[s]=1; dist[s]=0;
	while(h<=t){
		for(i=fir[q[h]];~i;i=e[i].nxt)
			if(vis[e[i].to]){
				if(dist[q[h]]+e[i].w!=dist[e[i].to])return 0;
			}
			else{
				q[++t]=e[i].to; vis[e[i].to]=1; dist[e[i].to]=dist[q[h]]+e[i].w;
			}
		++h; 
	}
	return 1;
}
int main()
{
	int i;
	n=read(); m=read();
	for(i=1;i<=n;i++)fir[i]=-1;
	for(i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		add(x,y,z); add(y,x,-z);
	}
	int flag=1;
	for(i=1;i<=n;i++)vis[i]=dist[i]=0;
	for(i=1;i<=n;i++)
		if(!vis[i]){
			if(!bfs(i))flag=0;
		}
	if(flag)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 6784
#include<stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  int h[n];
  int max=0;
  int ans=0;
  for(int i=0;i<n;i++){
    scanf("%d",&h[i]);
    if(max<=h[i]){
      max=h[i];
      ans++;
    }
  }
  printf("%d",ans);
}

Measured memory_bytes: 128
a,b,k = map(int,input().split())
if (b-a)<2*k:
	for i in range(a,b+1):
		if (i-a)<k or (b-i)<k:
			print(i)
else:
	for i in range(0,k):
		print(a+i)
	for i in range(k-1,-1,-1):
		print(b-i)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll n;
	cin>>n;
	
	int ans=0;
	rep(x,2,1000005){
		if (n%x==0){
			int cnt=0;
			while (n%x==0){
				n/=x;
				cnt++;
			}
			
			int curr=1;
			while (curr<=cnt){
				cnt-=curr;
				curr++;
				ans++;
			}
		}
	}
	
	if (n!=1) ans++;
	
	cout<<ans<<endl;
}

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

int main() {
    int n;
    string s;

    bool flg = false;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> s;

        if (s == "Y" && i > 3)
            flg = true;
    }

    if (flg)
        cout << "Four";
    else
        cout << "Three";
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
bool ok[400100];

int main() {
    int n; cin >> n;
    int A[n];
    for (int i= 0; i < n; i++) cin >> A[i];
    for (int bit = 0; bit < (1<<n); bit++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (bit & (1<<i)) {
                sum += A[i];
            }
        }
        ok[sum] = true;
    }
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int m; cin >> m;
        if (ok[m]) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}


Measured memory_bytes: 3100
def do_dp(N, Adj):
    univ = 2 ** N - 1
    dp = [[0] * N for i in range(univ + 1)]
    dp[1][0] = 1

    for S in range(2, univ + 1):
        for v in range(N):
            S2 = S & (univ ^ (1 << v))
            for u in range(N):
                if ((1 << u) & S2) and Adj[u][v]:
                    dp[S][v] += dp[S2][u]
    
    ans = sum(dp[univ][u] for u in range(1, N))

    return ans

def solve():
    N, M = map(int, input().split())
    Adj = [[0] * N for i in range(N)]

    for i in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        Adj[a][b] = 1
        Adj[b][a] = 1

    ans = do_dp(N, Adj)
    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
    double  m, b=0, c=0;
    int n;
    cin>>n>>m;
    double a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(int i=0; i<n; i++)
    {
        b+=a[i];
    }
    for(int i=0; i<n; i++)
    {
        if(a[i]/b >= 1/(4*m))
        {
            c++;
        }
    }
    if(c>=m)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1e16;
#define int long long

const int MAX_N = 1010;



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m; cin >> n >> m;
	if (abs(n - m) >= 2)cout << 0 << endl;
	else if (abs(n - m) == 1) {
		int ans = 1;
		for (int i = n; i >= 1; i--) {
			ans *= i; ans %= MOD;
		}
		for (int i = m; i >= 1; i--) {
			ans *= i; ans %= MOD;
		}
		cout << ans << endl;
	}
	else {
		int ans = 2;
		for (int i = n; i >= 1; i--) {
			ans *= i; ans %= MOD;
		}
		for (int i = m; i >= 1; i--) {
			ans *= i; ans %= MOD;
		}
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256