akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#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 SIZE(x) ((int)(x).size())

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

int main() {
  string N;
  int sum = 0;
  cin >> N;
  REP(i, SIZE(N)) {
    sum += N[i] - '0';
  }
  if (sum % 9 == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

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

int main(){
    int m1,d1,m2,d2;;
    cin>>m1>>d1>>m2>>d2;
    if(m2==m1+1 && d2==1){
        cout<<"1"<< endl;
    }else{
        cout<<"0"<< endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
mod = 10**9 + 7


def solve(now, from_, K, ab):
    if from_ == -1:
        can_num = K - 1
    else:
        can_num = K - 2
    if K < len(ab[now]):
        return 0
    case_num = 1
    for i in ab[now]:
        if i != from_:
            case_num *= can_num
            can_num -= 1
            case_num %= mod
    for i in ab[now]:
        if i != from_:
            case_num *= solve(i, now, K, ab)
            case_num %= mod
    return case_num


def main():
    N, K = map(int, input().split())
    if N == 1:
        print(K)
        exit(0)
    ab = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        ab[a - 1].append(b - 1)
        ab[b - 1].append(a - 1)
    ans = K * solve(0, -1, K, ab)
    print(ans % mod)


if __name__ == "__main__":
    main()

Measured memory_bytes: 88480
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
    double x, w, h, n, r, min_r;
    while (cin >> x >> w >> h, x || w || h){
	min_r = min(sqrt(x*x+w*w), min(sqrt(x*x+h*h), sqrt(w*w+h*h)));
	cin >> n;
	while (n--){
	    cin >> r;
	    r*=2;
	    (min_r < r)? cout << "OK" : cout << "NA";
	    cout << endl;
	}
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n;
    cin >> n;
    
    vector<ll> vec(n);
    for(int i = 0; i < n; i++){
        ll x;
        cin >> x;
        vec[i] = x;
    }
    sort(vec.begin(), vec.end());
    
    
    
    ll r = vec[0];
    ll x = 1e18;
    for(int i = 1; i < n; i++){
        if(r > x/vec[i]){
            cout << -1;
            return 0;
        }
        r *= vec[i];
    }

    cout << r;
    return 0;
}









Measured memory_bytes: 3984
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <numeric>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
//#define int long long
#define all(vec) vec.begin(), vec.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl
#define isEven(t) t % 2 == 0

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


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

	string S;
	cin>>S;
	int mn = 90000;

	for (int i = 2; i < (int)S.size(); i++) {
		int tmp = (S[i-2] - '0') * 100 + (S[i-1] - '0') * 10 + (S[i] - '0');
		tmp = abs(tmp - 753);
		mn = min(mn, tmp);
	}

	cout << mn << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll N, K;
    cin >> N >> K;

    vector<ll> t(N), d(N);
    rep(i, N) cin >> t[i] >> d[i];

    typedef pair<ll, ll> P;
    vector<P> f(t.size());
    rep(i, t.size()) f[i] = P(d[i], t[i]);
    
    sort(all(f));
    reverse(all(f));

    vector<int> cnt(N + 1);
    rep(i, K) {
        // ネタをカウント
        cnt[f[i].second]++;
    }

    ll nNeta = 0;
    rep(i, cnt.size()) {
        if (cnt[i] >= 1) nNeta++;
    }

    ll base = nNeta * nNeta;
    rep(i, K) {
        base += f[i].first;
    }

    // ~Kで入れ替え可能
    vector<P> to;
    for (int i = K - 1; i >= 0; i--) {
        if (cnt[f[i].second] >= 2) {
            to.push_back(f[i]);
        }
    }

    vector<ll> Sto(to.size());
    if (to.size() >= 1) {
        Sto[0] = to[0].first;
    }
    repi(i, to.size()) {
        Sto[i] = Sto[i - 1] + to[i].first;
    }

    // K~で入れ替え可能
    vector<P> from;
    for (int i = K; i < N; i++) {
        if (cnt[f[i].second] <= 0) {
            from.push_back(f[i]);
        }
        cnt[f[i].second]++;
    }

    vector<ll> Sfrom(from.size());
    if (from.size() >= 1) {
        Sfrom[0] = from[0].first;
    }
    repi(i, from.size()) {
        Sfrom[i] = Sfrom[i - 1] + from[i].first;
    }


    ll res = base;
    for (int nSwap = 1; nSwap <= K; nSwap++) {
        if (Sto.size() <= nSwap - 1 || Sfrom.size() <= nSwap - 1) {
            continue;
        }
        // 1~Kと重複のないものをK+1~からnSwap個選んで、
        // それを1~Kの重複のあるものをコストが小さい順に並び替えることを考える
        ll v = base - Sto[nSwap-1] + Sfrom[nSwap-1];
        v = v - nNeta*nNeta + (nSwap + nNeta) * (nSwap + nNeta);
        res = max(res, v);        
    }

    put(res);
}
signed main(){ Main();return 0;}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}

int main() {
  ll A, B, N; cin >> A >> B >> N;
  ll ans = 0;
  if(N < B) {
    ll tmp = A * N;
    ans = tmp / B;
  } else {
    ll tmp3 = A * (B - 1);
    ll E = tmp3 / B;

    ll tmp = A * N;
    ll C = tmp / B;
    ll tmp2 = N / B;
    ll D = A * tmp2;
    // ans = max(E, C - D);
    ans = E;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3548
#include <iostream>

using namespace std;

int trinum[46];

void init() {
    trinum[0] = 1;
    for (int i = 1; i < 46; i++) {
        trinum[i] = trinum[i-1] + i + 1;
    }
}

int count(int n) {
    int total = 0;
    for (int i = 0; trinum[i] + 1 < n; i++) {
        if ((n - trinum[i]) % (i + 2) == 0) {
            total++;
        }
    }
    return total;
}

int main() {
    init();
    int n;
    while (cin >> n) {
        if (n == 0) break;
        cout << count(n) << endl;
    }
    return 0;
}

Measured memory_bytes: 0
import java.util.Arrays;
import java.util.Scanner;

class Main{


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int a = sc.nextInt();
		int b  =sc.nextInt();
		int c = sc.nextInt();
		int[] data = {a,b,c};
		Arrays.sort(data);
		if(data[2] == (data[0] + data[1])){
			System.out.println("Yes");
		}else{
			System.out.println("No");

		}
		
				
	}
}

Measured memory_bytes: 21844
#include "bits/stdc++.h"
using namespace std;

int main()
{
	int A, B, K;
	cin >> A >> B >> K;

	int loop = min(A, B);

	vector<int> vec;

	for (int i = 1; i <= loop; i++) {
		if (A % i == 0 && B % i == 0) {
			vec.insert(vec.begin(),i);
		}
	}


	cout << vec.at(K-1) << endl;
}

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

const char wall = '#';
vector<vector<bool>> used;
vector<vector<ll>> dist;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {1, 0, -1, 0};

vector<ll> A;
// vectorのリサイズ
// A.resize(N);

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a*b/gcd(a, b);}

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

  ll n, m;
  cin >> n >> m;
  vector<vector<ll>> fields(n);
  rep(i, m) {
    ll a, b;
    cin >> a >> b;
    a--; b--;
    fields[a].push_back(b);
    fields[b].push_back(a);
  }
  for(ll o: fields[0]) {
    for(ll i: fields[o]) {
      if (i == n-1) {
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 12776
#include <stdio.h>
#define MAX_LENGTH 100000
int Arr[MAX_LENGTH]={0};
int n=0;
int b = 0;
int Partition(int Arr[], int p, int r)
{
    int x=Arr[r];
    int i=p-1;
    for(int j=p;j<r;j++)
    {
        if(Arr[j]<=x)
        {
            i+=1;
            int temp=Arr[i];
            Arr[i]=Arr[j];
            Arr[j]=temp;
        }
    }
    int t = Arr[i+1];
    Arr[i+1]=Arr[r];
    Arr[r]=t;
    return i+1;
}
int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    for(int i=0;i<n;i++){scanf("%d ", &Arr[i]);}
    b=Partition(Arr, 0, n-1);
    for(int i=0;i<n;i++)
    {
        if(i==n-1){printf("%d\n", Arr[i]);}
        else if(i==b){printf("[%d] ", Arr[i]);}
        else{printf("%d ", Arr[i]);}
    }
    return 0;
}



Measured memory_bytes: 2116
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace atcorder_yahoo
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] dataArr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); 
            int maxNum = dataArr[0];
            int cnt = dataArr[1];

            int getCnt = 0;

            for(int i = 1; i <= maxNum; i += 2)
            {
                getCnt++;
            }

            string ret = "NO";
            if(cnt <= getCnt)
            {
                ret = "YES";
            }

            Console.WriteLine(ret);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n;
  cin>>n;
  vecint a(n);
  REP(i,n)cin>>a[i];
  int d=0;
  REP(i,n) {
    if ((i%2) == 0) {
      d += a[i];
    } else {
      d -= a[i];
    }
  }
  vecint b(n);
  b[0] = d/2;
  REP(i,n-1) {
    b[i+1] = a[i] - b[i];
  }
  REP(i,n) {
    if(i)cout<<' ';
    cout<<2*b[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
 
using namespace std;
long long mod=1e9+7;
long long INF=1e7;
double EPS = 1e-12;
const long long lim = 2e5+100;
typedef long long int lld;
typedef long long ll;

#define rep(i,a,n) for(long long int i = (a); i <= (n); ++i)
#define mset(a, v) memset(a, v, sizeof(a))
#define Error(x...) { cout << "(" << #x << ")" << " = ( "; printIt(x); }
template <typename T1> void printIt(T1 t1) { cout << t1 << " )" << endl; }
template <typename T1, typename... T2>
void printIt(T1 t1, T2... t2) { cout << t1 << " , "; printIt(t2...); }
 
 
#define popcount __builtin_popcountll
 
ll powP(ll x, ll y) {
    ll ans = 1, po = x % mod;
    while(y > 0) {
        if(y & 1) ans = ans * po % mod;
        y >>= 1; po = po * po % mod;
    }
    return ans;
}


vector<ll> Ans, Adj[lim];
ll Array[lim], C[lim],dp[600][600];
pair<ll,ll> P[lim];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    
    lld T,i,p,j,l,e,r,b,c,k,m,q,a,d,w,x,y,u,v,z,t,curr,prev,sum=0,val,countA=0,indicator=0,pos,h,minA,maxA,type,n,ans=0,left,right;
    string A,B; a=b=0;  
    rep(i,1,3) {
        cin>>x;
        if(x==5) a++;
        else if(x==7) b++;
    }
    if(a==2 and b==1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

    return 0;
}
    


Measured memory_bytes: 8316
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;

int main()
{
    int n, d;
	scanf("%d %d", &n, &d);
	int x[2][1010];
	for(int i=0; i<n; i++) scanf("%d %d", &x[0][i], &x[1][i]);
	two_sat ts(n);
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			for(int k=0; k<2; k++) for(int l=0; l<2; l++) if(abs(x[k][i]-x[l][j])<d) ts.add_clause(i, k^1, j, l^1);
		}
	}
	if(ts.satisfiable()){
		printf("Yes\n");
		auto b=ts.answer();
		for(int i=0; i<n; i++) printf("%d\n", x[b[i]][i]);
	}else{
		printf("No\n");
	}
    return 0;
}


Measured memory_bytes: 3908
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().split()]
h = [0, *(int(x) for x in input().split())]
adj = [[] for i in range(n + 1)]
for _ in range(m):
    u, v = [int(x) for x in input().split()]
    adj[u].append(v)
    adj[v].append(u)
print(sum(1 for u in range(1, n + 1) if all(h[u] > h[v] for v in adj[u])))


Measured memory_bytes: 91488
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;
typedef vector<ll> vint;
int main() {
  string s;
  cin >> s;
  
  vint v(26);
  for (ll i=0;i<s.size();i++) {
    ll x=s.at(i)-'a';
    v.at(x)=1;
  }
  
  for (ll i=0;i<26;i++) {
    if (v.at(i)==0) {
      cout << (char)(i+97);
      break;
    }
    if (i==25) {
      cout << "None";
    }
  }
}

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

int main(void) {
    int x[3];
    cin >> x[0] >> x[1] >> x[2];
    sort(x, x+3);
    if(x[0] == 5 && x[1] == 5 && x[2] == 7)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=2e5+9;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,a[N],b[N];
    map<int,int>cnt;
    ll ans=0;
    cin>>n;
    for(int x,i=1;i<=n;i++){ 
        cin>>x;
        a[i]=x+i;
        b[i]=i-x;
        cnt[b[i]]++;
    }
    for(int i=1;i<=n;i++){ 
        ans+=cnt[a[i]];
    }
    cout<<ans<<'\n';
    
    
    return 0;
}


Measured memory_bytes: 22196
import java.util.Scanner;

public class Main {

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

	    int[] a=new int[4];
	    
	    
	    for (int i=0; i<6;i++) {
	    	int e=gi();
	    	a[e-1]++;
	    }
	    
	    int k=0;
	    for (int i=0; i<4;i++) {
	    	if(a[i]%2==1)k++;
	    }

	    if (k<=2) {
	    	System.out.println("YES");
	    } else {
	    	System.out.println("NO");
	    }
	    //System.out.println(y);
	}


	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35756
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
const ld inf = 1e18;

struct cht {
	struct line {
		ll k, b; ld x;
		ll val; bool isquery;

		line(ll _k = 0LL, ll _b = 0LL) : 
			k(_k), b(_b), x(-inf), val(0), isquery(false) {}

		ll eval(ll x) const { return k * x + b; }
		bool parallel(const line &l) const { return k == l.k; }
		ld intersection(const line &l) const { 
			if(parallel(l)) return inf;
			return (1.0 * l.b - b) / (1.0 * k - l.k);
		}

		bool operator < (const line &l) const 	{
			if(l.isquery) return x < l.val;
			else return k < l.k;
		}
	};

	set<line>hull;
	typedef set<line>::iterator iter;

	bool cPrev(iter it) { return it != hull.begin(); }
	bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

	bool bad(const line &l1, const line &l2, const line &l3) {
		return l1.intersection(l3) <= l1.intersection(l2);
	}
	bool bad(iter it) {
		return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
	}

	iter update(iter it) {
		if(!cPrev(it)) return it;

		ld x = it -> intersection(*prev(it));
		line tmp(*it); tmp.x = x;

		it = hull.erase(it);
		return hull.insert(it, tmp);
	}

	void addLine(ll k, ll b) {
		line l(k, b);
		iter it = hull.lower_bound(l);

		if(it != hull.end() && l.parallel(*it)) {
			if(it->b < b) it = hull.erase(it);
			else return;
		}

		it = hull.insert(it, l);
		if(bad(it)) return (void) hull.erase(it);

		while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
		while(cNext(it) && bad(next(it))) hull.erase(next(it));

		it = update(it);
		if(cPrev(it)) update(prev(it));
		if(cNext(it)) update(next(it));
	}

	ll query(ll x) {
		if(hull.empty()) return -inf;

		line tmp;
		tmp.val = x; tmp.isquery = true;

		iter it = --hull.lower_bound(tmp);
		
		return it -> eval(x);
	}
}ds;


ll n, c;
ll h[maxn];
ll dp[maxn];

int main() {
	cin>>n>>c;
	for(int i=1;i<=n;i++) {
		cin>>h[i];
	}

	dp[1] = 0LL;
	ds.addLine(2*h[1], -(h[1]*h[1] + dp[1]));

	// dp[i] = min(dp[j] + (h[i] - h[j])^2 + C)
	// dp[i] = min(dp[j] + h[i]^2 - 2*h[i]*2[j] + h[j]^2 + C)
	// slope: -2*h[j], extra = h[j]^2 + dp[j] 

	for(int i=2;i<=n;i++) {
		ll curr = -ds.query(h[i]);
		dp[i] = curr + c + h[i] * h[i];

		ds.addLine(2*h[i], -(h[i]*h[i] + dp[i]));
	}


	cout<<dp[n]<<"\n";

}

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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

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

    // 入力
    int n;
    cin >> n;

    // 処理
    if (n % 2 == 0) {
        cout << n << endl;

    } else {
        cout << n * 2 << endl;
    }

    return 0;
}


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

