akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#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 ln '\n'
const double PI = acos(-1.0);
const long long MOD = 1000000007LL;
//const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
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; }
///////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int A,B; cin >> A >> B;
    cout << max(0,A-2*B) << ln;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  int a,b;
  cin >> a;
  for(int i = 1;i < 10;i++){
    for(int j = 1;j < 10;j++){
      if(a == (i * j)){
        cout << "Yes";
        return 0;
      }
    }  
  }
  cout << "No";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    string s;
    cin >> s;
    sort(all(s));
    if(s[0] == s[1] && s[2] == s[3] && s[1]!=s[2])
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rrep(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr ll INF = (ll)1e9;
constexpr ll mod = (ll)1e9 + 7;
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


int main() {
	init();

	int N; cin >> N;
	vector<ll>A(N);
	rep(i, 0, N)cin >> A[i];
	sort(all(A),greater<ll>());
	ll ans = A[0];
	int i = 2;
	priority_queue<pair<ll, ll>>pq;
	rep(i,0,2)pq.emplace(A[1], A[0]);
	while (i < N) {
		auto v = pq.top();
		pq.pop();
		ans += v.first;
		pq.emplace(min(A[i], v.first), max(A[i], v.first));
		pq.emplace(min(A[i], v.second), max(A[i], v.second));
		++i;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 8968
A = 3.times.map{ gets.split }
N = gets.to_i
B = {}
$<.each{|ln| B[ln.chomp] = true }

puts (3.times.any?{|i|
	3.times.all?{|j|
		B[A[i][j]]
	}
} or 3.times.any?{|j|
	3.times.all?{|i|
		B[A[i][j]]
	}
} or 3.times.all?{|ij|
	B[A[ij][ij]]
} or 3.times.all?{|_|
	B[A[2-_][_]]
}) ? 'Yes' : 'No'


Measured memory_bytes: 1788
#include <stdio.h>

int main(){
  int A, B, K;
  int count = 1;
  int x = 100;
  int ans;
  int flag = 0;
  scanf("%d %d %d",&A,&B,&K);

  while(1){
    if(A % x == 0 && B % x == 0){
      ans = x;
      if(count == K){
        flag = 1;
        break;
      }else{
        count ++;
      }
    }
    if(flag == 1){
      break;
    }
    x --;
  }

  printf("%d",ans);

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;

    if (e - a <= k)
        cout << "Yay!" << endl;
    else
        cout << ":(" << endl;

    return 0;
}

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

using namespace std;

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

  int A[N];
  int visited[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i]--;
    visited[i] = -1;
  }

  int presentPoint = 0;
  int nextPoint = -1;
  vector<int> loop = {0};
  int loopstart = -1;
  int loopsize = -1;
  for (int i = 0; i < K; i++) {
    nextPoint = A[presentPoint];
    if (visited[nextPoint] != -1) {
      loopstart = visited[nextPoint];
      loopsize = i - visited[nextPoint];
      break;
    }
    presentPoint = A[presentPoint];
    visited[presentPoint] = i;
    loop.emplace_back(presentPoint);
  }

  int remaincount = (K - loopstart) % loopsize;
  if (remaincount != 0) {
    presentPoint = loop[loopstart + remaincount];
  }

  cout << presentPoint + 1 << endl;
  return 0;
}

Measured memory_bytes: 5780
S = input()
Q = int(input())
B = []
C = []
t = 1
for i in range(Q):
    A = input()
    if A=="1":
        t*=-1
    else:
        AL = list(A.split())
        if AL[1]=="1":
            if t==1:
                B.append(AL[2])
            else:
                C.append(AL[2])
        elif AL[1]=="2":
            if t==1:
                C.append(AL[2])
            else:
                B.append(AL[2])

B = ''.join(B)
C = ''.join(C)

if t==-1:
    print(C[::-1]+S[::-1]+B)
else:
    print(B[::-1]+S+C)

Measured memory_bytes: 70104
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int H, W, K, g[15][1005];
int n, m, a[15][1005], sum[15][1005], dp[1005];
int q[2005];
bool check(int i, int j)   //j能否作为i的决策
{
    for(int k = 1; k <= n; k++)
    {
        if(sum[k][i] - sum[k][j] > K)
            return false;
    }
    return true;
}
int solve()
{
    for(int i = 1; i <= n; i++)
    {
        sum[i][0] = 0;
        for(int j = 1; j <= m; j++)
            sum[i][j] = sum[i][j-1] + a[i][j];
    }
    int f = 0, r = 0;
    q[r++] = 0;
    dp[0] = 0;
    for(int i = 1; i <= m; i++)
    {
        while(f < r && !check(i, q[f]))
            f++;
        if(f == r)
            return INF;
        dp[i] = dp[q[f]] + 1;
        while(f < r && dp[q[r-1]] >= dp[i])
            r--;
        q[r++] = i;
    }
    return dp[m] - 1;
}
int main()
{
    scanf("%d %d %d", &H, &W, &K);
    for(int i = 1; i <= H; i++)
    {
        getchar();
        for(int j = 1; j <= W; j++)
        {
            char ch = getchar();
            if(ch == '0')
                g[i][j] = 0;
            else
                g[i][j] = 1;
        }
    }
    int ans = INF;
    for(int s = 0; s < (1<<(H-1)); s++)
    {
        n = 1, m = W;
        memset(a, 0, sizeof(a));
        for(int j = 1; j <= m; j++)
            a[n][j] += g[1][j];
        for(int i = 1; i <= H-1; i++)
        {
            if((s>>(i-1))&1)
                n++;
            for(int j = 1; j <= m; j++)
                a[n][j] += g[i+1][j];
        }
        ans = min(ans, solve() + n - 1);
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
using namespace std;
 
int main(){
  int A, B, C, K, nb, nc, t=0;
  cin >> A >> B >> C >> K;
  nb = B;
  nc = C;
  for(;;){
    if(nb <= A){
      nb = nb * 2;
      t = t + 1;
    }
    else{
      break;
    }
  }
  for(;;){
    if(nc <= nb){
    nc = nc * 2;
    t = t + 1;
    }
    else{
      break;
    }
  }
  if(t <= K){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }  
}

Measured memory_bytes: 3132
#include <iostream>
#include <queue>
#include <algorithm>
#include <climits>
#include <stack>
#include <vector>
#include <random>
#include <string.h>
#include <stdio.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef pair<int, int> ii;
typedef pair<long double, int> id;
typedef pair<long long, long long> llp;
const int N = 1e5+1;
int n, k, t;
int a[N][3], dp[N][3];
int main() {
    //freopen("ee.inp", "r", stdin);
    //freopen("ee.OUT", "w", stdout);
    fastIO;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];
    dp[1][0] = dp[1][1] = dp[1][2] = 0;
    for(int i=2;i<=n+1;i++) {
        dp[i][0] = max(dp[i-1][1]+a[i-1][1], dp[i-1][2]+a[i-1][2]);
        dp[i][1] = max(dp[i-1][0]+a[i-1][0], dp[i-1][2]+a[i-1][2]);
        dp[i][2] = max(dp[i-1][0]+a[i-1][0], dp[i-1][1]+a[i-1][1]);
    }
    cout << max(max(dp[n+1][0], dp[n+1][1]), dp[n+1][2]);
}


Measured memory_bytes: 5972
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

final class Main {

    private Main() {
    }

    public static void main(final String[] argv) throws IOException {
        final BufferedReader inputReader =
                new BufferedReader(new InputStreamReader(System.in));
        System.out.println(inputReader.readLine().toUpperCase());
    }
}

Measured memory_bytes: 9336
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){

    int a,b,c,k;

    cin >> a >> b >> c >> k;

    int max = std::max(a, std::max(b,c));
    int ans = a + b + c - max;

    for(int i=0;i<k;i++){
        max *= 2;
    }

    cout << ans+max << endl;

    return 0;
}


Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {n: usize, s: String};
    let s: String = s;

    let mut count = 0;

    for si in 0..n - 2 {
        if &s[si..si + 3] == "ABC" {
            count += 1;
        }
    }

    println!("{}", count)
}


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

