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

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

	int N;
	cin >> N;

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

	map<int, int> map;
	for(int i = 0; i < N; i++) {
		map[a[i]] = 0;
	}
	int cnt = 0;
	for(auto v : map) {
		map[v.first] = cnt++;
	}
	for(int i = 0; i < N; i++) {
		a[i] = map[a[i]];
	}

	

	int c = 0;
	for(int i = 0; i < N; i++) {
		if(i % 2 != a[i] % 2) c++;
	}
	cout << c / 2 << endl;
}

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

int main(void)
{
	int n,b, f, r, v;
	int nyu[5][4][11];

	rep(i, 5)
		rep(j, 4)
			rep(k, 11)
				nyu[i][j][k]=0;

	cin >> n;
	rep(i, n)
	{
		cin >> b >> f >> r >> v;
		nyu[b][f][r] += v;
	}

	for (int i = 1;i <= 4;++i)
	{
		for (int j = 1;j <= 3;++j)
		{
			for (int k = 1;k <= 10;++k)
			{
				cout << " " << nyu[i][j][k];
			}
			cout << endl;
		}
		if (i<4)
			cout << "####################" << endl;
	}
}



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

int main(){
    ll n,m,i,j;
    cin>>n>>m;
    char ch[n][m];
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)
        cin>>ch[i][j];
    }
    ll dp[n][m];
    memset(dp,0,sizeof(dp));
    for(i=0;i<n;i++){
        if(ch[i][0]=='#')
        break;
        else
        dp[i][0]=1;
    }
    for(j=0;j<m;j++){
        if(ch[0][j]=='#')
        break;
        else
        dp[0][j]=1;
    }
    for(i=1;i<n;i++){
        for(j=1;j<m;j++){
            if(ch[i][j]!='#')
            dp[i][j]=(dp[i-1][j]%mod+dp[i][j-1]%mod)%mod;
            else
            dp[i][j]=0;
        }
    }
    cout<<dp[n-1][m-1]%mod;
}

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

void solve () {
    long long n;
    cin >> n;
    long long ans = n;
    long long x = ans;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            ans = min (ans, i + n / i);
        }
    }
    long long p = 2;
    if (ans == x) p = 1;
    cout << ans - p;
}

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


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

int main() {
	int n;
	cin>>n;
	int a[n-1];
	map<int, int> M;
	for(int i=1;i<n;i++) {
		cin>>a[i];
		M[a[i]]++;
	}
	for(int i=1;i<=n;i++) {
		if(M[i]) cout<<M[i]<<"\n";
		else cout<<0<<"\n";
	}
	return 0;
}

Measured memory_bytes: 13792
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


D = z()
C = zz()
S = defaultdict(list)
for i in range(D):
    S[i+1] = zz()
for i in range(D):
    print(np.argmax(S[i+1]) + 1)


Measured memory_bytes: 27688
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));



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

	int N, C;
	cin >> N >> C;
	vector<pair<int,pair<int,int> > > A;
	REP(i, N) {
		int s, t, c;
		cin >> s >> t >> c;
		A.push_back(make_pair(c, make_pair(s, t)));
	}
	SORT(A);
	REP(i, N) {
		//cout << A[i].first << " " << A[i].second.first << " " << A[i].second.second << endl;
	}

	int cnt[30][100001] = { 0 };
	REP(i, N) {
		eFOR(j, A[i].second.first, A[i].second.second) {
			if(cnt[A[i].first - 1][j]==0)
				cnt[A[i].first - 1][j]++;
		}
	}
	int ans = 0;
	eFOR(i,1,100000 ) {
		int co = 0;
		REP(j, 30) {
		
			co += cnt[j][i];
			ans = max(ans, co);
			//cout << cnt[j][i];
		}
		//cout << endl;
	}

	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 26864
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N,K,ans = 0;
  cin >> N >> K;
  vector<int>vec(N);
  for(int i=0; i<N; i++){
    cin >> vec[i];
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for(int i=0; i<N; i++){
   if(i<K){
     continue;
   }
    else{
      ans += vec[i];
    }
  }
cout << ans << endl;
}
      