def is_81(num):
    for d in range(1, 10):
        q, mod = divmod(num, d)
        if mod == 0 and q < 10:
            return True
    return False

num = int(input())

if is_81(num):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 2940
#include <iostream>
#include <set>
#include <numeric>
#include <map>
using namespace std;

map <int, int> start_to_ends[30];
int main(void){
   int N;
   int C;
   cin >> N >> C;
   int max_t = 0;
   for(int i = 0; i < N; i++){
       int s;
       int t;
       int c;
       cin >> s >> t >> c;
       start_to_ends[c - 1][s - 1] = t;
       max_t = max(max_t, t);
   }
   
   int ans = 0;
   for(int i = 0; i < max_t; i++){
       int overlap = 0;
       for(int j = 0; j < C; j++){
           auto it = start_to_ends[j].upper_bound(i);
           //cout << max_t << endl;
           if(it == start_to_ends[j].begin()){
               continue;
           } else {
               it --;
               int cur_s = it->first;
               int cur_t = it->second;
               //cout << cur_s << " " <<cur_t << endl;
               if(cur_s <= i && i < cur_t){
                   overlap ++;
               }
           }
       }
       ans = max(ans, overlap);
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
 
int main(){
  int i, j, s, f, d, sum;
 
  while(scanf("%d", &d) != EOF){
    sum = 0;
    for(i=d, j=1; i<600; i+=d, j++){
      s = j * d;
      f = s * s;
      sum += (d * f);
    }
 
    printf("%d\n", sum);
  }
 
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)
 
int main() {

 long double angL;
 long double angS;
 long double t,s;
 long double ans;
 long double  A,B,H,M;
 cin>>A>>B>>H>>M;

 angL=(long double)((H*60.0+M)/2.0);
 angS=(long double)(M*6.0);

 s=(long double)(abs(angL-angS));
 t=(long double)((s/180.0)*pi);

 ans=(long double)(A*A+B*B-2.0*A*B*cos(t));

printf("%20.20Lf",sqrt(ans));


}

Measured memory_bytes: 4160
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=j; i<=k; i++)
#define FFOR(i, j, k) for(int i=j; i<k; i++)
#define DFOR(i, j, k) for(int i=j; i>=k; i--)
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "D"
string s;
bool check(int k){
    if(k+k-1<=s.size()) return 1;
    int off=0;
    int maxcontrol=s.size()-k;
    FOR(i, 0, maxcontrol) if((s[i]+off)%2) off++;
    FFOR(i, maxcontrol+1, k) if((s[i]+off)%2) return 0;
    return 1;
}
int main(){
    #ifdef Megumin
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Megumin
    cin>>s;
    for(char &c: s) c-=48;
    int l=1, r=s.size(), m, ans=0;
    while(l<=r){
        m=(l+r)/2;
        if(check(m)){
            ans=m;
            l=m+1;
        }
        else r=m-1;
    }
    write(ans);
}

Measured memory_bytes: 512
solve :: Int -> Int -> Int
solve m d = length [ (x, y10, y1) | x <- [1 .. m], y10 <- [2 .. 9], y1 <- [2 .. 9], y10 * 10 + y1 <= d, x == y10 * y1]

main :: IO ()
main = do
  [m, d] <- fmap (\x -> read x :: Int) . words <$> getLine
  print $ solve m d


Measured memory_bytes: 508
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,vl>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
const ll INF=1LL<<60;
const ll MOD=1000000007;




int main(){
    ll N;
    cin >> N;
    ll M;
    cin >> M;
    vector<ll> S(N+1,0);
    vector<ll> T(M+1,0);
    for(ll i=1;i<=N;i++){
        cin>>S[i];
    ;}
    for(ll i=1;i<=M;i++){
        cin>>T[i]
    ;}

    //dp[i][j]はS[i]とT[j]を最後とする共通整数列の数
    vector<vector<ll>> dp(N+1, vector<ll>(M+1, 0));
    vector<vector<ll>> sum(N+1, vector<ll>(M+1, 0));
    for(ll i=1;i<=N;i++){
     for(ll j=1;j<=M;j++){
         if(S[i]!=T[j])dp[i][j]=0;
         else dp[i][j]=sum[i-1][j-1]+1;
         sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j]+MOD;
         sum[i][j]%=MOD;
     ;}
    ;}
    cout<<(sum[N][M]+1)%MOD<<endl;

    
    


    return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<double> v(n);
  for (auto&& e : v) {
    cin >> e;
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < n - 1; i++) {
    v[i + 1] = (v[i] + v[i + 1]) / 2.;
  }
  cout << fixed << setprecision(10) << v[n - 1] << '\n';
  return 0;
}