int main(){

	int N, W;
	cin >> N >> W;

	int w[101];
	int* v = new int[1001];

	for (int i = 0; i < N; i++)
		cin >> v[i] >> w[i];


	int DP[102][10001];

	for (int j = 0; j <= W; j++)
		DP[0][j] = 0;

	for (int i = 1; i <= N; i++)
		for (int j = 0; j <= W; j++)
			if (j < w[i - 1])
				DP[i][j] = DP[i - 1][j];
			else{
				if (DP[i - 1][j]>DP[i][j - w[i - 1]] + v[i - 1])
					DP[i][j] = DP[i - 1][j];
				else
					DP[i][j] = DP[i][j - w[i - 1]] + v[i - 1];
			}


			cout << DP[N][W] << endl;

			delete[] v;

			return 0;
}

Measured memory_bytes: 5148
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if (a%2 == 0 || b%2 == 0 || c%2 == 0)cout << 0 << endl;
    else {
        vector<ll>abc = {a,b,c};
        sort(all(abc));
        cout << abc[0] * abc[1] << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)
const int INF=1e9;
using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  int n;
  cin>>n;
  int a[n];
  rep(i,0,n) cin>>a[i];
  int ans=a[0];
  rep(i,1,n) ans=__gcd(ans,a[i]);
  cout<<ans<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 4016
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
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; }


