akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long

class Mod{
public:
    vector<int>fac;
    vector<int>finv;
    vector<int>inv;
    int MOD;

    Mod(int MAX=1e6,int mod=1e9+7){
        MOD = mod;
        fac.resize(MAX+2);
        finv.resize(MAX+2);
        inv.resize(MAX+2);
        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;
        }
    }

    int 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;
    }

    int add(int a, int b){
        return (a + b)%MOD;
    }
    
    int mul(int a,int b){
        return (a*b)%MOD;
    }
    
    int modinv(int a) {
        int b = MOD, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        return u;
    }
    
    int div(int a, int b){
        return (a*modinv(b)%MOD);
    }
};
Mod m;

signed main(void){
    int x,y; cin >> x >> y;
    // int one=-1,two=-1;
    // i:x軸上での１移動の数
    for(int i=0;i<=x;i++){
        if((x-i)%2==0){
            int one = i,two=(x-i)/2;
            if(one*2+two==y){
                // cout << one << ' ' << two << endl;
                cout << m.com(one+two,one) << endl;
                return 0;
            }
        }else{
            continue;
        }
    }
    cout << 0 << endl;
    // cout << one << ' ' << two << endl;
    return 0;
}

Measured memory_bytes: 23680
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;
//�I�[�o�[�t���[�ɋC������您����������
//�m�F�Y���Ȃ您����������

int main() {
    string odd,even; cin >> odd >> even;
    rep(i,even.size()){
        cout << odd[i] << even[i];
    }
    if(odd.size()!=even.size()) cout << odd[odd.size()-1];
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int arr[100005];
int main(){
   string s;
   cin>>s;
   int n=s.length();
    for(int i=0;i<n;i++){
    
        if(s[i]=='R' && s[i+1]=='L'){
            int j=i;
            while(j>=0 && s[j]=='R'){
                if((i-j)%2 == 0){
                    arr[i]++;
                }
                else arr[i+1]++;
                j--;
            }
            j=i+1;
            while(j<=n&&s[j] == 'L'){
                if((j-i)%2 == 1){
                    arr[i+1] ++;
                }
                else arr[i]++;
                j++;
            } 
        }

    }
    for(int i=0;i<n;i++){
        cout<<arr[i]<<' ';
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 4076
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

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

        String s = scanner.next();
        String t = scanner.next();

        List<Character> sortedS = s.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList());
        List<Character> sortedT = t.chars().mapToObj(c -> (char) c).sorted().collect(Collectors.toList());

        boolean shorter = sortedS.size() < sortedT.size();

        String result = "";

        for (int index = 0; index < sortedS.size(); index++) {
            Character cs = sortedS.get(index);
            Character largestInT = sortedT.get(sortedT.size()-1);
            if (cs == largestInT) { continue; }
            if (cs < largestInT) { result = "Yes"; break; }
            if (cs > largestInT) { result = "No"; break; }
        }

        if (result.isEmpty()) {
            if (!shorter) result = "No";
            else result = "Yes";
        }

        System.out.print(result);
    }
}

Measured memory_bytes: 28616
fun main() {
    val (n,t)= readLine()!!.split(" ").map { it.toInt() }
    val ct= Array(n){ readLine()!!.split(" ").map { it.toInt() }}
    var ans:Int?=null
    for ((cos,time) in ct){
        if (time>t){continue}
        if (ans==null){ans=cos}
        else{ans=Math.min(ans, cos)}
    }
    if (ans==null){
        println("TLE")
    }else{
        println(ans)
    }
}

Measured memory_bytes: 37968
//Bismillahir Rahmanir Rahim
//In the name of Allah the Most Merciful
//Astagfirullahil laji Rabbi Minkulli Jamio
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
int i,j,k;
main()
{

 int n;cin>>n;
 int a[n]={0};
 int b[n]={0};int j=0;
 for(i=0;i<n;i++)
    cin>>a[i];
    int c[n]={0};k=0;
    map<int,int> m;
    for(i=0;i<n;i++)
    {
        m[a[i]]++;
        if(m[a[i]]==2)
        {
            b[j++]=a[i];
        }
        if(m[a[i]]==4)
        {
            c[k++]=a[i];
        }
    }
//for(i=0;i<j;i++) cout<<b[i]<<' ';
//for(i=0;i<k;i++) cout<<c[i]<<' ';
   sort(b,b+j);
   sort(c,c+k);
   if(k==0&&j==0) cout<<0<<endl;
   else
   if(k==0) cout<<b[j-1]*b[j-2]<<endl;
   else if(j<=1) cout<<c[k-1]*c[k-1]<<endl;
   else cout<<max(c[k-1]*c[k-1],b[j-1]*b[j-2]);
}


Measured memory_bytes: 12048
m,n = map(int,input().split())

a = list(map(int,input().split()))

a.sort()

su = 0

b = [[0,0] for i in range(n-1)]
for i in range(n-1):
	b[i][0] = a[i+1]-a[i]
	b[i][1] = i
	su += a[i+1]-a[i]