Measured memory_bytes: 3804
H, W = map(int, input().split())
S = [[] for _ in range(H)]
for i in range(H):
    S[i] = list(input())

count = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            count[i][j] = 10**7
        else:
            count[i][j] = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            if j != W-1: 
                if S[i][j+1] == '#':
                    count[i][j] += 1
            if j != 0: 
                if S[i][j-1] == '#':
                    count[i][j] += 1
            if i != H-1: 
                if S[i+1][j] == '#':
                    count[i][j] += 1
            if i != 0: 
                if S[i-1][j] == '#':
                    count[i][j] += 1

check = 0
for i in range(H):
    for j in range(W):
        if count[i][j] < 1:
            check = 1

if check == 0:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;
//========================================================================


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	int A, B, C;
	cin >> A >> B >> C;

	cout << B + min(C, A + B + 1);




}


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

int main()
{

  int a, b;
  cin >> a >> b;
  cout << a + b / 2 << endl;
  return 0;
}

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MAX_COMB = 2e5+4;
const LL mod = 1e9 + 7;
LL fct[MAX_COMB+1];
LL invfct[MAX_COMB+1];

void build(){
	fct[0] = fct[1] = 1;
	repp(i,2,MAX_COMB+1){
		fct[i] = fct[i-1] * i % mod;
	}
	LL x = fct[MAX_COMB];
	invfct[MAX_COMB] = 1;
	for(int i = mod - 2 ; i > 0 ; i >>= 1){
		if(i % 2 == 1) (invfct[MAX_COMB] *= x) %= mod;
		(x *= x) %= mod;
	}
	repm(i,MAX_COMB,0){
		invfct[i-1] = invfct[i] * i % mod;
	}
}