int main() {
    ll n, m; cin >> n >> m;
    string s, t; cin >> s >> t;
    ll LCM = n / __gcd(n, m) * m;
    map<int, char> mp;
    bool fg = true;
    rep(i, n){
        mp[i*(LCM/n)] = s[i];
    }
    rep(i, m){
        int index = i*LCM/m;
        if(mp[index]>= 'a' && mp[index] <= 'z' && mp[index] != t[i]){
            fg = false; break;
        }
    }
    if(fg) cout << LCM << ln;
    else cout << -1 << ln;
}


Measured memory_bytes: 8192
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
using namespace std;

const double PI=acos(-1);

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

    vector<int> l(m);
    for(int i = 0; i < m; i++){
        cin >> l[i];
    }
    int left = 0, right = 0;
    for(int i = 0; i < m; i++){
        if(l[i] < x) left++;
        else right++;
    }

    cout << min(left, right) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    long long X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
    if (X / D > K) {
        X -= D * K;
    }
    else {
        K -= X / D;
        X %= D;
        X -= D * (K % 2);
    }
    cout << abs(X) << endl;
}


Measured memory_bytes: 3632
var P = 2L

fun mod(x: Long) = if (x >= 0) x % P else (P - ((-x) % P)) % P
fun modPlus(x1: Long, x2: Long) = (x1 + x2) % P
fun modMinus(x1: Long, x2: Long) = (x1 + P - x2) % P
fun modTimes(x1: Long, x2: Long) = (x1 * x2) % P

fun main(args: Array<String>) {
  val (n, pInt) = readLine()!!.split(" ").map { it.toInt() }
  P = pInt.toLong()

  val pTable = LongArray(n + 1, { 0 })
  pTable[0] = 2L
  for (i in 1..n) {
    pTable[i] = modTimes(pTable[i - 1], pTable[i - 1])
  }

  val cTable = Array(n + 1, { LongArray(n + 1, { 0L })})
  cTable[0][0] = 1L
  for (i in 1..n) {
    for (j in 0..i) {
      cTable[i][j] = if (j == 0) 1L else modPlus(cTable[i - 1][j - 1], cTable[i - 1][j])
    }
  }

  val gTable = Array(n + 1, { LongArray(n + 1, { 0 })})
  gTable[0][0] = 1
  for (i in 1..n) {
    for (j in 0..i) {
      gTable[i][j] =
          if (j == 0 || j == i) 1
          else modPlus(gTable[i - 1][j - 1], modTimes(gTable[i - 1][j], (j + 1).toLong()))
    }
  }
//  println("gTable[2][0]" + gTable[2][0])
//  println("gTable[2][1]" + gTable[2][1])
//  println("gTable[2][2]" + gTable[2][2])
//  println("gTable[3][1]" + gTable[3][1])
//  println("gTable[4][2]" + gTable[4][2])

  val hTable = Array(n + 1, { LongArray(n + 1, { 0 }) })
  for (i in 0..n) {
    for (j in 0..n) {
      hTable[i][j] =
          if (i == 0 || j == 0) 1
          else if (i == 1) modTimes(hTable[1][j - 1], 2)
          else modTimes(hTable[i - 1][j], hTable[1][j])
    }
  }


  val fTable = LongArray(n + 1, { 0 })
  for (i in 1..n) {
    var acc = 0L
    for (x in 0..i) {
      acc = modPlus(acc, modTimes(gTable[i][x], hTable[x][n - i]))
    }
    fTable[i] = modTimes(pTable[n - i], acc)
  }

  var ans = pTable[n]
  for (k in 1..n) {
    val sign = if (k % 2 == 0) 1 else mod(-1)
    ans = modPlus(ans, modTimes(modTimes(sign, cTable[n][k]), fTable[k]))
  }

  println(ans)
}

Measured memory_bytes: 301368
Suit = ["S","H","C","D"]
deck = []


for i in range(4):
    for n in range(1,14):
        tmp = (Suit[i]+" "+str(n))
        deck.append(tmp)

#print (deck)

u = int(input())

for _ in range(u):
    s = str(input())
    if s in deck:
        deck.remove(s)

for y in range(len(deck)):
    print('{}'.format(deck[y]))


Measured memory_bytes: 5596
import sys

inf = int(1e12)

def shortestPath(graph, s):
    n = len(graph)
    dist = [inf for _ in range(n)]
    dist[s] = 0

    for i in range(n):
        for u in range(n):
            for v, cost in graph[u]:
                newDist = dist[u] + cost
                if dist[u] != inf and newDist < dist[v]:
                    if i == n - 1:
                        return None
                    dist[v] = newDist
    return dist

def main():
    v, e, s = map(int, input().split())
    
    graph = [[] for _ in range(v)]
    
    for i in range(e):
        a, b, cost = map(int, input().split())
        graph[a].append((b, cost))
            
    dist = shortestPath(graph, s)

    if not dist:
        print("NEGATIVE CYCLE")
    else:
        for d in dist:
            if d >= inf:
                print("INF")
            else:
                print(d)
main()

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