b.sort(key = lambda x:x[0])
b.reverse()

if m >= n:
	print(0)
else:
	for i in range(m-1):
		su -= b[i][0]
	print(su)


Measured memory_bytes: 65320
/*
  The Island Was Silent before.
  .....
  And One day again it became Silent.
*/

#include<bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ll  long long
#define modd(a,b) ((a+2*b)%b)
#define debug(a) cout << #a << ": " << (a) << "\n"
#define ioso ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rtt cerr << "Time: " << clock()*1.0 / CLOCKS_PER_SEC << endl;
#define ffe freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);
ll ss[1000100]; 
int main() {
  ioso
  #ifndef ONLINE_JUDGE
 //ffe
  #endif
  memset(ss,0,sizeof(ss));
  ll n; cin >> n;
  ll a[200010];
  
  for(ll i=0;i<n;i++) {
    cin >> a[i];
    
    ss[a[i]]++;
    
  }
  ll cnt=0;
  for(ll i=0;i<n;i++) {
    ll f= 1;
    for(ll j=1;j*j<=a[i];j++) {
      if(a[i]%j==0) {
      ll an = a[i]/j;

      if(ss[j]>1) {
        f=0;break;
      }
      else if(ss[an]>1) {
        f=0;break;
      }
      else if(ss[j]==1) {
        if(a[i]!=j) {
          f=0; break;
        }
      }
      else if(ss[an]==1) {
        if(a[i]!=an) {
          f=0; break;
        }
      }
      
    }
    }

    if(f==1) {cnt++; //cout << a[i] << endl;
    }
  }

  cout << cnt << endl;
 
}

Measured memory_bytes: 13028
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<unordered_set>
#include<complex>
#include <cassert>