LL comb(int x , int y){
	x += y;
	if(x < 0 || y < 0 || x < y) return 0;
	return fct[x] * invfct[y] % mod * invfct[x-y] % mod;
}

int main(){
	build();
	int H,W,N; cin >> H >> W >> N;
	vector<pair<int,int>> p(N);
	repp(i,0,N) cin >> p[i].first >> p[i].second;
	sort(p.begin(),p.end());
	vector<LL> dp(N);
	LL ans = comb(H-1,W-1);
	repp(i,0,N){
		dp[i] = mod-comb(p[i].first-1,p[i].second-1);
		repp(j,0,i) (dp[i] -= dp[j]*comb(p[i].first-p[j].first,p[i].second-p[j].second)) %= mod;
		(ans += dp[i]*comb(H-p[i].first,W-p[i].second)) %= mod;
	}
	cout << (ans+mod)%mod << endl;
	return 0;
}


Measured memory_bytes: 3456
H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
ans=[]

for i in range(H):
    for j in range(W):
        if A[i][j]%2==1:
            if i==H-1 and j==W-1:
                continue
            elif j==W-1:
                A[i+1][j]+=1
                A[i][j]-=1
                ans.append([i+1,j+1,i+2,j+1])
            else:
                A[i][j+1]+=1
                A[i][j]-=1
                ans.append([i+1,j+1,i+1,j+2])