int main(){
    ll n;
    cin >> n;
    ll a[n+1],b[n];
    for(ll i = 0; i < n+1; i++){
        cin >> a[i];
    }
    for(ll i = 0; i < n; i++){
        cin >> b[i];
    }

    ll ans = 0;

    for(ll i = 0; i < n; i++){
        if(b[i] <= a[i]){
            ans += b[i];
            a[i] -= b[i];
            b[i] = 0;
        }
        else if(b[i] > a[i] && b[i] < a[i] + a[i+1]){
            ans += b[i];
            a[i+1] += (a[i] - b[i]);
            a[i] = 0;
            b[i] = 0;
        } else if(b[i] >= a[i+1]+ a[i]){
            ans = ans + a[i] + a[i+1];
            a[i] = 0;
            a[i+1] = 0;
            b[i] = b[i] - a[i] - a[i+1];
        }

    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	for(int n;cin>>n,n;){
		vi a(n);
		rep(i,n)
			cin>>a[i];
		vector<pii> res;
		res.push_back(mp(a[0],a[0]));
		repi(i,1,n){
			if(res.back().second+1==a[i])
				res.back().second++;
			else
				res.push_back(mp(a[i],a[i]));
		}
		rep(i,res.size()){
			if(res[i].first==res[i].second)
				printf("%d",res[i].first);
			else
				printf("%d-%d",res[i].first,res[i].second);
			printf("%c",i==res.size()-1?'\n':' ');
		}
	}
	
	return 0;
}

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

#define int long long int
#define double long double
#define pb push_back
#define fi first
#define se second
#define vii vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define pq priority_queue<int>
#define test int tcase; cin>>tcase; for(int tc = 1; tc <= tcase; tc++)
#define inp(a,n,f) int a[n+f];for(int hh=f;hh<n+f;hh++)cin>>a[hh];
#define prdec(k) cout<<fixed<<setprecision(k);
#define mem(a,k) memset(a,k,sizeof(a))
#define ub upper_bound
#define lb lower_bound
#define mii map<int,int>
#define all(v) v.begin(),v.end()
#define inf LLONG_MAX


signed main()
{
	#ifndef ONLINE_JUDGE
   		freopen("input.txt","r",stdin);
   		freopen("output.txt","w",stdout);   
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

   	string s;
   	cin>>s;
   	int res=0;
   	for(char x:s)
   		res+=x-'0';
   	res%9==0?cout<<"Yes":cout<<"No";
	return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    sort(p.begin(), p.end());
    rep(i,k) ans += p[i];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, a[200010], b[200010];
int mi, ma;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i] >> b[i];
	sort(a, a + n);
	sort(b, b + n);
	if (n % 2)mi = a[n / 2], ma = b[n / 2];
	else mi = a[n / 2] + a[n / 2 - 1], ma = b[n / 2] + b[n / 2 - 1];
	cout << ma - mi + 1 << endl;
}

Measured memory_bytes: 6752
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    int a, b;
    cin >> a >> b;
    if(a + b == 15) cout << '+' << endl;
    else if(a * b == 15) cout << '*' << endl;
    else cout << 'x' << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

int main()
{
  int n,a[100000];
  cin>>n;
  rep(i,n) cin>>a[i];
  sort(a,a+n);
  bool flag=true;

  if(n%2==0)
  {
    int i=n-1;
    while(i>0)
    {
      if(a[i]==i && a[i-1]==i) i-=2;
      else
      {
        flag=false;
        break;
      }
    }
  }
  else
  {
    int i=n-1;
    while(i>0)
    {
      if(i==0)
      {
        if(a[i]!=0) flag=false;
      }
      else
      {
        if(a[i]==i && a[i-1]==i) i-=2;
        else
        {
          flag=false;
          break;
        }
      }
    }
  }

  int ans=1,cnt=0;
  while(cnt<n/2)
  {
    ans*=2;
    ans%=inf;
    cnt++;
  }

  if(flag) cout<<ans;
  else cout<<0;
  cout<<endl;
}

Measured memory_bytes: 640
#!/usr/bin/env python3
import sys


def solve(N: int, A: int, B: int, C: int, l: "List[int]"):
    mn = 1e9
    for i in range(1 << N):
        for j in range(1 << N):
            n = []
            a = []
            b = []
            c = []
            for k in range(N):
                if (i >> k) % 2 == 0 and (j >> k) % 2 == 0:
                    n.append(k)
                if (i >> k) % 2 == 0 and (j >> k) % 2 == 1:
                    a.append(k)
                if (i >> k) % 2 == 1 and (j >> k) % 2 == 0:
                    b.append(k)
                if (i >> k) % 2 == 1 and (j >> k) % 2 == 1:
                    c.append(k)
            if len(a) == 0 or len(b) == 0 or len(c) == 0:
                continue
            else:
                m = 10 * (len(a) + len(b) + len(c) - 3) + abs(A - sum([l[aa] for aa in a])) + abs(B - sum([l[bb] for bb in b])) + abs(C - sum([l[cc] for cc in c]))
                if mn > m:
                    mn = m
    print(mn)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    l = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A, B, C, l)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define pq priority_queue <pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> 