using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //ios::sync_with_stdio(false); cin.tie(0);
    int x;
    cin >> x;
    
    int ans = lcm(360, x) / x;
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
const constexpr int MAX = 100;
constexpr ll INF = 1LL<<32;
int n;
vv(ll, d, MAX, MAX, INF);
inline void floyd() {
	rep(k, 0, n) {
		rep(i, 0, n) {
			if(d[i][k] == INF) continue;
			rep(j, 0, n) {
				if(d[k][j] == INF) continue;
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}
int main() {
	int e; cin >> n >> e;
	rep(i, 0, n) d[i][i] = 0L;
	int u, v, c;
	rep(i, 0, e) {
		cin >> u >> v >> c;
		d[u][v] = c;
	}
	floyd();
	bool negative = false;
	rep(i, 0, n) if(d[i][i] < 0) { negative = true; break; }
	if(negative) P("NEGATIVE CYCLE");
	else {
		rep(i, 0, n) {
			rep(j, 0, n) {
				if(j) p(" ");
				if(d[i][j] == INF) p("INF");
				else p(d[i][j]);
			}
			cout << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 3304
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

const int MAXN = 15;
vector<vector<int>> speak(MAXN, vector<int>(MAXN,-1)); // iがxをspeakだと言っている
int res = 0;

void dfs(vector<int> &fact, int &n, int honest){
  
	if(fact.size() == n){
     // cout << fact[0] << fact[1] << fact[2] << endl;
		rep(i,n){
			if(fact[i] == 0) continue; // iの言うことはどうでもいい
			rep(j,n){
				if(speak[i][j] != -1 && speak[i][j] != fact[j]) return; // 矛盾
			}
		}
     // cout << "ok--"<< fact[0] << fact[1] << fact[2] << endl;
		res = max(res,honest);
	}
	else{
		fact.push_back(0);
		dfs(fact, n, honest);
		fact.pop_back();
		fact.push_back(1);
		dfs(fact, n, honest+1);
      fact.pop_back();
	}
	return;
}

int main(){
	
	int n;
	cin >> n;
	
	
	rep(i,n){
		int a;
		cin >> a;
		rep(j,a){
			int x,y;
			cin >> x >> y;
			speak[i][--x] = y;
		}
	}
	
	vector<int> fact; // iはfactである
	dfs(fact, n, 0);
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    N, M, C = map(int, input().split())
    B = [int(number) for number in input().split()]
    A = []
    A = [[int(m) for m in input().split()] for n in range(N)]

    num_of_clear = 0
    for list_a in A:
        sum_num = 0
        for index, a in enumerate(list_a):
            sum_num += a * B[index]
        sum_num += C
        if sum_num > 0:
            num_of_clear += 1

    print(num_of_clear)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  long dp[n+1];
  memset(dp,1000000007,sizeof(dp));
  dp[0]=0;
  for(int i=1;i<n;i++){
    for(int j=1;j<=k;j++){
      if(i-j<0)
        break;
      dp[i]=min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
    }
  }
  // for(int i=0;i<n;i++)
  //   cout<<dp[i]<<" ";
  cout<<dp[n-1]<<endl;
}   

Measured memory_bytes: 4796
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
int H=Integer.parseInt(sc.next());
int W=Integer.parseInt(sc.next());
if(H==0&&W==0){break;}
for(int i=0;i<H;i++){
    for(int t=0;t<W;t++){
        if(i==0||i==H-1){
            System.out.print("#");}else{
            if(t==0||t==W-1){System.out.print("#");
            }else{System.out.print(".");}
    }
    }System.out.println("");
}System.out.println("");
    

}
}
}


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


int main() {

    int a,b;

    cin >> a >> b;
    
    int numa1 = (a * 25) / 2;
    if ((a % 2)!=0) numa1+=1;

    int numb1 = b * 10;

    int numa2 = ((a+1) * 25) / 2;
    if ((a+1)%2==0) numa2 -= 1;

    int numb2 = (b+1) * 10 -1;

    if ((numa1 > numb2) || (numb1 > numa2)){
        cout << "-1" << endl;
    } else {
        cout << max(numa1,numb1) << endl;
    }
    

}

Measured memory_bytes: 256
//From Naruto to Hokage
//#include <RJ>
#include<bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=100005;
void solve(){
    ll n,a,b;
    cin>>n;
    vector <pii> v;
    rep(i,0,n-1){
        cin>>a>>b;
        v.pb({b,a});
    }
    sort(all(v),greater<pii>());
    ll curr=v[0].F;
    rep(i,0,n-1){
        curr=min(curr,v[i].F);
        curr-=v[i].S;
        if(curr<0) {
            cout<<"No";
            return;
        }
    }
    cout<<"Yes";
}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

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

int check(string s)
{
    int counter=0;

    for(int i=1; i<s.size(); i++)
    {
        if(s[i]==s[i-1])
        {
            counter++;
            i++;
        }
    }
    return counter;
}

int main()
{
    string s;
    long long k;

    while(cin>>s>>k)
    {
        string temp=s;

        int first=check(s);

        s+=temp;
        int second=check(s)-first;

        s+=temp;
        int third=check(s)-(first+second);

        //cout<<first<<' '<<second<<' '<<third<<endl;

        long long res=0;

        if(k==1)
            res=first;
        else
        {
            res+=first;
            res+=second*(k/2);

            if(k%2==0)
                res+=third*((k/2)-1);
            else if(k%2!=0)
                res+=third*(k/2);
        }
        cout<<res<<endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long A,B,C,K;
  cin>>A>>B>>C>>K;
  if(A==B)
  {
    cout<<0<<endl;
  }else{
    if(A>B)
    {
      if(K%2==0)
      {
        cout<<A-B<<endl;
      }else{
        cout<<B-A<<endl;
      }
    }else{
      if(K%2==0)
      {
        cout<<A-B<<endl;
      }else{
        cout<<B-A<<endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
bingo = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for _ in range(N):
  b = int(input())
  for i in range(3):
    for j in range(3):
      if bingo[i][j] == b:
        bingo[i][j] = 0

ans = "No"
for k in range(3):
  if bingo[k][0] == bingo[k][1] == bingo[k][2] or \
     bingo[0][k] == bingo[1][k] == bingo[2][k]:
    ans = "Yes"
    break
if bingo[0][0] == bingo[1][1] == bingo[2][2] or \
   bingo[0][2] == bingo[1][1] == bingo[2][0]:
  ans = "Yes"
print(ans)

Measured memory_bytes: 9228
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  for(int i=0;i<n;i++) cin >> h[i];

  vector<int> dp(n);
  dp[0] = 0;
  dp[1] = abs(h[1]-h[0]);

  for(int i=2;i<n;i++){
    dp[i] = min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));
  }

  cout << dp[n-1] << endl;
}

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

namespace abc178_c
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = CIn.ReadLong();
            var x = ModPow(10, N) - ModPow(9, N) - ModPow(9, N) + ModPow(8, N) + (int)Math.Pow(10,9) + 7 + (int)Math.Pow(10, 9) + 7;    
            var ans = x % ((int)Math.Pow(10, 9) + 7);
            Console.WriteLine(ans);
        }
        static long ModPow(long a, long n)
        {
            var result = 1L;
            for (var i = 1; i <= n; i++)
            {
               result = result *  a % ((int)Math.Pow(10, 9) + 7);
            }
            return result;
        }
    }
    class CIn
    {
        private static readonly Queue<string> fieldBuffer = new Queue<string>();

        public static string Read()
        {
            if (fieldBuffer.Count == 0)
            {
                foreach (var field in Console.ReadLine().Split())
                {
                    fieldBuffer.Enqueue(field);
                }
            }

            return fieldBuffer.Dequeue();
        }

        public static int ReadInt() => int.Parse(Read());
        public static long ReadLong() => long.Parse(Read());
        public static double ReadDouble() => double.Parse(Read());

        public static string[] ReadStringArray(long n)
        {
            var array = new string[n];

            for (var i = 0; i < n; i++)
            {
                array[i] = Read();
            }

            return array;
        }

        public static int[] ReadIntArray(long n)
        {
            var array = new int[n];

            for (var i = 0; i < n; i++)
            {
                array[i] = ReadInt();
            }

            return array;
        }

        public static long[] ReadLongArray(long n)
        {
            var array = new long[n];

            for (var i = 0; i < n; i++)
            {
                array[i] = ReadLong();
            }

            return array;
        }
        public static double[] ReadDoubleArray(long n)
        {
            var array = new double[n];

            for (var i = 0; i < n; i++)
            {
                array[i] = ReadDouble();
            }

            return array;
        }
    }
    
}


Measured memory_bytes: 28196
s = input()
t = input()
dp = [[0 for _ in range(len(s)+1)] for _ in range(len(t) + 1)]

for i,c1 in enumerate(s,1):
    for j,c2 in enumerate(t,1):
        if c1 == c2:
            dp[j][i] = dp[j-1][i-1] + 1
        else:
            dp[j][i] = max(dp[j-1][i],dp[j][i-1])

i1,i2 = len(s),len(t)
#  print(" " + s)
#  for i,row in enumerate(dp):
    #  if i == 0:
        #  print(" ",row)
    #  else:
        #  print(t[i-1],row)

rev_ans = ""
while i1 != 0:
    lru = dp[i2-1][i1-1]
    now = dp[i2][i1]
    dup = now - dp[i2-1][i1]
    dleft = now - dp[i2][i1-1]
    dupleft = now - lru
    #  print(i1,i2,dupleft,dup,dleft)
    if dupleft == 1 and dleft == 1 and dup == 1:
        rev_ans += t[i2-1]
        i2 -= 1
        i1 -= 1
    elif dleft == 1:
        i2 -= 1
    else:
        i1 -= 1

for c in reversed(rev_ans):
    print(c,end='')


Measured memory_bytes: 119772
#include <bits/stdc++.h>
int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  auto cal = [&] (long long n, long long k, long long b) {
    assert(k < b);
    return
      n / b * (b - k) +
      std::max(0LL, n % b - k + 1);
  };
  long long n, k; std::cin >> n >> k;
  if (k == 0) {
    std::cout << n * n << std::endl;
    return 0;
  }
  long long ans = 0;
  for (int b = k + 1; b <= n; b++) {
    ans += cal(n, k, b);
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 256
//Created by Kira

#include <bits/stdc++.h>
using namespace std;

#define IOS                 \
    cin.sync_with_stdio(0); \
    cin.tie(0);             \
    cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);

const int N = 5e5+10;

int n;


struct S{

    vector<bool> cnt;
    
    S() {
        cnt.assign(26, false);
    }
    S(vector<bool> cnt) : cnt(cnt){}
};


 S combine(S a, S b){
        S res;

        for(int i = 0; i < 26; i++){
            res.cnt[i] = a.cnt[i] | b.cnt[i];
        }

        return res;
}

S t[2 * N];

void build()
{
    for (int i = n - 1; i >= 0; --i)
        t[i] = combine(t[i<<1], t[i<<1 | 1]);
}

void modify(int p, S val)
{ //Set Value at position p
    for (t[p += n] = val; p > 1; p >>= 1)
        t[p >> 1] = combine(t[p],t[p ^ 1]);
}

S query(int l, int r)
{ //query on interval [l,r)

    S resL, resR;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            resL  = combine(resL, t[l++]);
        if (r & 1)
            resR  = combine(resR, t[--r]);
    }
    return combine(resL, resR);
}

int main(){
    IOS
    
    cin>>n;

    string s; cin>>s;
    int q; cin>>q;

    for(int i = 0; i < 2*n; i++){
        t[i].cnt.assign(26,false);
    }


    for(int i = n; i < 2*n; i++){
        t[i].cnt[s[i-n]-'a'] = true;
    }

    build();

    for(int i = 0; i < q; ++i){
        int type; cin>>type;

        if(type == 1){
            int pos; char val;
            cin>>pos>>val; --pos;
            S nn; 
            nn.cnt.assign(26,false);
            nn.cnt[val-'a'] = true;
            modify(pos, nn);

        }else if (type == 2){
            int L, R; cin>>L>>R; L--;

            S res = query(L, R);
            
            int fres = 0; 
            for(int i = 0; i < 26; ++i){
                if(res.cnt[i])fres++;
            }

            cout<<fres<<"\n";
        }
    }

}

ll pwr(ll a, ll b)
{
    a %= mod; //Remove mod if not required
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}


Measured memory_bytes: 71444
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

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

    vector<int> A(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];

    for (int i = 0; i < N; i++) {
        if (A[i] % 2 != 0)
            continue;

        if ((A[i] % 3 != 0) && (A[i] % 5 != 0)) {
            cout << "DENIED" << endl;

            return 0;
        }
    }

    cout << "APPROVED" << endl;

    return 0;
}


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