print(len(ans))
for i in ans:
    print(*i)

Measured memory_bytes: 72284
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    int64 n,k;
    cin >> n >> k;

    int64 i = n / k;
    int64 ans = abs(n - k * i);
    ans = min(ans, abs(n - k*(i-1)));
    ans = min(ans, abs(n - k*(i+1)));
    cout << ans << endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define pq priority_queue
using namespace std;
constexpr long long gcd(long long a, long long b){return b ? gcd(b, a % b) : a;}
constexpr long long lcm(long long a, long long b){return a / gcd(a, b) * b;}
constexpr int INF = 1e9, MOD = INF + 7, around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
constexpr int mod_pow(long long x, long long n, const int mod){long long ret=1;while(n){if(n&1)(ret*=x)%=mod;(x*=x)%=mod;n>>=1;}return ret;}
template<int n> struct Prime{bool arr[n+1];constexpr bool operator[](int k){return arr[k];}constexpr Prime():arr(){for(int i=2;i<n;i++){arr[i]=true;for(int j=2;j*j<=i;j++){if(!(i%j))arr[i]=false;}}}};
template<int n> struct Factorial{long long arr[n+1],ary[n+1];constexpr Factorial():arr(),ary(){arr[0]=1;ary[0]=1;for(int i=0;i<n;i++){arr[i+1]=arr[i]*(i+1)%MOD;ary[i+1]=mod_pow(arr[i+1],MOD-2,MOD);}}};
constexpr Factorial<1010> fact; constexpr Prime<10> prime;
constexpr long long comb(int a, int b){if(a < b) return 0LL;if(!a or !b) return 1LL; long long pos = fact.arr[a], pot = fact.ary[a - b], por = fact.ary[b]; return pos * pot % MOD * por % MOD;}
template<int n> struct Bernoulli{long long arr[n+1];constexpr Bernoulli():arr(){arr[0]=1;for(int i=1;i<=n;i++){long long sum=0;for(int j=0;j<i;j++){(sum+=comb(i+1,j)*arr[j]%MOD)%=MOD;}arr[i]=(MOD-mod_pow(i+1,MOD-2,MOD))%MOD*sum%MOD;}}};
constexpr int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
constexpr long double PI = abs(acos(-1));
constexpr int sqrtN = 512, logN = 32;
constexpr long long LINF=1e18;