#define graph1 vector<vector<pair<ll,ll>>>
#define graph vector<vector<ll>>
#define pq1 priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll,ll>>>, greater<pair<ll, pair<ll, ll>>>>
#define loop(i,a,b) for (ll i = a; i < b; i++)
#define fast ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
bool visited[100005];
graph g;
ll maxx = 0;
void dfs(int node,  int dp[], bool vis[])
{
	
	vis[node] = true;

	for (int i = 0; i < g[node].size(); i++) {

		if (!vis[g[node][i]])
			dfs(g[node][i], dp, vis);

		dp[node] = max(dp[node], 1 + dp[g[node][i]]);
	}
}


int findLongestPath(int n)
{
	
	int dp[n + 1];
	memset(dp, 0, sizeof dp);

	
	bool vis[n + 1];
	memset(vis, false, sizeof vis);

	
	for (int i = 1; i <= n; i++) {
		if (!vis[i])
			dfs(i, dp, vis);
	}

	int ans = 0;

	// Traverse and find the maximum of all dp[i] 
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dp[i]);
	}
	return ans;
}

int main()
{

	ll n, m;
	cin >> n >> m;
	g.resize(n + 1);
	memset(visited, false, sizeof(visited));
	loop(i, 0, m)
	{
		ll u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}
	cout << findLongestPath(n);
}

Measured memory_bytes: 8960
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
  int a[3];
  rep(i,3) cin >> a[i];
  
  sort(a,a+3);
  
  int ans = abs(a[0]-a[1])+abs(a[1]-a[2]);
  
  cout << ans << endl;
  
  return 0;
}
                      
                      

Measured memory_bytes: 256
#include <iostream>

using namespace std;
bool pr(string s){
int    n=s.size();
if (n%2==1) return 0;
for(int i=0;i<n/2;i++) if(s[i]!=s[i+n/2]) return 0;
return 1;
}
int main()
{
    string s;
    cin>>s;
    s.resize(s.size()-1);
    while(!pr(s)){
     s.resize(s.size()-1);
    }
    cout<<s.size();
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    bool ish = false;
    rep (i, s.size()) {
        // ish = (s[i] == '?');
        if (s[i] == '?') cout << 'D';
        // if (s[i] == '?') cout << (isd ? 'P' : 'D');
        else cout << s[i];
        // isd = (s[i] == 'D');
    }
    cout << "\n";
    return 0;
}

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