ch = 0
buy = []
sell = []
for i in range(1,N):
    if ch == 0:
        if A[i-1] < A[i]:
            buy.append(A[i-1])
            ch = 1
    else:
        if A[i-1] > A[i]:
            sell.append(A[i-1])
            ch = 0
    if ch == 1 and i == N-1:
        sell.append(A[N-1])
    
ans = 1000
for i in range(len(sell)):
    kabu = ans // buy[i]
    ans %= buy[i]
    ans += kabu * sell[i]

print(ans)
    
    

Measured memory_bytes: 9208
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
 
/*Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
 
}
 
Node treeSearch(Node u, int k){
  /*while(u!=NIL && k!=u->key){
    if(k<u->key)u=u->left;
    else u=u->right;
  }
  return u;//

 
  if(u==NIL || k==u->key)return u;
  if(k<u->key)return treeSearch(u->left,k);
  else return treeSearch(u->right,k);
  
 
}
 
Node treeSuccessor(Node x){
  Node y;
  if(x->right!=NIL)return treeMinimum(x->right);
  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL || z->right==NIL)y=z;
  else y=treeSuccessor(z);
 
  if(y->left!=NIL)x=y->left;
  else x=y->right;
 
  if(x!=NIL)x->parent=y->parent;
 
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent->left=x;
  else y->parent->right=x;
 
  if(y!=z){
    z->key=y->key;
    z->left=y->left;
    z->right=y->right;
    z->parent=y->parent;
  }
  //return y;
}*/
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;
}
 