Measured memory_bytes: 3980
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>   //PBDS
#include <ext/pb_ds/tree_policy.hpp>       //PBDS
#define int long long int
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pi pair<int,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mi map<int,int>
#define PI  3.141592653589
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define f(i,x,n) for(int i=x;i<n;i++)
#define rf(i,x,n) for(int i=n-1;i>=x;i--)
#define check(x)   cerr<<#x<<" : "<<x<<endl;
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fbo find_by_order                    //return iterator PBDS
#define ook order_of_key                     //return number :)) PBDS
#define baar exit(0)
using namespace __gnu_pbds;
using namespace std;
int powmod(int base,int exponent,int mod)
{
    int ans=1;
    while(exponent){
        if(exponent&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        exponent/=2;
    }
    return ans;
}
signed main()
{
//   #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   #endif
    fast
    int n;
    cin>>n;
    string s;
    cin>>s;
    vi v,v1;
    f(i,0,n)
    {
    	if(s[i]=='W') v.pb(i);
    	else v1.pb(i);
	}
	reverse(all(v1));
	int l=0,r=0;
	int cnt=0;
	while(l!=v.size() && r!=v1.size())
	{
		
		if(v[l]>v1[r])
		{
			break;
		}
		if(v1[r]>v[l])
		{
			l++;
			r++;
			cnt++;
		}
	}
	cout<<cnt;
	//cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
    return 0;
}

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

#define int            long long int
#define float          long double
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define inf            1e18
#define set_pre(x,y)   fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define pi             3.14159265358979323
using namespace std;

int32_t main()
{
    int n;
    cin>>n;
    map<int,string>m;
    m[0]="pon";
    m[1]="pon";
    m[2]="hon";
    m[3]="bon";
    m[4]="hon";
    m[5]="hon";
    m[6]="pon";
    m[7]="hon";
    m[8]="pon";
    m[9]="hon";
    cout<<m[n%10];

}

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

int main(){
	int c[3][3];
	for (int i = 0;i < 3;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> c[i][j];
		}
	}

	int diffb[2];
	diffb[0] = c[0][0] - c[0][2];
	diffb[1] = c[0][1] - c[0][2];
	for (int i = 1;i < 3;i++) {
		for (int j = 0;j < 2;j++) {
			if (diffb[j] != c[i][j] - c[i][2]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	int diffa[2];
	diffa[0] = c[0][0] - c[2][0];
	diffa[1] = c[1][0] - c[2][0];
	for (int i = 1;i < 3;i++) {
		for (int j = 0;j < 2;j++) {
			if (diffa[j] != c[j][i] - c[2][i]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}

	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256
from bisect import bisect_left
n = int(input())
ls = map(int, input().split())
ls = sorted(ls)

counter = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        counter += (bisect_left(ls, ls[i] + ls[j]) - 1) - j

print(counter)


Measured memory_bytes: 3188
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  string s;
  cin >> s;
  if(s[0] == s[2]) {
    puts("Yes");
  } else {
    puts("No");
  }
  return 0;
}


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

#define int long long
#define sz(x) (int)(x.size())
#define fi first
#define se second
#define pii pair<int, int>

const int N = 3001;
int n, a[N];
int dp[N][N][2];

int solve(int l, int r, int turn){
    if(dp[l][r][turn] != -1){
        return dp[l][r][turn];
    }
    if(l == r){
        return dp[l][r][turn] = (turn ? -a[l] : a[l]);
    }
    if(turn == 0){
        dp[l][r][turn] = max(a[l] + solve(l + 1, r, 1 - turn), a[r] + solve(l, r - 1, 1 - turn));
    }else{
        dp[l][r][turn] = min(-a[l] + solve(l + 1, r, 1 - turn), -a[r] + solve(l, r - 1, 1 - turn));
    }
    return dp[l][r][turn];
}

signed main(){
    ios::sync_with_stdio(false);
    memset(dp, -1, sizeof dp);
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    cout << solve(0, n - 1, 0) << "\n";
}

Measured memory_bytes: 141184
n = gets.to_i
as = gets.split.map &:to_i

sum = as.inject(:+)

aa = []

start = 0
as.each{ |a|
	aa << start + a
	start += a
}

c_sum = sum / 2

x = aa.bsearch_index{ |a|
	a >= c_sum
}


if aa[x] == c_sum then
	puts 0
else
	puts [(sum - aa[x-1] * 2), (aa[x] * 2 - sum)].min
end


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


using namespace std;
double pi=3.14159265358979323846264338;
long long sum;

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	if(b*c>=a)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 2005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

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);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_nodes,D,dis[MAXN],res=INT_MAX;
bool vis[MAXN];
vector<int> connections[MAXN];
vector<pii> edges;

inline void init(int rt, int ignore){
	memset(vis,false,sizeof vis);
	queue<int> q;
	q.push(rt);
	vis[rt] = true;
	dis[rt] = 0;
	while(q.size()){
		int node = q.front(); q.pop();
		for(int check:connections[node]){
			if(vis[check] || check == ignore) continue;
			vis[check] = true;
			dis[check] = dis[node]+1;
			q.push(check);
		}
	}
}

int main(){
	scanf("%d %d",&num_nodes,&D);
	for(int i=1; i<num_nodes; i++){
		int a,b; scanf(" %d %d",&a,&b);
		connections[a].pb(b);
		connections[b].pb(a);
		edges.pb(mp(a,b));
	}
	if(D%2 == 0){
		for(int rt=1; rt<=num_nodes; rt++){
			init(rt,-1);
			int cnt = 0;
			for(int i=1; i<=num_nodes; i++)
				if(dis[i] > D/2)
					cnt++;
			res = min(res,cnt);
		}
	}else{
		for(pii check:edges){
			init(check.first,check.second);
			init(check.second,check.first);
			int cnt = 0;
			for(int i=1; i<=num_nodes; i++){
				if(dis[i] > D/2)
					cnt++;
			}
			res = min(res,cnt);
		}
	}
	printf("%d\n",res);
}

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

int main()
{
  string s;
  cin >> s;
  cout << s;
  if (s[s.length() - 1] == 's')
  {
    cout << "es" << endl;
  }
  else
  {
    cout << "s" << endl;
  }
}


Measured memory_bytes: 3596
using System;
using System.Linq;
using System.Collections.Generic;

namespace Aojx
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            double[] pos = { 1, 0 };
            List<double[]> posList = new List<double[]>();
            posList.Add(pos);

            for (int i = 1; i <= 999; i++)
            {
                double[] lastPos = posList.Last();
                double[] e = new double[2];

                double norm =
                    Math.Sqrt(
                        Math.Pow(lastPos[0], 2) + Math.Pow(lastPos[1], 2)
                    );

                e[0] = -lastPos[1] / norm;
                e[1] = lastPos[0] / norm;

                posList.Add(new double[]
                    {
                        lastPos[0] + e[0], lastPos[1] + e[1]
                    }
                );
            }
            
            string s;
            while ((s = Console.ReadLine()) != "-1")
            {
                int n = int.Parse(s) - 1;
                Console.WriteLine("{0}\n{1}", posList[n][0], posList[n][1]);
            }
        }
    }
}

Measured memory_bytes: 6020
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define PI 3.14159265358979323846264338327950288
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define testP	 cout << "------------------ test ------------------" << endl;	// 動作確認テスト
#define testX(x) cout << "testout : " << x << endl;	// テストアウト
typedef long long ll;
using namespace std;
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)