int main(){
	int n; cin >> n; vector<long long> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(begin(a), end(a));
	
	long long mi = LINF, pos = 0;
	for(int i = 0; i < n - 1; i++){
		if(a.back() % 2){
			long long D = abs(a.back() / 2 - a[i]);
			D = min(D, abs(a.back() / 2 + 1 - a[i]));
			
			if(mi > D){
				mi = D;
				pos = i;
			}
		}else{
			long long D = abs(a.back() / 2 - a[i]);
			
			if(mi > D){
				mi = D;
				pos = i;
			}
		}
	}
	
	cout << a.back() << " " << a[pos] << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define pb push_back
#define ff first 
#define ss second  
typedef pair<int,int> pp;
bool com(pp x,pp y){
    return x.ff<y.ff;
} 
int N=1e5+9;
ll multiply(ll x,ll y){
    return ((x%mod)*(y%mod))%mod;
}
ll sum(ll x,ll y){
    return (x%mod+y%mod)%mod;
}
void solve(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=max(b*d,a*c);
    ans=max(max(a*d,b*c),ans);
    cout<<ans;
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) 
	    solve();
	return 0; 
	
}


Measured memory_bytes: 3656
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int k = scan.nextInt();
		int i = 1;

		long mod = 0;

		if(k % 2 == 0 || k % 5 == 0) {
			System.out.println(-1);
		}else {
			do {
				mod *= 10;
				mod += 7;
				if(mod % k == 0) {
					System.out.println(i);
				}
				mod = mod % k;
					i++;
			}while(mod % k != 0);

		}

		scan.close();
	}
}


Measured memory_bytes: 35760
#include "bits/stdc++.h"

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}
/*
typedef __int128_t Int;
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
  if (s) {
	__uint128_t tmp = value < 0 ? -value : value;
	char buffer[128];
	char *d = std::end(buffer);
	do {
	  --d;
	  *d = "0123456789"[tmp % 10];
	  tmp /= 10;
	} while (tmp != 0);
	if (value < 0) {
	  --d;
	  *d = '-';
	}
	int len = std::end(buffer) - d;
	if (dest.rdbuf()->sputn(d, len) != len) {
	  dest.setstate(std::ios_base::badbit);
	}
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
	if ('0' <= s[i] && s[i] <= '9')
	  ret = 10 * ret + s[i] - '0';
  return ret;
}
*/

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template <class T> bool chmin(T &a, const T &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int Q; cin >> Q;
	vector<int>A(Q), B(Q); rep(i, 0, Q) { cin >> A[i] >> B[i]; }
	rep(i, 0, Q) {
		int a = A[i], b = B[i];
		if (a > b)swap(a, b);
		int ab = a * b;
		if (abs(a - b) <= 1) {
			cout << 2 * (a - 1) << endl;
		}
		else {
			int c = sqrt(ab);
			if (c*c == ab)c--;
			if (c*(c + 1) >= ab) {
				cout << 2 * c - 2 << endl;
			}
			else {
				cout << 2 * c - 1 << endl;
			}
		}
	}


	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(x) x.begin(),x.end()
#define MOD 1000000007

using namespace std;
typedef long long ll;

template<typename T>
T gcd(T a, T b) {
    if (a % b == 0) {
        return(b);
    }
    else {
        return(gcd(b, a % b));
    }
}

template<typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

ll cnt(ll n) {
    ll ans = 0;
    for (ll i = 1; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            ++ans;
            if (n / i != i) {
                ++ans;
            }
        }
    }
    return ans;
}

int main(void) {
    ll n;
    cin >> n;
    ll ans = 0;
    for (ll a = 1; a < n; ++a) {
        ll b = 1;
        while (a * b < n) {
            ++ans;
            ++b;
        }
    }
    cout << ans;
}



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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<int>h(n);
    for(int i=0;i<n;i++)
        cin>>h[i];
    int c[n]={0};
    int tr[n]={0};
    tr[0]=1;
    queue<int>q;
    q.push(0);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(x+1<n)
        {
            if(tr[x+1]==0)
            {
                c[x+1]=c[x]+abs(h[x]-h[x+1]);
                q.push(x+1);
                tr[x+1]=1;
            }
            else
            {
                if(c[x+1]>c[x]+abs(h[x]-h[x+1]))
                {
                    q.push(x+1);
                    c[x+1]=c[x]+abs(h[x]-h[x+1]);
                }
            }
        }
        if(x+2<n)
        {
            if(tr[x+2]==0)
            {
                c[x+2]=c[x]+abs(h[x]-h[x+2]);
                q.push(x+2);
                tr[x+2]=1;
            }
            else
            {
                if(c[x+2]>c[x]+abs(h[x]-h[x+2]))
                {
                    q.push(x+2);
                    c[x+2]=c[x]+abs(h[x]-h[x+2]);
                }
            }
        }
    }
    cout<<c[n-1]<<endl;
}


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