void inorder(Node u){
  if(u!=NIL){
    inorder(u->left);
	printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
	//printf("%d",u->key);
	//if(u->left==NIL && u->right==NIL){
		//printf(" ");
	//}
  if(u!=NIL){
	printf(" %d",u->key);
	if(u->left!=NIL)preorder(u->left);
	if(u->right!=NIL)preorder(u->right);
  }
  /*if(u->left!=NIL){
    preorder(u->left);
  }
  if(u->right!=NIL){
    preorder(u->right);
  }*/
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    /*if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else */if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } /*else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }*/
  }
 
  return 0;
}

Measured memory_bytes: 24040
N, X, Y = map(int, input().split())

res = [0 for _ in range(N)]

for i in range(1, N+1):
    for j in range(i, N+1):
        kyori = min(abs(i - j), abs(X-i) + 1 +
                    abs(Y-j), abs(Y-i) + 1 + abs(X-j))
        res[kyori] += 1

for i, ky in enumerate(res):
    if i == 0:
        continue
    print(ky)


Measured memory_bytes: 3444
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}


#line 2 "abc168_c.cpp"

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

  double a, b;
  int h, m;
  cin >> a >> b >> h >> m;

  double A_theta = ((60 * h + m) * M_PIl) / (2 * 180);
  double B_theta = (m * M_PIl) / 30;

  double ax = a * cos(A_theta), ay = a * sin(A_theta);
  double bx = b * cos(B_theta), by = b * sin(B_theta);

  coutd(14) << hypot(ax - bx, ay - by) << endl;
}


Measured memory_bytes: 4036
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    

    ll n;
    cin >> n;
    if(n < 10){
        cout << n << endl;
    }else if(n < 1000){
        cout << 9 + max((ll)0, n-(ll)99) << endl;
    }else if(n < 100000){
        cout << 909 + max((ll)0, n-9999) << endl;
    }else{
        cout << 90909 << endl;
    }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var x int
	fmt.Scan(&x)
	maxPow := 1
	for i := 2; i < x; i++ {
		j := 2
		for {
			pow := int(math.Pow(float64(i), float64(j)))
			if pow > x || j >= x {
				break
			} else if pow > maxPow {
				maxPow = pow
			}
			j++
		}
	}
	fmt.Println(maxPow)
}


Measured memory_bytes: 512
#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=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
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; }