// ------------------ ベクター表示 ------------------ //
void printVec(vector<int>& vec) {
	cout << "";
	for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << " ";
	cout << endl;
}

// ------------------ ベクター合計 ------------------ //
int sumVec(vector<int> v) {
	int sum = 0;
	for (size_t i = 0; i < v.size(); i++) sum += v[i];
	return sum;
}

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

int main(void) {

	int X, N;
	int p[105];
	cin >> X >> N;

	int ans = X;
	bool ok[105] = { false };

	if (N == 0) {
		cout << ans << endl;
	}
	else {
		rep(i, N) {
			cin >> p[i];
			ok[p[i]] = true;
		}

		int n = 0;
		while (true) {
			if (ok[X - n] == false) {
				ans = X - n;
				break;
			}
			if (ok[X + n] == false) {
				ans = X + n;
				break;
			}
			n++;
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste

// #include "UnionFind.hpp"
// #include "power.hpp"


int add(int a, int b) {
    return (a + b) % MOD;
}

signed main() {
    int N;
    cin >> N;
    if (N == 3) {
        cout << 61 << endl;
        return 0;
    }
    vector<char> ACGT = {'A', 'C', 'G', 'T'};
    vector<vector<int>> dp(300, vector<int>(300, 0));
    for (int i = 0; i < 256; i++) {
        dp[4][i] = 1;
    }

    vector<int> ban = 
    {
        9, 36, 37, 38, 39, 73, 137, 201,
        9, 25, 41, 57,
        33, 37, 41, 45,
        33, 97, 132, 133, 134, 135, 161, 225,
        6, 24, 25, 26, 27, 70, 134, 198
    };

    for (int j = 0; j < ban.size(); j++) {
        dp[4][ban[j]] = 0;
    }

    for (int i = 5; i <= 100; i++) {
        for (int j = 0; j < 256; j++) {
            int temp = j / 4;
            bool check = true;
            if (check) dp[i][j] = (dp[i - 1][temp] + dp[i - 1][64 + temp] + dp[i - 1][128 + temp] + dp[i - 1][192 + temp]) % MOD;
            dp[i][j] %= MOD;
        }
        for (int j = 0; j < ban.size(); j++) {
            dp[i][ban[j]] = 0;
        }
    }


    int ans = 0;
    for (int i = 0; i < 256; i++) {
        ans = add(ans, dp[N][i]);
    }
    cout << ans << endl;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main(){
    int n;
    cin >>n;
    vector<string> s(n);
    map<string,int> mp;
    rep(i,n) {
        string s;
        cin>>s;
        mp[s]++;    
    }
    int mx=0;
    for(auto p :mp) mx= max(mx,p.second);
    for (auto p :mp){
        if (p.second ==mx){
            cout << p.first<<endl;
        }
    }
}


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

using namespace std;

int main(){
        int N, L;
        string s[101];
        cin>>N>>L;
        for(int i=0;i<N;i++){
                cin>>s[i];
        }
        sort(s, s+N);
        for(int i=0;i<N;i++){
                cout<<s[i];
        }
        cout<<endl;
        return 0;
}


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


public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String s = r.readLine();
		boolean c = false;
		boolean f = false;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == 'C') {
				c = true;
			} else if (s.charAt(i) == 'F' && c) {
				f = true;
			}
		}
		if (f == true) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 7892
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n = input()
    s = sum(int(c) for c in n)
    if s % 9 == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 9332
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int X, A;
	cin >> X >> A;
	if (X < A) {
		cout << 0 << endl;
	}
	else {
		cout << 10 << endl;
	}
}

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

int main()
{
  int64_t N, C, K, firstT = -1, waiting = 0, cnt = 0;
  cin >> N >> C >> K;
  vector<int64_t> T(N);
  for (int i = 0; i < N; i++)
  {
    cin >> T.at(i);
  }
  sort(T.begin(), T.end());
  for (int i = 0; i < N; i++)
  {
    if (firstT == -1)
    {
      firstT = T.at(i);
    }
    if (waiting + 1 == C)
    {
      if (T.at(i) <= firstT + K)
      {
        waiting = 0;
        cnt++;
        firstT = -1;
      }
      else
      {
        waiting = 1;
        cnt++;
        firstT = T.at(i);
      }
    }
    else if (T.at(i) > firstT + K)
    {
      waiting = 1;
      cnt++;
      firstT = T.at(i);
    }
    else
    {
      waiting++;
    }
  }
  if (waiting > 0)
    cnt++;
  cout << cnt << endl;
}


Measured memory_bytes: 1024
using System;

namespace abc148_c
{
    class Program
    {
        static void Main()
        {
            var tmp = Console.ReadLine().Split();
            var a = long.Parse(tmp[0]);
            var b = long.Parse(tmp[1]);
            var result =  a * b / Gcd(a, b);
            Console.WriteLine(result);
        }

        private static long Gcd(long m, long n)
        {
            while (true)
            {
                if (m < n)
                {
                    var m2 = m;
                    m = n;
                    n = m2;
                    continue;
                }

                if (n == 0) return m;
                var m1 = m;
                m = n;
                n = m1 % n;
            }
        }
    }
}


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

int main() {
 int n,sum=0,k=0,s=0,l=-1,r;cin>>n;int h[n+1],H[n+1];
  for(int i=0;i<n;i++){
    cin>>h[i];
    s+=h[i];
    H[i]=0;
  }
  h[n]=0;H[n]=0;
  
  /*for(int i=0;i<n+1;i++){
    cout<<H[i]<<endl<<h[i]<<endl;
  }*/
 int i;
 while(sum<s){
    for(i=0;i<n+1;i++){
      if(h[i]>H[i]){
        if(l<0){
          l=i;
        }
        H[i]++;//cout<<"i="<<i<<" "<<"h,H "<<h[i]<<H[i]<<endl;
      }
      else if(l>=0){
        r=i-1;break;
      }
    }
    k++;sum+=r-l+1;//cout<<"r="<<r<<" "<<"l="<<l<<endl;
      l=-1;//cout<<sum<<endl;
  }
cout<<k<<endl;
}




Measured memory_bytes: 256
//
//  main.cpp
//  AtCoderDPPractice: A-Frog 1
//
//  Created by Glen Cahilly on 9/1/20.
//  Copyright © 2020 Glen Cahilly. All rights reserved.
//

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



int func(int h[], int n) {
    int cost[n];
    cost[n-1]=0;
    cost[n-2]=abs(h[n-1]-h[n-2]);
    
    for (int k=n-3; k>=0; k--) {
        cost[k]=min(cost[k+1]+abs(h[k+1]-h[k]), cost[k+2]+abs(h[k+2]-h[k]));
    }
    /*
    for (int value : cost) {
        cout << value << " ";
    }
    */
    return cost[0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n; cin >> n; int h[n];
    for (int k=0; k<n; k++) {
        int in; cin >> in;
        h[k]=in;
    }
    cout << func(h, n);
}


Measured memory_bytes: 4388
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
	int a, b, res1, res2, res3;
	scanf("%d%d", &a, &b);
	res1 = a+b;
	res2 = a-b;
	res3 = a*b;
	int max;
	if (res1 > res2)max = res1;
	else max = res2;
	if (max < res3) max = res3;
	printf("%d\n", max);
    return 0;
}

Measured memory_bytes: 128
n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
ans=-10**9
for i in range(1,2**10):
  a=0
  m=[i%2,i//2%2,i//4%2,i//8%2,i//16%2,i//32%2,i//64%2,i//128%2,i//256%2,i//512%2]
  mm=[0 for i in range(n)]
  for i in range(10):
    for j in range(n):
      if m[i]==1 and f[j][i]==1:
        mm[j]+=1
  for i in range(n):
    a+=p[i][mm[i]]
  ans=max(ans,a)
print(ans)
  

Measured memory_bytes: 3064
/*input
1 + 2
*/

#include <iostream>

using namespace std;

int main()
{

	int A,B;
	string op;

	cin >> A >> op >> B;

	if(op=="+"){
		cout << (A+B) << endl;
	}else{
		cout << (A-B) << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	map<int,int> m;

	for (int i = 0;i < n;i++) {
		cin >> a[i];
		m[a[i]]++;
	}

	long long sum = 0;

	for (auto x : m) {
		if (m[x.first] > 1) {
			sum += (long long)m[x.first] * (long long)(m[x.first] - 1) / 2;
		}	
	}

	for (int i = 0;i < n;i++) {
		long long ans = sum;
		if (m[a[i]] > 1) {
			ans -= m[a[i]] - 1;
		}
		cout << ans << endl;
	}

	return 0;
}

//CCCCCCCCCCCCCC
//int main() {
//	double l;
//	cin >> l;
//
//	long double ans = pow(l / 3, 3);
//
//	printf("%.7llf", ans);
//
//	return 0;
//}

//BBBBBBBBBBBBBB
//int main() {
//	string s;
//	cin >> s;
//	int n = s.length();
//	string s1 = s.substr(0, (n - 1) / 2);
//	string _s = s;
//	string _s1 = s1;
//
//	reverse(_s.begin(), _s.end());
//	reverse(_s1.begin(), _s1.end());
//
//	if (s == _s && s1 == _s1) {
//		cout << "Yes" << endl;
//	}
//	else {
//		cout << "No" << endl;
//	}
//
//	return 0;
//}


//AAAAAAAAAAAAAAA
//int main() {
//	int n, m;
//	cin >> n >> m;
//	int ans = 0;
//	if (n >= 2)ans += n * (n - 1) / 2;
//	if (m >= 2)ans += m * (m - 1) / 2;
//	cout << ans << endl;
//
//	return 0;
//}

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

#define rep(i, n) for(int i = 0; i < n; i++)

typedef long long ll;
using namespace std;
int mod = 1000000007;

int solve(int dlim, int k, int rem, int n){
    if(k == 1){
        if(rem <= n && dlim < rem) return 1;
        else return 0;
    }
    int ret = 0;
    for(int i = dlim+1; i <= n; i++){
        ret += solve(i, k-1, rem-i, n);
    }
    return ret;
}

int main(void){
    int n, k, s;
    while(true){
        cin >> n >> k >> s;
        if(n == 0) break;
        cout << solve(0, k, s, n) << endl;
    }
    return 0;
}


Measured memory_bytes: 3056
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	if (k == 0)printf("%lld\n", (ll)(n)*(ll)(n));
	else
	{
		ll r = 0;
		for (int i = k + 1; i <= n; i++)r += (i - k)*((n + 1) / i) + max(0, (n + 1) % i - k);
		printf("%lld\n", r);
	}
}


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

int N;
pair<double, double> P[1010];
double R[1010];
double Dis[1010];
double INF = 1000000000000000000;
static double Root[1010][1010] = {};
bool Search[1010] = {};

void BFS() {
	Dis[0] = 0;
	for (int i = 1; i <= N + 1; i++) {
		Dis[i] = INF;
		Search[i] = true;
	}
	queue<int> Q;
	Q.push(0);
	while (Q.size()) {
		int q = Q.front();
		Q.pop();
		for (int i = 0; i <= N + 1; i++) {
			double qi_dis = Dis[q] + Root[q][i];
			if (qi_dis < Dis[i]) {
				Dis[i] = qi_dis;
				Q.push(i);
			}
		}
		Search[q] = false;
	}
}

int main() {
	double sx, sy, gx, gy;
	cin >> sx >> sy >> gx >> gy >> N;
	P[0] = { sx, sy }, R[0] = 0.0;
	for (int i = 1; i <= N; i++) {
		cin >> P[i].first >> P[i].second >> R[i];
	}
	P[N + 1] = { gx, gy }, R[N + 1] = 0.0;
	for (int i = 0; i <= N + 1; i++) {
		for (int j = i; j <= N + 1; j++) {
			double disx = P[i].first - P[j].first;
			double disy = P[i].second - P[j].second;
			Root[i][j] = Root[j][i] = max(0.0, sqrt(disx * disx + disy * disy) - R[i] - R[j]);
		}
	}
	BFS();
	printf("%.12f", Dis[N + 1]);
}

Measured memory_bytes: 9216
using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Text.RegularExpressions;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            if (r[0] <= r[1])
            {
                Console.WriteLine(r[0]);
            }
            else
            {
                Console.WriteLine(r[0] - 1);
            }
        }
    }
}