int main(){
    int number;
    cin >> number;
    int a,b,c,d;
    a = number/1000;
    b = (number/100)%10;
    c = (number/10)%10;
    d = number%10;
    if(a==b||b==c||c==d) cout << "Bad" << endl;
    else cout << "Good" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int s1 , s2 , s3 ;
  cin >> s1;
  int H , J , I;
  H=s1/100;
  s1=s1%100;
  J=s1/10;
  s1=s1%10;
  I=s1;
  cout << H + J + I << endl ;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long

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

    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i ++) cin >> a.at(i);

    int ans = 10000000000;
    int sum;

    for(int i = -100;i <= 100;i ++){
        sum = 0;
        for(int j = 0;j < n;j ++){
            sum += (a.at(j) - i) * (a.at(j) - i);
        }
        ans = min(ans, sum);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
k=int(input())
if k==1:
  print(1)
  exit()
if k%2==0:
  print(-1)
  exit()
if k%5==0:
  print(-1)
  exit()
if k==7:
  print(1)
  exit()
a=7%k
for i in range(10**6+50):
  a=(a*10+7)%k
  if a==0:
    break
print(i+2)

Measured memory_bytes: 63140
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vint;
#define rep(i,n) for (ll i = 0; i < (ll)(n); ++i)
#define rrep(i,j,n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define mrep(i,n) for (ll i = (ll)(n-1); i >= 0; i--)
#define be(v) (v).begin(), (v).end()
#define dcout cout << fixed << setprecision(20) 
ll INF = 1LL << 60;
ll mod = 1e9 + 7;

int main(){
	int n; cin >> n;
	vector<int> s(n);
	int sum=0;
	rep(i,n) {
		cin >> s[i];
		sum=sum+s[i];
	}
	ll ans=INF;
	rep(i,n) {
		int ss=sum-(s[i]/2);
      if(ans>ss) ans=ss;
		//ans=min(ans,ss);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
list_a = [int(x) for x in input().split()]
list_a_str = [str(s) for s in list_a]
ans = 1

for i in range(0, n):
    if list_a_str[i] in '0':
        print('0')
        exit()

for i in range(0, n):
    ans *= list_a[i]
    if ans > 10 ** 18:
        print('-1')
        exit()

else: print(ans)

Measured memory_bytes: 21908
open System

let a, b = stdin.ReadLine().Split() |>fun list -> (list.[0], list.[1])

[ 
    (float a * 100.0 / 8.0 |> Math.Ceiling |> int)
        ..
        (float ( int a + 1 ) * 100.0 / 8.0 |> Math.Ceiling |> int) - 1 
]
|> Set.ofList
|> Set.intersect (
    [ 
        ( float b * 100.0 / 10.0 |> Math.Ceiling |> int )
            ..
            ( float ( int b + 1 ) * 100.0 / 10.0 |> Math.Ceiling |> int ) - 1
    ]
    |> Set.ofSeq
)
|> function
| set when set.IsEmpty -> -1
| set -> set |> Set.minElement
|> stdout.WriteLine


Measured memory_bytes: 14300
#include <cstdio>
#include <iostream>
int num[200001];
int main(int argc, const char * argv[]) {
   
    long long total = 0;
    
    
    
    int n,t;
    scanf("%d %d",&n,&t);
    
    
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
    }
    
    long long start = num[0];
    long long end = start+t;
    
    for(int i=1;i<n;i++){
       
        if(end >= num[i]){
            end = num[i]+t;
        }else{
            total += end-start;
            start = num[i];
            end = start+t;
        }
    }
    total += end-start;
    printf("%lld\n",total);
    
    
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(){
	int x,a,b;
	int jaraka,jarakb;
	scanf("%d %d %d",&x,&a,&b);
	jaraka = x-a;
	jarakb = x-b;
	if(jaraka<0){
		jaraka *= -1;
	}
	if(jarakb<0){
		jarakb *= -1;
	}
	if(jaraka>jarakb){
		printf("B\n");
	}
	else{
		printf("A\n");
	}
	
     return 0;
}

Measured memory_bytes: 2084
import sys
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
if N == K:
    print(0)
    sys.exit()
_A = [0] * N
for a in A:
    _A[a - 1] += 1
_A.sort()
print(sum(_A) - sum(_A[N-K:]))


Measured memory_bytes: 32292
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rrep(i,n) for (int i = 1; i <= (n); i++)
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
  ll n,k;
  cin >> n >> k;
  ll a[n];
  rep(i,n) cin >> a[i];
    ll ans=1e18;
  rep(bit,1<<n){
    if(__builtin_popcount(bit)<k || bit%2==0)continue;
    vector<ll> s;
    rep(i,n) {
      if(bit>>i&1) s.push_back(i);
    }
    ll l = 0,total = 0;
    s.push_back(n);
    rep(j,s.size()-1){
        l = max(l+1,*max_element(a+s[j],a+s[j+1]));
        total += l - a[s[j]];
    }
    ans = min(ans,total);
  }
  cout << ans << endl;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010

string S;

signed main()
{
    cin >> S;
    int g = 0, p = 0;
    REP(i, S.length()) {
        if(S[i] == 'g') { g++; }
        else { p++; }
    }
    printf("%lld\n", (g - p) / 2);
    return 0;
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
  public static void main(String[] args) {
    List<Integer> targetList = new ArrayList<Integer>();

    createNumsList(targetList);
    bubbleSort(targetList);

    printResult(targetList);
  }

  private static void createNumsList(List<Integer> targetList) {
    Scanner sc = new Scanner(System.in);
    for (int i = 0; i < 3; i++) {
      targetList.add(sc.nextInt());
    }
  }

  private static void bubbleSort(List<Integer> targetList) {
    for (int i = 0; i < 3; i++) {
      for (int j = i+1; j < 3; j++) {
        if (targetList.get(i) > targetList.get(j)) {
          swap(targetList, i, j);
        }
      }
    }
  }

  private static void swap(List<Integer> targetList, int x, int y) {
    int temp = targetList.get(x);
    targetList.set(x, targetList.get(y));
    targetList.set(y, temp);
  }

  private static void printResult(List<Integer> targetList) {
    int sizeOfList = targetList.size();
    for (int i = 0; i < sizeOfList; i++) {
      System.out.print(targetList.get(i));
      if (i != sizeOfList-1) {
        System.out.print(" ");
      }
    }
    System.out.println();
  }
}

Measured memory_bytes: 26108
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
#define ld long double
#define pb push_back
#define mk make_pair
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
using namespace std;

int main(){
    ld a, b, c, d;
    cin >> a >> b >> c >> d;
    ll ak, t;
    ak = ceil(c/b);
    t = ceil(a/d);
    if(ak > t){
        cout << "No";
    }
    else if(ak <= t)
        cout << "Yes";
}


Measured memory_bytes: 3712
#include<stdio.h>

int linearSSearch(int A[],int n,int key){
int i;

for( i = 0; i < n; i++){
	if (A[i] == key)
	return 1;
}
return 0;
}





int main(){

  int i,n,d,f,total=0;
  scanf("%d",&n);
  int A[10000+50];
  int B[1000];
  for (i=0;i<n;i++){
  
  scanf("%d",&A[i]);
  }
  scanf("%d",&d);
  for(i=0;i<d;i++){
  scanf("%d",&B[i]);
  }
  for(i=0;i<d;i++){
  
  if (linearSSearch(A,n,B[i])) total++;
 }
  printf("%d\n",total);
  
 return 0;
}





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

vector<vector<vector<int>>>dp(55,vector<vector<int>>(55,vector<int>(55*55,0)));
// dp[i][j][k] i番目以内でj個使ってkを作る

signed main(void){
    int n,a; cin >> n >>a;
    vector<int>x(n+1,0);
    for(int i=1;i<=n;i++) cin >> x[i];
    dp[1][1][x[1]]++;
    for(int i=2;i<=n;i++){
        dp[i][1][x[i]]++;
        for(int j=1;j<=i;j++){
            for(int k=0;k<=50*50;k++){
                dp[i][j][k] += dp[i-1][j][k];
                if(k+x[i] < dp[i][j].size()) dp[i][j][k+x[i]] += dp[i-1][j-1][k];
            }
        }
    }
    
    // for(int i=0;i<10;i++){
    //     for(int j=0;j<10;j++){
    //         for(int k=0;k<30;k++){
    //             cout << dp[i][j][k] << ' ';
    //         }cout << endl;
    //     }cout << endl;
    // }cout << endl;
    
    
    int ans = 0;
    for(int i=1;i<=n;i++){
        
        ans += dp[n][i][a*i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 73216
n = gets.to_i
w = gets.split(' ').map(&:to_i)
sums = []
sum = 0
n.times do |a|
    sum = sum + w[a]
    sums << sum
end
results = []
result = 0
n.downto(2) do |b|
    restsum = sums[-1]-sums[b-2]
    result = (sums[b-2] - restsum).abs
    results << result
end
puts results.min


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

int main() {
    int N;  cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; ++i) cin >> d[i];
    sort(d.begin(), d.end());
    cout << d[N / 2] - d[N / 2 - 1] << endl;
}


Measured memory_bytes: 640
def main():
    from bisect import bisect_right

    N = int(input())
    *e, = map(int, input().split())

    e.sort()

    ans = 0
    for j in range(2, N):
        for i in range(1, j):
            d = e[j] - e[i]
            ans += i - bisect_right(e, d, lo=0, hi=i)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
const double PI=3.14159265358979323846;
const long long INF = 1LL << 60;

int main() {
	string N;
	cin >> N;
	int a=0, b=0, c=0, x, y, z;
	char t = N.at(N.size()-1);
	if (t == '3') {
		std::cout << "bon" << '\n';
	} else if (t == '0' || t == '1' || t == '6' || t == '8') {
		std::cout << "pon" << '\n';
	} else {
		std::cout << "hon" << '\n';
	}
}


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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, n, m) for (int i = n; i < m; i++)
#define ll long long int

using namespace std;

int main()
{
  int n,q;
  int c[100005] = {};
  int ans[100005];
  cin >> n >> q;
  string s;
  cin >> s;

  FOR(i, 2, n + 1) {
    if(s[i-2] == 'A' && s[i-1] == 'C') {
      c[i] = c[i-1] + 1;
    } else {
      c[i] = c[i-1];
    }
  }


  REP(i,q) {
    int l,r;
    cin >> l >> r;
    ans[i] = c[r] - c[l];
  }

  REP(i,q) {
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 1792
/**
 *
 * ......................我佛慈悲......................
 *                       _oo0oo_
 *                      o8888888o
 *                      88" . "88
 *                      (| -_- |)
 *                      0\  =  /0
 *                    ___/`---'\___
 *                  .' \\|     |// '.
 *                 / \\|||  :  |||// \
 *                / _||||| -卍-|||||- \
 *               |   | \\\  -  /// |   |
 *               | \_|  ''\---/''  |_/ |
 *               \  .-\__  '-'  ___/-. /
 *             ___'. .'  /--.--\  `. .'___
 *          ."" '<  `.___\_<|>_/___.' >' "".
 *         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
 *         \  \ `_.   \_ __\ /__ _/   .-` /  /
 *     =====`-.____`.___ \_____/___.-`___.-'=====
 *                       `=---='
 *
 *..................佛祖开光 ,永无BUG...................
 *
 */
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int h,w;
char a[51][51];
int main() {
	cin>>h>>w;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++)
			cin>>a[i][j];
	}
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			if(a[i][j]=='.') {
				int ans=0;
				if(a[i-1][j-1]=='#')
					ans++;
				if(a[i-1][j]=='#')
					ans++;
				if(a[i-1][j+1]=='#')
					ans++;
				if(a[i][j+1]=='#')
					ans++;
				if(a[i+1][j+1]=='#')
					ans++;
				if(a[i+1][j]=='#')
					ans++;
				if(a[i+1][j-1]=='#')
					ans++;
				if(a[i][j-1]=='#')
					ans++;
				cout<<ans;
			}
			else
				cout<<"#";
		}
		cout<<'\n';
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
constexpr i64 MOD = 1e9 + 7;

template<int n>
struct mat {
    vvi d;

    mat() {
        d = vvi(n, vi(n));
    }

    mat(initializer_list<initializer_list<i64>> m) {
        for (auto a: m) {
            vi row(a.begin(), a.end());
            d.emplace_back(row);
        }
        assert(n == d.size());
        assert(n == d.front().size());
    };

    mat operator+(const mat rhs) {
        mat ret;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ret.d[i][j] = d[i][j] + rhs.d[i][j];
            }
        }
        return ret;
    }

    mat operator-(const mat rhs) {
        mat ret;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ret.d[i][j] = d[i][j] - rhs.d[i][j];
            }
        }
        return ret;
    }

    mat operator*(const mat rhs) {
        mat ret;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    ret.d[i][j] += d[i][k] * rhs.d[k][j];
                }
            }
        }
        return ret;
    }

    mat operator*(const i64 k) {
        mat ret;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ret.d[i][j] = d[i][j] * k;
            }
        }
        return ret;
    }

    static mat eye() {
        mat ret;
        for (int i = 0; i < n; i++) {
            ret.d[i][i] = 1;
        }
        return ret;
    }
};