int main(){
    int x,y; cin >> x >> y;
    rep(i,x+1){
        if(i*2 + (x-i)*4 == y) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

constexpr int MAX = 500010;

struct Node{
  int key;
  Node* left;
  Node* right;
  Node* p;
};

Node gT[MAX];
Node* gRoot = nullptr;

void Insert( int k ){
  Node* y = nullptr;
  Node* x = gRoot;
  Node* z = new Node;
  z->key = k; z->left = nullptr; z->right = nullptr;
  
  while( x != nullptr ){
    y = x;
    if( z->key < x->key ) x = x->left;
    else                  x = x->right;
  }
  z->p = y;

  if( y == nullptr ){
    gRoot = z;
  }else if( z->key < y->key ){
    y->left = z;
  }else{
    y->right = z;
  }
}


void Inorder( Node* s ){
  if( s == nullptr ) return;

  Inorder( s->left );
  cout << " " << s->key;
  Inorder( s->right );
}

void Preorder( Node* s ){
  if( s == nullptr ) return;

  cout << " " << s->key;
  Preorder( s->left );
  Preorder( s->right );
}

int main(){
  for( int i = 0; i < MAX; i++ ){
    gT[i].left = gT[i].right = gT[i].p = nullptr;
  }
  
  int m; cin >> m;
  for( int i = 0; i < m; i++ ){
    char cmd[10]; cin >> cmd;
    if( cmd[0] == 'i' ){
      int key; cin >> key;
      Insert( key );
    }else if( cmd[0] == 'p' ){
      Inorder( gRoot ); cout << endl;
      Preorder( gRoot ); cout << endl;
    }
  }
}



Measured memory_bytes: 42088
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = [[0] * W for _ in range(H)]

# Find strawberrys
B = []
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            B.append((i, j))

# Cut the cake
for i, b in enumerate(B):
    U, L, D, R = b[0], b[1], b[0], b[1]
    ans[b[0]][b[1]] = i + 1
    while True:
        if W > L - 1 >= 0 and S[U][L - 1] == '.' and ans[U][L - 1] == 0:
            ans[U][L - 1] = i + 1
            L -= 1
        else:
            break
    while True:
        if W > R + 1 >= 0 and S[D][R + 1] == '.' and ans[D][R + 1] == 0:
            ans[D][R + 1] = i + 1
            R += 1
        else:
            break
    while True:
        if H > U - 1 >= 0 and not ('#' in S[U - 1][L:R + 1]) and sum(ans[U - 1][L:R + 1]) == 0:
            for j in range(L, R + 1):
                ans[U - 1][j] = i + 1
            U -= 1
        else:
            break
    while True:
        if H > D + 1 >= 0 and not ('#' in S[D + 1][L:R + 1]) and sum(ans[D + 1][L:R + 1]) == 0:
            for j in range(L, R + 1):
                ans[D + 1][j] = i + 1
            D += 1
        else:
            break
for i in range(H):
    print(' '.join(map(str, ans[i])))


Measured memory_bytes: 14144
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long lint;

string read_string() {
  char *str;
  scanf("%ms", &str);
  string result(str);
  free(str);
  return result;
}

int main() {
  int n;
  scanf("%d", &n);
  string s = read_string();

  vector<int> m_count(n + 1);
  for (int i = 0; i < n; ++i)
    m_count[i + 1] = m_count[i] + (s[i] == 'M');
  vector<int> d_count(n + 1);
  for (int i = 0; i < n; ++i)
    d_count[i + 1] = d_count[i] + (s[i] == 'D');
  vector<lint> per_d_m_count(n + 1);
  for (int i = 0; i < n; ++i) {
    per_d_m_count[i + 1] = per_d_m_count[i];
    if (s[i] == 'D') {
      per_d_m_count[i + 1] += m_count[n] - m_count[i];
    }
  }

  int nq;
  scanf("%d", &nq);
  for (int q = 0; q < nq; ++q) {
    int k;
    scanf("%d", &k);
    lint result = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] != 'C') continue;

      lint res = (per_d_m_count[i] - per_d_m_count[max(i - k + 1, 0)]) -
                 (lint)(d_count[i] - d_count[max(i - k + 1, 0)]) *
                     (m_count[n] - m_count[i]);
      result += res;
    }
    printf("%lld\n", result);
  }

  return 0;
}


Measured memory_bytes: 16940
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
const int mod = 1e9+7;