Measured memory_bytes: 13268
#include<iostream>
#include<algorithm>
#include<vector> 
using namespace std;
int main() {
    string S,A="No";
    cin >> S;
	std::vector<char> data;
	data.push_back(S[0]);
	data.push_back(S[1]);
	data.push_back(S[2]);
	data.push_back(S[3]);
	std::sort(data.begin(),data.end());
    if (data[0]==data[1] && data[2]==data[3] && data[0]!=data[2])
        A="Yes";
    cout << A << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define minz(p,q)((p)&&(p<q)?(p):(q))

int dp[100010];
int a[100010];

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=n;i>0;i--){
		if(dp[i]==0)dp[i]=1;
		dp[a[i]]=minz(dp[a[i]],dp[i]+1);
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(a[i]==0||dp[i]<=k)ans++;
	printf("%d\n",ans);
}



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

int main() {
	int a, b;
	cin >> a >> b;
	double ans = 0;
	for (int i = 1; i <= a; i++) {
		double tmp = 1.0 / a;
		int j = i;
		while (j < b) {
			j *= 2;
			tmp /= 2;
		}
		ans += tmp;
	}
	printf("%.15f\n", ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		String A = sc.next();
		String B = sc.next();
		String ans = "";
		if (A.length() == B.length()) {
			if (A.compareTo(B) == 0) {
				ans = "EQUAL";
			} else if (A.compareTo(B) > 0) {
				ans = "GREATER";
			} else {
				ans = "LESS";
			}
		} else if (A.length() > B.length()) {
			ans = "GREATER";
		} else {
			ans = "LESS";
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
# https://atcoder.jp/contests/abc150/tasks/abc150_d
# 半公倍数Xとは、X=a_k (p_k + 0.5) for any k を満たす数字である(p_kは負はない整数)
# 2を掛ければ、2X=a_k P_k where P_k=2p_k+1 となる。2Xは数列Aの公倍数と解釈できる。
# よってこの問題は、a_k (k=1...N)の公倍数2X は 0<=X<=Mを満たす範囲にいくつ存在するか？という風に読み替えられる。
# 数列Aの最小公倍数を2lcmと定義すると、答えの候補はlcmの倍数であるところまで絞り込めた。
# これで答えの候補を最小公倍数の半分、lcmの倍数であるところまで絞り込めた。

# ところでP_kは必ず奇数でなければ行けないのだから,Xとa_kは同じ回数2で割り切れなければ行けない。
# これを満たすXは,lcmがP_kと同じ回数2で割り切れる かつ lcmの奇数倍の数である。

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from fractions import gcd


def lcm(a, b):
    # 最小公倍数 #単位元は1
    g = gcd(a, b)
    return a // g * b


N, M = read_ints()
A = read_ints()
X = 1
for a in A:
    X = lcm(X, a)
X = X // 2

# すべてのa//2 はX(lcmと同じ回数2で割り切れないければ行けない)
lcm = X
n_div = 0
while lcm & 1 == 0:
    lcm //= 2
    n_div += 1

for a in A:
    if n_div != 0 and (a // 2) % (pow(2, n_div)):
        print(0)  # 割り切れなかった時点でそのような半公倍数は存在しない
        exit()


print((M // X + 1) // 2)  # 奇数倍のlcmの個数 つまりすべて-偶数の分


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

using namespace std;

const int N = 200000 + 7;

typedef long long ll;
int main() {
  string s;
  cin >> s;
  int x = 0, o = 0;
  for(char c: s) {
    if(c == 'x') ++x;
    else ++o;
  }
  if(x < 8) cout << "YES\n";
  else cout << "NO\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <map>
#include <numeric>
using namespace std;
using Int = long long;
#define REP(i, n) for(int i = 0; i < n; i++)
#define DUMP(range) do{for(auto& x:range){cout<<x<<' ';}cout<<endl;}while(0)
const Int MOD = 1000000007;
Int fact[200000], invfact[200000];
int power(int x, int y)
{
    if (y == 0) return 1;
    Int ans = power((Int)x * x % MOD, y / 2);
    if (y % 2) ans *= x;
    return ans % MOD;
}
int comb(int n, int r)
{
    return (Int)fact[n] * invfact[n - r] % MOD * invfact[r] % MOD;
}
Int f(int a, int b)
{
    return comb(a+b, a);
}
int main()
{
    int H, W, A, B; cin >> H >> W >> A >> B;
    fact[0] = invfact[0] = 1;
    for (int i = 1; i < 200000; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
        invfact[i] = power(fact[i], MOD - 2);
    }
    Int s = 0;
    for (int i = H - A; i < H; i++) {
        s += f(B-1, i) * f(W-1-B, H-1-i) % MOD;
    }
    s %= MOD;
    cout << (MOD + f(W-1, H-1) - s) % MOD << endl;
    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <cstdio>

bool solve(const int* values, int count, int top1, int top2)
{
	return (count == 0)
		|| (*values > top1 && solve(values + 1, count - 1, *values, top2))
		|| (*values > top2 && solve(values + 1, count - 1, top1, *values));
}


int main()
{
	int count = 0;
	std::cin >> count;

	for (int i = 0; i < count; ++i) {
		int values[10] = {};
		for (int j = 0; j < 10; ++j) {
			std::cin >> values[j];
		}
		if (solve(values, 10, 0, 0)) {
			std::cout << "YES\n";
		} else {
			std::cout << "NO\n";
		}
	}

	return 0;
}

Measured memory_bytes: 1120
# -*- coding: utf-8 -*-

N = int(input())

A = input().split()
B = input().split()
C = input().split()

score = 0
  
for a_str in A:
    a = int(a_str)
    score = score + int(B[a-1])

for i in range(len(A)-1):
    if int(A[i+1]) == int(A[i]) + 1:
        score = score + int(C[int(A[i])-1])
        continue
  
print(score)


Measured memory_bytes: 3060
n = int(input())

d = {"AC":0,"WA":0,"TLE":0,"RE":0}
for i in range(n):
  c = input()
  d[c]=d[c]+1 
print("AC x "+str(d["AC"]))
print("WA x "+str(d["WA"]))
print("TLE x "+str(d["TLE"]))
print("RE x "+str(d["RE"]), end='')


Measured memory_bytes: 9192
import java.util.Scanner;
public class Main
{
	public static void main(String args[])
	{
		Scanner inp = new Scanner(System.in);
		int a, b, c, count = 0;
		a = inp.nextInt();
		b = inp.nextInt();
		c = inp.nextInt();
		for(int i = a; i <= b; i++)
		{
			if(c%i==0)
				count++;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 26336
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    while(true){
        vector<bool> list(7368792,false);
        int m,n;
        cin >> m >> n;
        if(m==0)break;
        for(int i=m;n!=0;i++){
            if(!list[i]){
                n--;
                for(int j=1;j*i<list.size();j++){
                    list[j*i]=true;
                }
            }
        }
        int ans=0;
        bool flag=false;
        for(int i=m;i<list.size();i++){
            if(!list[i]){
                ans=i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4004
import collections
N = int(input())
a = list(map(int, input().split()))
A = set()
table = collections.defaultdict(int)

for i in range(1, N):
    table[a[i]] += 1

ans = [-1]*N
ans[0] = a[0]
for i in range(1, N):
    if (a[0] ^ a[i]) in table and table[a[0] ^ a[i]] >= 1:
        if a[0] == 0:
            if table[a[i]] == 1:
                continue
        ans[1] = (a[0] ^ a[i])
        ans[2] = a[i]
        table[ans[1]] -= 1
        table[ans[2]] -= 1
        break

if ans[1] == -1:
    print("No")
    exit(0)

for i in range(3, N):
    if (ans[i-1] ^ ans[i-2]) in table and table[ans[i-1] ^ ans[i-2]] >= 1 and table[ans[i-1] ^ ans[i-2]] >= 1:

        ans[i] = ans[i-1] ^ ans[i-2]
        table[ans[i]] -= 1
    else:
        print("No")
        exit(0)
print("Yes")


Measured memory_bytes: 14468
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;

int main() {
  int n;
  cin >> n;
  vector<string> v(n);
  for(int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  cout << v.size() << endl;
  return 0;
}

Measured memory_bytes: 9548
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    int m = n/2;

    vector<double> p(n);
    rep(i, n) {
        cin >> p[i];
    }

    vector<vector<double>> dp(n+1, vector<double>(n+1));  // dp[i+1][j] : i枚目(iは0-index)までに表がj枚出る確率

    dp[0][0] = 1.0;
    rep(i, n) {
        rep(j, n+1) {
            dp[i+1][j] = dp[i][j] * (1 - p[i]);
            if(j >= 1) {
                dp[i+1][j] += dp[i][j-1] * p[i];
            }
        }
    }

    double ans = 0;
    for(int j = m+1; j <= n; j++) {
        ans += dp[n][j];
    }

    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 70656
import java.util.Scanner;


public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String str = "";
		while(sc.hasNext()){
			str += sc.nextLine();
		}
		char c = 'a';
		int[] a = new int[26];
		for(int i = 0; i < 26; i++){
			for(char x: str.toCharArray()){
				if(x == (char)(c + i) || x == (char)(c + i - 32)){
					a[i]++;
				}
			}

		}
		for(int i = 0; i < 26; i++){
			System.out.println((char)(c + i) + " : " + a[i]);
		}
	}
}




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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 1e9

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

    ll N,K;
    cin >> N >> K;

    ll x[N];
    for (ll i = 0; i < N; i++) {
        cin >> x[i];
    }

    if (N == 1) {
        cout << x[0] << endl;
        exit(0);
    }

    ll ans = INF;
    for (ll i = 0; i < N-K+1; i++) {
        ll left = abs(x[i]) + abs(x[i+K-1] - x[i]);
        ll right = abs(x[i+K-1]) + abs(x[i] - x[i+K-1]);

        ans = min(ans, left);
        ans = min(ans, right);
    }
    cout << ans << endl;

}

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

// lib/square.hpp
#ifndef SQUARE_HPP
#define SQUARE_HPP

/*
usage:

tools::square(5) => 25
*/

namespace tools {
  template <typename T>
  constexpr T square(const T x) {
    return x * x;
  }
}

#endif

// lib/pow.hpp
#ifndef POW_H
#define POW_H


/*
usage:

tools::pow(2, 5) => 32
*/

namespace tools {
  template <typename T>
  constexpr T pow(const T base, const T exponent) {
    return exponent == 0
      ? 1
      : exponent % 2 == 0
        ? square(pow(base, exponent / 2))
        : pow(base, exponent - 1) * base;
  }
}

#endif

// main.cpp

int main() {
  std::int_fast64_t n, m;
  std::cin >> n >> m;
  std::cout << (1900 * m + 100 * (n - m)) * tools::pow<std::int_fast64_t>(2, m) << std::endl;
  return 0;
}

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

#[fastout]
fn main() {
    input! {
        n: usize,
        ax: [i64; n]
    }

    let mut dp = vec![vec![0; n+1]; n+1];

    let mut axi: Vec<_> = ax.iter().enumerate().collect();
    axi.sort_by_key(|a| a.1);
    axi.reverse();

    let mut ans = 0;
    for i in 1..=n {
        for j in 0..=i {
            let (index, ai) = axi[i-1];
            if j > 0 {
                dp[i][j] = 
                    max(
                        dp[i][j],
                        dp[i-1][j-1] + ai * (index as i64 - (j-1) as i64).abs()
                    );
            }
            let k = i - j;
            if k > 0 {
                dp[i][j] = 
                    max(
                        dp[i][j],
                        dp[i-1][j] + ai * (index as i64 - (n-k) as i64).abs()
                    );
            }
            ans = max(ans, dp[i][j]);
        }
    }

    println!("{}", ans);
}

Measured memory_bytes: 33436
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };


// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */



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

    int N; cin >> N;
    vector<ll> T(N), A(N);
    rep(i, N) cin >> T[i] >> A[i];

    ll t = T[0], a = A[0];
    repr(i, 1, N){
        ll k = max((a+A[i]-1)/A[i], (t+T[i]-1)/T[i]);
        a = k*A[i], t = k*T[i];
    }
    cout << a+t << endl;
    
    return 0;
}

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

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]){
	long long X;
	cin >> X;
	long long ans=0;
	long long s = 100.0;
	double r = 1.01;
	while(s < X){
		s = (long long)s*r;
		ans++;
	}
	cout << ans << endl ;
	return 0;
}


Measured memory_bytes: 3680
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
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;
}
///////////////////////////////////////////////////////////////

vector<string> S;

int N,k;

int dfs (char op,int w) {
    int y;
    if (op == '+') {
        y = 0;
        while (k < N && S[k].size() == w+1) {
            if (S[k][w] == '+' || S[k][w] == '*') {
                y += dfs(S[k++][w],w+1);
            } else {
                y += S[k][w] - '0';
                k++;
            }
        }
    } else {
        y = 1;
        while (k < N && S[k].size() == w+1) {
            if (S[k][w] == '+' || S[k][w] == '*') {
                y *= dfs(S[k++][w],w+1);
            } else {
                y *= S[k][w] - '0';
                k++;
            }
        }
    }
    return y;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    while (true) {
        cin >> N;
        if (N == 0) break;
        S.resize(N);
        rep(i,N) cin >> S[i];
        k = 0;
        cout << dfs('+',0) << endl;
    }
}


Measured memory_bytes: 3232
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <queue>
#include <math.h>
#include <bitset>
#define INF 100000000000
#define N 100001
#define ll long long
using namespace std;

int main(){
    int h,w;
    cin>>h>>w;
    
    int data[10][10];
    for (int i=0; i<10; i++){
        for (int j=0; j<10; j++){
            cin>>data[i][j];
        }
    }
    
    bool point=true;
    while(point){
        point=false;
        for (int i=0; i<10; i++){
            for (int j=0; j<10; j++){
                for (int k=0; k<10; k++){
                    if (data[i][j]>data[i][k]+data[k][j]) point=true;
                    data[i][j]=min(data[i][j],data[i][k]+data[k][j]);
                }
            }
        }
    }
    
    ll sum=0;
    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            int p;
            cin>>p;
            
            if (p==1 || p==-1) continue;
            
            sum+=data[p][1];
        }
    }
    
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  int N, K;
  while(cin >> N >> K){
    vector<LLI> A(N); cin >> A;

    REP(i,N) A[i] -= 1;

    vector<LLI> S(N+1);
    REP(i,N) S[i+1] = (S[i] + A[i]) % K;

    map<LLI, LLI> m;

    LLI ans = 0;

    REPE(i,N){
      if(i-K >= 0) m[S[i-K]] -= 1;

      ans += m[S[i]];
      
      m[S[i]] += 1;
    }

    cout << ans << endl;
  }

  return 0;
}


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

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 2e6 + 5;

std::string str[MAXN];
int n,sm;
int lft[MAXN],rst[MAXN];
std::vector<P> S1,S2;
bool cmp1(P a,P b){
	return a.se < b.se;
}

bool cmp2(P a,P b){
	return a.fi > b.fi;
}

int main(){
	std::cin >> n;
	FOR(i,1,n) std::cin >> str[i];
	FOR(i,1,n){
		int len = str[i].length();
		int t1=0,now = 0;
		FOR(j,0,len-1){
			if(str[i][j] == '(') now++,sm++;
			else{
				now--;if(now < 0) t1++,now = 0;
				--sm;
			}
		}
		lft[i] = now;rst[i] = t1;
	}
	if(sm != 0){
		std::cout << "No\n";return 0;
	}
	sm = 0;
	FOR(i,1,n) if(rst[i] == 0) sm += lft[i];
	FOR(i,1,n) if(rst[i] && lft[i]){
		if(lft[i]-rst[i] >= 0) S1.pb(MP(lft[i],rst[i]));
		else S2.pb(MP(lft[i],rst[i]));
	}
	std::sort(all(S1),cmp1);
	std::sort(all(S2),cmp2);
	for(auto x:S1){
		sm -= x.se;
		if(sm < 0){
			std::cout << "No\n";
			return 0;
		}
		sm += x.fi;
	}
	for(auto x:S2){
		sm -= x.se;
		if(sm < 0){
			std::cout << "No\n";
			return 0;
		}
		sm += x.fi;
	}
	std::cout << "Yes\n";
	return 0;
}

Measured memory_bytes: 73956