template<int k>
mat<k> pow(mat<k> a, i64 n) {
    if (n == 0) {
        return mat<k>::eye();
    }
    if (n % 2 == 0) {
        mat<k> t = pow(a, n / 2);
        return t * t;
    }
    return a * pow(a, n - 1);
}

i64 fib(i64 n) {
    if (n <= 1) return n;
    mat<2> f{{1, 1}, {1, 0}};
    mat<2> res = pow(f, n - 2);
    return res.d[0][0] + res.d[0][1];
}

int main() {
    int n;
    cin >> n;
    cout << fib(n + 1) << endl;
}


Measured memory_bytes: 3160
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func min(a ...int) int {
	m := a[0]
	for i, v := range a {
		if i == 0 {
			continue
		}
		if m > v {
			m = v
		}
	}
	return m
}

func max(a ...int) int {
	m := a[0]
	for i, v := range a {
		if i == 0 {
			continue
		}
		if m < v {
			m = v
		}
	}
	return m
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var sc = bufio.NewScanner(os.Stdin)

func main() {
	// Code for C - /\/\/\/
	var n int
	fmt.Scan(&n)

	sc.Split(bufio.ScanWords)
	v := make([]int, n)
	temp1 := make(map[int]int, n)
	temp2 := make(map[int]int, n)

	var count1, count2 int
	for i := 0; i < n; i++ {
		v[i] = nextInt()
		if i%2 == 0 {
			temp1[v[i]]++
			count1++
		} else {
			temp2[v[i]]++
			count2++
		}
	}

	sortTemp1 := make([]int, 0)
	for _, v := range temp1 {
		sortTemp1 = append(sortTemp1, v)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(sortTemp1)))

	sortTemp2 := make([]int, 0)
	for _, v := range temp2 {
		sortTemp2 = append(sortTemp2, v)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(sortTemp2)))

	var maxNum1 int
	for i, v := range temp1 {
		if v == sortTemp1[0] {
			maxNum1 = i
		}
	}

	var maxNum2 int
	for i, v := range temp2 {
		if v == sortTemp2[0] {
			maxNum2 = i
		}
	}

	var ans int
	if maxNum1 != maxNum2 {
		fmt.Println(count1 - temp1[maxNum1] + count2 - temp2[maxNum2])
	} else {
		if len(temp1) == 1 && len(temp2) == 1 {
			ans = min(count1+count2-temp2[maxNum2], count1-temp1[maxNum1]+count2)
			fmt.Println(ans)
		} else if len(temp1) == 1 && len(temp2) != 1 {
			for i, v := range temp2 {
				if v == sortTemp2[1] {
					maxNum2 = i
				}
			}
			fmt.Println(count1 - temp1[maxNum1] + count2 - temp2[maxNum2])
		} else if len(temp1) != 1 && len(temp2) == 1 {
			for i, v := range temp1 {
				if v == sortTemp1[1] {
					maxNum1 = i
				}
			}
			fmt.Println(count1 - temp1[maxNum1] + count2 - temp2[maxNum2])
		} else {
			var maxNum1New, maxNum2New int
			for i, v := range temp1 {
				if v == sortTemp1[1] {
					maxNum1New = i
				}
			}
			for i, v := range temp2 {
				if v == sortTemp2[1] {
					maxNum2New = i
				}
			}
			ans = min(count1-temp1[maxNum1]+count2-temp2[maxNum2New], count1-temp1[maxNum1New]+count2-temp2[maxNum2])
			fmt.Println(ans)
		}
	}
}


Measured memory_bytes: 11060