int main()
{
    ll H, W, K; cin >> H >> W >> K;
    vvll dp(H + 1, vll (W, 0)); dp[0][0] = 1;
    rep(i, H) {
        rep(j, W) {
            rep(k, 1<<(W - 1)) {
                bool ok = true;
                rep(l, W - 2) {
                    if (((k >> l) & 1) && ((k >> (l + 1)) & 1)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    if (j >= 1 && ((k >> (j - 1)) & 1)) {
                        dp[i + 1][j - 1] += dp[i][j];
                        dp[i + 1][j - 1] %= mod;
                    } else if (j <= W - 2 && ((k >> j) & 1)) {
                        dp[i + 1][j + 1] += dp[i][j];
                        dp[i + 1][j + 1] %= mod;
                    } else {
                        dp[i + 1][j] += dp[i][j];
                        dp[i + 1][j] %= mod;
                    }
                }
            }
        }
    }
    cout << dp[H][K - 1] << endl;
    
    return 0;
}

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

int Kaijo(int n){
  if(n==0)return 1;
  else{
    return n*Kaijo(n-1);
  }
}


int main(){
  int N,ans;
  cin>>N;
  vector<int>P(N);
  vector<int>Q(N);
  vector<int>L(N);
  int p,q;
  p=1;q=1;
  for(int i=0;i<N;i++){
    cin>>P.at(i);
  }
  for(int i=0;i<N-1;i++){
    int d=0;
    for(int j=i+1;j<N;j++){
      if(P.at(i)>P.at(j))d++;
    }
    //cout<<N-i-1<<" "<<d<<endl;
    p+=Kaijo(N-i-1)*d;
  }
  q = p;

  p=1;
  for(int i=0;i<N;i++){
    cin>>P.at(i);
  }
  for(int i=0;i<N-1;i++){
    int d=0;
    for(int j=i+1;j<N;j++){
      if(P.at(i)>P.at(j))d++;
    }
    //cout<<N-i-1<<" "<<d<<endl;
    p+=Kaijo(N-i-1)*d;
  }




  ans = abs(p-q);
  cout<<ans;

}


Measured memory_bytes: 256
import math
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            tempgcd=math.gcd(a,b)
            if a==b or b==c or a==c:
              if a==b and b==c:
                ans=ans+math.gcd(tempgcd,c)
              else:
                ans=ans+3*math.gcd(tempgcd,c)
            else:
              ans=ans+6*math.gcd(tempgcd,c)
            
print(ans)


Measured memory_bytes: 9200
K,N=map(int,input().split())
L=list(map(int,input().split()))
S=0
for i in range(N):
	if i==N-1:
		S=max(S,(K+L[0])-L[i])
	else:
		S=max(S,L[i+1]-L[i])
print(K-S)

Measured memory_bytes: 26436
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef complex<double> base;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

const ll MOD = 1e9+7;

int N;
int A[22][22];
int pc[1<<21];
ll dp[22][1<<21];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    repp(i, 1, N+1) rep(j, N) cin >> A[i][j];
    rep(i, 1<<N) pc[i] = __builtin_popcount(i);

    dp[0][0] = 1;
    rep(i, N) {
        rep(j, 1<<N) if (pc[j] == i and dp[i][j] > 0) {
            rep(k, N) if (((j>>k)&1) == 0 and A[i+1][k]) dp[i+1][j|(1<<k)] = (dp[i+1][j|(1<<k)]+dp[i][j])%MOD;
        }
    }

    cout << dp[N][(1<<N)-1] << endl;
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    int n;
    cin >> n;
    vector<ll> x(n);
    int b = 0;
    ll ma=0, mi=1e12, zep=1e12, zem=1e12;
    map<int, int> mp;
    rep(i, n) {
        cin >> x[i];
        x[i] -= (i+1);
        ma = max(ma, x[i]);
        mi = min(mi, x[i]);
        if (abs(zep) > abs(x[i]) and x[i] > 0) {
            zep = x[i];
        }
        if (abs(zem) > abs(x[i]) and x[i] < 0) {
            zem = x[i];
        }
        mp[x[i]]++;
    }

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

    ll ans1=0, ans2=0, ans3=0, ans4=0, ans5=0, ans6=0;
    rep(i, n) {
        ans1 += abs(x[i]-ma);
        ans2 += abs(x[i]-mi);
        ans3 += abs(x[i]-zep);
        ans4 += abs(x[i]-zem);
        ans5 += abs(x[i]-x[n/2]);
        ans6 += abs(x[i]-x[n/2+1]);
    }
    cout << min({ans1, ans2, ans3, ans4, ans5, ans6}) << endl;
}


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

using namespace std;
vector<long long> factors;
#define ll long long

#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000'000'007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x0f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }

//****************************don't use int!!!!!!!****************************//
//***************************code starts here!!!!!****************************//