int main()
{
	char b;
	cin >> b;

	switch (b)
	{
	case 'A':
		cout << "T\n";
		break;
	case 'C':
		cout << "G\n";
		break;
	case 'T':
		cout << "A\n";
		break;
	case 'G':
		cout << "C\n";
		break;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define BITS 60

const ll mod = 1e9+7;

template<typename T>
T modMul(T a, T b, T m) {
	T x = 0, y = a % m;
	while (b > 0) {
		if (b % 2 == 1) x = (x + y) % m;
		y = (y * 2) % m; b /= 2;
	}
	return x % m;
}

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin.exceptions(cin.failbit);
    int n, maior = 0;
    cin >> n;
    ll a[n], ones[BITS], zeroes[BITS];
    memset(ones, 0 ,sizeof ones);
    memset(zeroes, 0, sizeof zeroes);
    rep(i, 0, n){
        cin >> a[i];
        rep(j, 0, BITS){
            ones[j] += ((a[i] & (1LL << j)) > 0);
            //cout << ones[i+1][j];
            zeroes[j] +=((a[i] & (1LL << j)) == 0);
            //cout << zeroes[i+1][j];
        }
        maior = max(maior, (int)log2(a[i]) + 1);
       //x   cout << '\n';
    }
    ll ans = 0;
    
    rep(j, 0, maior){
        //cout << zeroes[n][j] - zeroes[i][j] << '\n';
        ans += modMul((ones[j])*(zeroes[j]), 1LL<<j, mod);
        ans %= mod;
    }
    
    cout << ans << '\n';
    return 0;
}


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

signed main(){
	int N;
	string S;
	cin >> N>>S;
	int ans =0;
	for(int i=0;i<N-2;i++){
		if(S.at(i)=='A' &&S.at(i+1)=='B'&&S.at(i+2)=='C')ans++;
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 256
s = input()
n = len(s)
p = []
ans = [0]*n

p.append(-1)
for i in range(n-1):
    if s[i] != s[i+1]:
        p.append(i)
p.append(n-1)
m = len(p)

for i in range(1, m, 2):
    start = p[i-1]+1
    end = p[i+1]+1
    mid = p[i]
    r_pos = p[i]
    l_pos = p[i]+1
    r_num = mid - start + 1
    l_num = end - mid - 1

    if (r_num + l_num) % 2 == 0:
        ans[r_pos] = (r_num + l_num) // 2
        ans[l_pos] = (r_num + l_num) // 2
    elif r_num > l_num:
        ans[r_pos] = (r_num + l_num) // 2 + (r_num % 2 != 0)
        ans[l_pos] = (r_num + l_num) // 2 + (r_num % 2 == 0)
    elif r_num < l_num:
        ans[l_pos] = (r_num + l_num) // 2 + (l_num % 2 != 0)
        ans[r_pos] = (r_num + l_num) // 2 + (l_num % 2 == 0)


print(' '.join(list(map(str, ans))))


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

ll a[MAX];
int dp[MAX][2];
int main(){
	int n, k, tmp;
	while(cin >> n >> k, n){
	fill(a, a+MAX, 0);
	fill((int*)dp, (int*)(dp+MAX), 0);
	for(int i = 0;i < k;i++){
		cin >> tmp;
		a[tmp] = 1;
	}
	
	int ans = 0;
	for(int i = 1;i < MAX;i++){
		if(a[i])dp[i][0] = dp[i-1][0]+1;
		if(dp[i-1][0] <= dp[i-1][1] && !a[i])dp[i][1] = dp[i-1][0]+1;
		else if(a[i])dp[i][1] = dp[i-1][1]+1;
		ans = max(ans, dp[i][0]);
		if(a[0])ans = max(ans, dp[i][1]);
	}
	//for(int i = 1;i <= 10;i++)cout << i << " " << dp[i][1]  << endl;
	cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 4636
#include <iostream>
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        int a,b,c;
        a=N/100;
        b=(N-100*a)/10;
        c=N%10;
        if(a==7||b==7||c==7)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3592
from fractions import gcd
import sys
a,b = map(int,input().split())
g = gcd(a,b)
ans = 1
if g % 2 == 0:
    ans += 1
    while g % 2 == 0:
        g //= 2
if g == 1:
    print(ans)
    sys.exit()
for i in range(3,int(g**(0.5))+2,2):
    if g % i == 0:
        ans += 1
        while g%i == 0:
            g //= i
    if g == 1:
        break
else:
    ans += 1
print(ans)    

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

int main(){
  int n;
  cin >> n;
  int a,b,c,d;
  d=n%10;
  c=(n/10)%10;
  b=(n/100)%10;
  a=(n/1000)%10;
  if(a+b+c+d==7)cout << a <<"+"<<b << "+"<<c<<"+"<< d<<"=7" <<endl;
  else if(a+b+c-d==7)cout << a <<"+"<<b << "+"<<c<<"-"<< d<<"=7" <<endl;
  else if(a+b-c+d==7)cout << a <<"+"<<b << "-"<<c<<"+"<< d<<"=7" <<endl;
  else if(a+b-c-d==7)cout << a <<"+"<<b << "-"<<c<<"-"<< d<<"=7" <<endl;
  else if(a-b+c+d==7)cout << a <<"-"<<b << "+"<<c<<"+"<< d<<"=7" <<endl;
  else if(a-b+c-d==7)cout << a <<"-"<<b << "+"<<c<<"-"<< d<<"=7" <<endl;
  else if(a-b-c+d==7)cout << a <<"-"<<b << "-"<<c<<"+"<< d<<"=7" <<endl;
  else if(a-b-c-d==7)cout << a <<"-"<<b << "-"<<c<<"-"<< d<<"=7" <<endl;



  
  return 0;

}


Measured memory_bytes: 256
#入力受け取り
n = int(input())
tourList = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    tourList.append(array)

#DebugPrint
currentTime = 0
currentX = 0
currentY = 0

for i in range(len(tourList)) :
    Time = tourList[i][0]
    X = tourList[i][1]
    Y = tourList[i][2]

    Time = Time - currentTime
    X = X - currentX
    Y = Y - currentY
    flag=False

    NUM = abs(X)+abs(Y)
    if( (Time-NUM)%2==0 and NUM <= Time):
        flag=True

    # while (X+Y+Z) <= Time :
    #     if X+Y+Z == Time:
    #         flag=True
    #         break
    #     else:
    #         Z+=2
    
    #継続判定
    if flag == False:
        print("No")
        exit()
    
    currentTime = Time
    currentX = X
    currentY = Y

print("Yes")

    #最初の点がまず実現可能か


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

ans = [0]*N
for i in range(N-1):
    c,s,f = map(int,input().split())
    ans[i] += s+c
    for j in range(i):
        ans[j] = max((ans[j]+f-1)//f*f, s)+c
for a in ans:
    print(a)

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x[] = new long[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextLong();
        }

        long ans = 0;
        for (int i = 0; i < n - 1; i++) {
            ans += Math.min(b, a * (x[i + 1] - x[i]));
        }
        System.out.println(ans);
    }

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


Measured memory_bytes: 49272
#include<bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define mod 1000000007
#define P pair<int,int>
using namespace std;
signed main(){
	int a,b,c;
	cin>>c>>a>>b;
	cout<<min(a,b)<<" "<<max((int)(0),(a+b-c))<<endl;
	return 0;
}


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

using namespace std;

typedef long long ll;

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

  if(n==1&&m==1) cout<<1<<endl;
  else if(n == 1 || m == 1) cout<<max(n-2,m-2)<<endl;
  else {
      cout<<(n*m)-(n+n+m+m-4)<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define INIT_LOOP 0														/* ??????????????????					*/
#define SECOND_ELEMENT 1												/* 2?????????????´?					*/
#define EXIT_SUCCESS 0													/* ????????????????????????				*/

int main( void )
{
	unsigned long usW_Delement_cnt;										/* ????´??????°						*/
	unsigned long usW_Dloop_cnt;										/* ?????????????????????				*/
	signed long ulW_Delement;											/* ????´?							*/
	signed long ulW_Delement_first;										/* 1?????????????´??¨???¶?????°			*/
	signed long ulW_Delement_min;										/* ????°?????¨???¶?????°				*/
	signed long slW_Delement_max;										/* ?????§????¨???¶?????°				*/
	signed long slW_Dcalc;												/* ?¨??????¨?????°					*/

	scanf("%d", &usW_Delement_cnt );									/* ????´??????°?????\???				*/
	/* ????´??????°??????????????? */
	for( usW_Dloop_cnt = INIT_LOOP; usW_Dloop_cnt < usW_Delement_cnt; usW_Dloop_cnt++){
		scanf("%ld", &ulW_Delement );									/* ????´??????\???					*/
		/* ????´????1?????????????´??????£?????´??? */
		if( usW_Dloop_cnt == INIT_LOOP ){
			ulW_Delement_first = ulW_Delement;							/* 1?????????????´??¨???¶?????°?????????	*/
		}
		else{
			/* else???????????????????????§?????\ */
		}

		slW_Dcalc = ulW_Delement - ulW_Delement_min;					/*?????????????¨????					*/
		/* ????´????2?????????????´??????£?????´??? */
		if( usW_Dloop_cnt == SECOND_ELEMENT ){
			slW_Delement_max = ulW_Delement - ulW_Delement_first;		/* ?????§????¨???¶?????°????????????????¨????	*/
		}
		/* ????´?-????°????????????§???????????§????????´??? */
		else if( slW_Delement_max < slW_Dcalc ){
			slW_Delement_max = ulW_Delement - ulW_Delement_min;			/* ?????§??????????´?-????°????????????????	*/
		}
		else{
			/* else?????????????????????????????\*/
		}

		/* ????´????1?????????????´??????£?????´??? */
		if( usW_Dloop_cnt == INIT_LOOP ){
			ulW_Delement_min = ulW_Delement;							/* ????°?????¨???¶?????°????????????????¨????	*/
		}
		/* ????´????????°???????????°?????????´??? */
		else if( ulW_Delement_min > ulW_Delement ){
			ulW_Delement_min = ulW_Delement;							/* ????°???????????´?????????????			*/
		}
		else{
			/* else?????????????????????????????\ */
		}

	}
	printf("%ld\n", slW_Delement_max);									/* ?????§????????????					*/
	return EXIT_SUCCESS;
}

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

for i in range(N+1):
    for j in range(N+1):
        if N-i-j>=0:
            if 10000*i+5000*j+1000*(N-i-j)==Y:
                print(i,j,N-i-j)
                exit()
print('-1','-1','-1')
        

Measured memory_bytes: 9028
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using static System.Console;
using static System.Math;
using static System.Array;

class Program
{
    public static void Main()
    {
        var n = ReadLine();
        if(n[n.Length - 1] == 's')
            WriteLine(n + "es");
        else
            WriteLine(n + "s");
    }
}


Measured memory_bytes: 17364
#include <bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
   	
int main() {
	char x;

	cin >> x;

	if (isupper(x))
	{
		cout << "A";
	}
	else
	{
		cout << "a";
	}

	return 0;
}

Measured memory_bytes: 3592