int main()
{

	ll R, G, B, N;
	cin >> R >> G >> B >> N;

	ll res = 0;
	for (auto i = 0; i <= N / R; i++)
	{
		ll n2 = N - R * i;
		for (auto j = 0; j <= n2 / G; j++)
		{
			ll n3 = n2 - G * j;
			if (n3 % B == 0)
				res += 1;
		}
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
class UnionFind{
private:
    vector<int> p,s;
	int cnt;
public:
	UnionFind(){}
	UnionFind(int N){
		cnt = N;
		p = s = vector<int>(N+1,0);
		for(int i=1;i<=N;i++){
			p[i] = i; s[i] = 1;
		}
	}
	int find(int x){
		if(p[x]==x) return x;
		else return p[x] = find(p[x]);
	}
	void unite(int x,int y){
		x = find(x); y = find(y);
		if(x==y) return;
		if(s[x]>s[y]){
			p[y] = x;
			s[x] += s[y];
		}else{
			p[x] = y;
			s[y] += s[x];
		}
		cnt--;
	}
	bool is_same_set(int x,int y) {return find(x)==find(y);}
	ll size(int x) {return s[find(x)];}
	int compnents_number(){return cnt;}
};
   
int main(){
    ll N,M,Q;
    cin >> N >> M >> Q;
    vector<pair<int,int>> v[2];
    for(int i=0;i<Q;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a++; b++;
        v[c].push_back({a,b});
    }
    if(M==N-1){
        cout << (v[1].empty()? "Yes":"No") << endl;
        return 0;
    }
    UnionFind uf(N);
    for(auto x:v[0]){
        uf.unite(x.first,x.second);
    }
    bool ok = true;
    for(auto x:v[1]){
        if(uf.is_same_set(x.first,x.second)) ok = false;
    }
    ll si = uf.compnents_number();
    ll upp = N+si*(si-3)/2;
    ok &= (M<=upp);
    cout << (ok? "Yes":"No") << endl;
}

Measured memory_bytes: 2036
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
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; }


using namespace std;

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

#define t_max 100000+5

int v[30][t_max] = {};

int main(){
    int i, j;
    int n, c;
    cin >> n >> c;
    rep(i, n) {
        int a, b, c;
        cin >> a >> b >> c;
        c--;
        v[c][a]++;
        v[c][b]--;
    }
    rep(i, c) rep(j, t_max-1) v[i][j+1] += v[i][j];
    rep(i, c) rep(j, t_max-1) {
        if (v[i][j] == 0 && v[i][j + 1] == 1) v[i][j]++;
    }
    int ans = 0;
    rep(j, t_max) {
        int cnt = 0;
        rep(i, c) if (v[i][j]) cnt++;
        ans = max(ans, cnt);
    }

    cout << ans << endl;

}

Measured memory_bytes: 11904
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
S = str(input())

count = 0
for i in range(len(S)-2):
    if S[i:i+3]=='ABC':
        count += 1

print(count)

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

using ll = long long int;

int main() {
    ll a, b, c, d, cd;
    cin >> a >> b >> c >> d;

    cd = c * d / __gcd(c, d);

    ll ic = a + (c - (a % c));
    if (a % c == 0)
        ic -= c;
    ll fc = b - (b % c);
    ll diff_c = fc - ic;

    ll tc = diff_c - diff_c / c;
    if (a % c != 0)
        tc += c - (a % c);
    tc += b % c;

    ll id = a + (d - (a % d));
    if (a % d == 0)
        id -= d;
    ll fd = b - (b % d);
    ll diff_d = fd - id;

    ll td = diff_d - diff_d / d;
    if (a % d != 0)
        td += d - (a % d);
    td += b % d;

    ll icd = a + (cd - (a % cd));
    if (a % cd == 0)
        icd -= cd;
    ll fcd = b - (b % cd);
    ll diff_cd = fcd - icd;

    ll tcd = diff_cd - diff_cd / cd;
    if (a % cd != 0)
        tcd += cd - (a % cd);
    tcd += b % cd;

    ll total = td + tc - tcd;
    cout << total << '\n';
}

Measured memory_bytes: 3632
N, K = map(int, input().split())
mod = 10**9+7
ans= 0
for k in range(K, N + 2):
    min_num = ((k-1) * k) / 2
    max_num = (N * (N+1)) / 2 - ((N-k) * (N-k+1)) / 2
    ans +=  max_num - min_num + 1
print(int(ans % mod))

Measured memory_bytes: 9196
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

vector<ll> solve(const vector<ll>& A) {
  int L = A.size();
  vec<ll, 2> dp = make_v(L + 1, 2, 0ll);
  vector<ll> res(L + 1, 0);
  ll sum = 0;
  for (int i = 0; i < L; i++) {
    ll cur = A[i];
    if (cur == 0) {
      dp[i + 1][0] = min(dp[i][0] + 2, sum);
      dp[i + 1][1] = min(min(dp[i][0], dp[i][1]) + 1, sum);
    } else {
      dp[i + 1][0] = dp[i][0] + (cur % 2 != 0);
      dp[i + 1][1] = min(dp[i][0], dp[i][1]) + (cur % 2 != 1);
    }
    res[i + 1] = min(dp[i + 1][0], dp[i + 1][1]);
    sum += cur;
  }
  return res;
}

int main() {
  int L;
  while (cin >> L) {
    vector<ll> A(L);
    for (int i = 0; i < L; i++) cin >> A[i];
    auto X = solve(A);
    reverse(A.begin(), A.end());
    auto Y = solve(A);
    reverse(Y.begin(), Y.end());
    ll res = 1ll << 60;
    for (int i = 0; i <= L; i++) res = min(res, X[i] + Y[i]);
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 15920
#include<stdio.h>
int main(void){
  int A,B,C,D;
  scanf("%d%d%d%d",&A,&B,&C,&D);
  int sq_1=A*B;
  int sq_2=C*D;
  if(sq_1>sq_2)
    printf("%d\n",sq_1);
  else
    printf("%d\n",sq_2);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <bitset>
#include <algorithm>

using namespace std;

int main() {
  int N, a{};
  bitset<8> b;
  cin >> N;
  while (cin >> N) {
    if (N < 3200) b.set(N/400);
    else ++a;
  }
  cout << max(1ul, b.count()) << " " << b.count() + a << endl;
}


Measured memory_bytes: 3620
n, m = map(int, input().split())
a = [list(input()) for i in range(n)]
b = [list(input()) for i in range(m)]
flag = False
for i in range(n - m + 1):
    for j in range(n - m + 1):
        #if cnt == m * 2   
        cnt = 0
        for k in range(m):
            for l in range(m):
                if a[i + k][j + l] == b[k][l]:
                    cnt += 1
                if cnt == m ** 2:
                    flag = True
if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064