akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main () {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int l = a+b, r = c+d;
    if (l > r) puts("Left");
    else if (l == r) puts("Balanced");
    else puts("Right");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(j, n) for (int j = 0; j < (n); j++)

typedef long long ll;

int main(){
int n,ans;
cin>>n;
vector<int>a(n);
rep(i,n)cin>>a[i];
rep(i,n){
  while(a[i]%2==0){
    a[i]/=2;
    ans++;
  }
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/pb_ds/detail/standard_policies.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define endl "\n"
    #define fi first
    #define se second
    #define pb push_back
    #define ll long long
    #define ld long double
    #define pii pair<ll,ll>
    #define read(t) ll t;cin>>t;
    #define all(x) x.begin(),x.end()
    #define f(a,b,c) for(ll a=b;a<c;a++)
    #define For(i,n) for(ll i=0;i<n;i++)
    #define what(x) cerr << #x << " is " << x << endl;
    #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) ;
    typedef tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> ordered_mset;
    typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
/*.....................................................................................................................*/

    const ll mod=(ll)1e9+7;
    ll add(ll x,ll y) {return (x+y)%mod;}
    ll mult(ll x, ll y){return ((x%mod )* (y%mod)) % mod;}
    long long binpow(long long x, long long p) 
    {
        if (p == 0) {return 1;}
    	if (p == 2 || (p & 1)) {return mult(x, binpow(x, p - 1));}
    	return binpow(binpow(x, p / 2), 2);
    }
    ll modinv(ll a) {return binpow(a,mod-2);}
    double pi=3.141592653589793238462641;
    ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    const ll man=(ll)1e5+5;
/*........................................................................................................................*/


signed main()
{
    fast;
    ll n;
    cin>>n;
    ll x=0;
    while(n)
    {
        n/=2;
        x++;
    }
    cout<<(1ll<<(x))-1<<endl;
}

Measured memory_bytes: 3656
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	char lc1Buf[1024];

	// 幅・高さ・頂点 - 取得
	int liW, liH, liX, liY;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d%d", &liW, &liH, &liX, &liY);

	// 面積/2 - 取得
	double ldArea = (double)liW * (double)liH / 2.0;

	// 中心判定
	int liCenter = 0;
	if (liX * 2 == liW) {
		if (liY * 2 == liH) {
			liCenter = 1;
		}
	}

	// 出力
	sprintf(lc1Buf, "%.10lf %d\n", ldArea, liCenter);
	fOut(lc1Buf);

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



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

int main() {
  int N,a,b,c,d;
  cin >> N;
  a = N / 1000;
  b = (N - a*1000) / 100;
  c = (N- a*1000 - b*100) / 10;
  d = N - a*1000 - b*100 - c*10;
  if( ((a == b) &&(b== c)) ||(( b == c)&&(c == d))){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let x: i64 = read();

    if x < 1200 {
        println!("ABC");
    } else {
        println!("ARC");
    }
}


Measured memory_bytes: 4352
Module Module1

    Sub Main()

        Dim InTbl As String = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
        Dim tmp As String() = Split(intbl, ",")
        Dim K As Integer = CInt(Console.ReadLine())

        Console.WriteLine(tmp(K - 1).Trim)

    End Sub

End Module


Measured memory_bytes: 13524
#include<stdio.h>
int main(void)
{
  int a,t=0;
  scanf("%d",&a);
  for(int i=1;i<=9;i++){
    for(int j=1;j<=9;j++){
      if(a == (i*j))
        t = 1;
    }
  }
  if(t == 1) printf("Yes");
  else printf("No");
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iterator>
#include<math.h>
using namespace std;
int main()
{
        int n;
     cin>>n;
     if(n>=30)
        cout<<"Yes"<<endl;
     else
        cout<<"No"<<endl;


}


Measured memory_bytes: 3672
n,m,q=map(int,input().split())
constraints = [tuple(map(int,input().split())) for _ in range(q)]

def eval(a):
  score = 0
  for c in constraints:
    if a[c[1] - 1] - a[c[0] - 1] == c[2]:
      score += c[3]
  return score

# a: 長さNの配列, i番目以前の要素は値が決まっていて、それ以降は未定
def dfs(a, i):
  if i == n:
    return eval(a)
  score = 0
  for x in range(a[i - 1] if 0 < i else 1, m + 1):
    a[i] = x
    score = max(score, dfs(a, i + 1))
  return score

print(dfs([None] * n, 0))


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

using namespace std;


void Solve();

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

void Solve(){
  int n;
  	scanf("%d",&n);
  vector<int> A(n);
  for(int i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  
  vector<int> B(n);
  for(int i=n;i>0;i--){
    for(int j=i;j>0;j--){
      if(A[j-1]==j){
        B[i-1]=j;
        A.erase(A.begin()+j-1);
        break;
      }
    }
  }

    
  if(B[0]==0){
    printf("%d\n",-1);
    return;
  }
  
  for(int i=0;i<n;i++){
    printf("%d\n",B[i]);
  }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll K; cin >> K;
    ll num = 0;
    rep(i, 1000000){
        num = (num * 10 + 7) % K;
        if (num == 0){cout << i + 1 << endl; exit(0);}
    }
    cout << -1 << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n = 1e6;
int n, m,q;
string a;
int main(){
  cin >> n >> q >> a;
  vector<int> l(q), r(q);
  for(int i=0 ; i<q ; i++){
    cin >> l[i] >> r[i];
    l[i]--; r[i]--;
  }
  vector<int> right(n+1), left(n+1);
  for(int i=1 ; i<n ; i++){
    if(a[i-1]=='A'&&a[i]=='C'){
      left[i] = left[i-1] + 1;
    }else{
      left[i] = left[i-1];
    }
  }
  for(int i=0 ; i<q ; i++){
      cout << left[r[i]] - left[l[i]] << endl;
  }
  return 0;
}


Measured memory_bytes: 2688
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main()
{
	ios::sync_with_stdio(false);
	int n; cin >> n;
	ld result = 0;
	for (int i = 0; i < n; i++)
	{
		ld a; cin >> a;
		result += 1.0L / a;
	}
	result = 1.0L / result;
	cout << setprecision(10) << fixed << result << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main(){
  int n;
  cin >> n;
  vector<int> buttons(n);
  vector<int> flags(n, 0);
  rep(i, n){
    int num;
    cin >> num;
    buttons[i] = num-1;
  }
  int cnt = 0;
  int now = 0;
  while(flags[now] == 0){
    if(now == 1){
      cout << cnt << endl;
      return 0;
    }
    flags[now] = 1;
    cnt++;
    now = buttons[now];
  }
  cout << -1 << endl;
  return 0;
}
    
    
    
  

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		if(i%3==0||i%5==0)
			continue;
		sum+=i;	
	}
	cout<<sum;
	return 0;
}


Measured memory_bytes: 3556
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
#define lint long long int
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
*/

int main() {
	int N;
	cin >> N;
	double a = N;
	N = N / 2 + bool(N % 2);
	double b = N;
	cout << b / a << endl;
}


Measured memory_bytes: 256
/*
Educational DP Contest - F - LCS
https://atcoder.jp/contests/dp/tasks/dp_f
*/

#include <bits/stdc++.h>
using namespace std; 
#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)
typedef long long ll; 
 
int main()  
{ 
    FAST_INP;
    string s,t;
    cin >> s >> t;
	vector<vector<int>> dp(3005,vector<int>(3005,0));
    int m=s.size(), n=t.size();
    for(int i=0;i<m;i++){
    	for(int j=0;j<n;j++){
    		if(s[i]==t[j]) dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
    		dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j]);
    		dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1]);
		}
	}
	string ans="";
	int i=m, j=n;
	while(i&&j){
		if(dp[i][j]==dp[i-1][j]) i--;
		else if(dp[i][j]==dp[i][j-1]) j--;
		else {
			ans=s[i-1]+ans;
			i--, j--;	
		}
	}
	cout << ans << endl;
    return 0;
} 


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

int main(){
 int h,w;
 while(1){
  cin >> h >> w ;
  if(h==0&&w==0)break;
  for(int i=0;i<h;i++){
   for(int j=0;j<w;j++){
    if((i+j)%2==0)cout << "#" ;
    else cout << "." ;
   }
   cout << endl;
  }
  cout << endl;
 }

 return 0;
}

Measured memory_bytes: 3076
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans;
int A,P;

void solve(){
    cout << (3*A + P)/2 << endl;
}

int main(){
    cin >> A >> P;

    solve();
}


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

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) {
        int x=i;
        if(i%3==0) {
            cout<<" "<<i;
        } else {
            while(x) {
                if(x%10==3) {
                    cout<<" "<<i;
                    break;
                }
                x/=10;
            }
        }
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+1;
pair<int,int> s[maxn];
int n, suf[maxn];
int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0;i < n;++i)cin >> s[i].first >> s[i].second, ++s[i].second;
    sort(s, s+n);
    int l = 0, r = 1000000001, w = 0;
    for(int i = 0;i < n;++i){
        l = max(l, s[i].first);
        r = min(r, s[i].second);
        w = max(w, s[i].second-s[i].first);
    }
    int res = w+max(0, r-l);
    suf[n-1] = s[n-1].second;
    for(int i = n-2;i > -1;--i)suf[i] = min(suf[i+1], s[i].second);
    for(int i = n-2;i > -1;--i)res = max(res, max(0, r-s[i].first) + max(0, suf[i+1]-l));
    cout << res << '\n';
}


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

int main() {

    int w, h, x, y, r;

    std::cin >> w >> h >> x >> y >> r;

    x >= r && x <= w - r && y >= r && y <= h - r
        ? std::cout << "Yes" << std::endl
        : std::cout <<  "No" << std::endl ;

    return 0;
}



Measured memory_bytes: 3104
#include <iostream>

using namespace std;
int main()
{
    int n;

    cin >> n;
    int p[n];
    int i;

    for ( i = 0; i < n; i ++ ) cin >> p[i];

//    for ( i = 0; i < n; i ++ ) cout << p[i] << " ";
//    cout << endl;

    int count = 0;
    for( i = 0; i < n-2; i ++ ) {
        int a, b, c;
        a = p[i];
        b = p[i+1];
        c = p[i+2];
//        cout << a << " " << b << " " << c << endl;
        if ( (a < b && b < c) || ( c < b && b < a ) ) count ++;
        if (  a == c && b > a ) count ++;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<queue>
#include<tuple>
#include<string>
#include<iomanip>
#include<cmath>

using namespace std;

int N, M;
vector<vector<int>> E;
int cost[200000 + 10];
int ans[200000 + 10];

int main() {

	cin >> N >> M;
	E.resize(N);

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		E[a].push_back(b), E[b].push_back(a);
	}
	
	for (int i = 0; i < N; i++)cost[i] = 1145141919;
	cost[0] = 0;
	queue<int> q;
	q.push(0);
	while (q.size()) {
		int npos = q.front(); q.pop();
		for (int i = 0; i < E[npos].size(); i++) {
			int nxt = E[npos][i];
			if (cost[nxt] > cost[npos] + 1) {
				cost[nxt] = cost[npos] + 1;
				ans[nxt] = npos + 1;
				q.push(nxt);
			}
		}
	}

	cout << "Yes\n";
	for (int i = 1; i < N; i++)cout << ans[i] << "\n";
	return 0;
}

Measured memory_bytes: 10744
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL<<60;
typedef pair<ll, ll> P;

int main() {
    cin>>N>>M;
    ll sum = 0;
    rep(i,M) {
        cin>>A;
        sum += A;
    }
    cout<<max(-1LL, N - sum)<<endl;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll n,m,ans=0;
void Main(){
    cin>>n>>m;
    vector<ll> a(n),dp(n+1);
    dp[0]=0;
    For(i,0,n)cin>>a.at(i);
    sort(ALL(a));
    For(i,0,n)dp[i+1]=dp[i]+a[i];
    ll ooi=a[0]*2-1,sukunai=a[n-1]*2+1;
    while(sukunai>ooi+1){
        ll center=(sukunai+ooi)/2;
        //cout<<"center = "<<center;
        ll cnt=0;
        For(i,0,n){
            auto itr=upper_bound(ALL(a),center-a[i]);
            ll num=a.end()-itr;
            //cout<<" "<<num;
            cnt+=num;
        }
        //cout<<endl;
        if(cnt>m) ooi=center;
        else sukunai=center;
    }
    ll C=0;
    For(i,0,n){
        auto itr=upper_bound(ALL(a),sukunai-a[i]);
        ll num=a.end()-itr;
        C+=num;
        //cout<<num<<endl;
        ans+=(num*a[i]+dp[n]-dp[n-num]);
    }
    ans+=(m-C)*sukunai;
    cout<<ans<<endl;
}
int main(){
    Main();
    return 0;
}


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

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T') continue;
        int cnt = 1;
        for (int j = i + 1; j < s.size(); ++j) {
            if (s[j] == 'A' || s[j] == 'C' || s[j] == 'G' || s[j] == 'T') cnt++;
            else break;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
#N, M = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]
#S = input()
#S = [input() for _ in range(N)]

if N == 1:
    print(0)
    exit()
    
answer = 0
max_a = A[0]

for a in A[1:]:
    max_a = max(max_a, a)
    answer += max_a - a

print(answer)

Measured memory_bytes: 94332
#3問目
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

dictionary = {}
count = 0
N = int(input())
for i in range(N):
    s = input()
    s = ''.join(sorted(s))
    if(s in dictionary):
        dictionary[s] += 1
    else:
        dictionary[s] = 1

for i in dictionary.values():
    if(i >= 2):
        count += combinations_count(i, 2)

print(count)

Measured memory_bytes: 17932
#include <stdio.h>
#include <iostream>
#define rep(i,n) for(int i = 2; i <= (n); ++i)
using namespace std;
int n;
bool p[1000000];
int main() {
	rep(i,1000) {
		int k = i;
		if(!p[k]) {
			while(k < 1000000) {
				k += i;
				p[k] = true;
			}
		}
	}
	while(scanf("%d\n", &n) != EOF) {
		int count = 0;
		rep(i,n) {
			if(!p[i]) count++;
		}
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 2188
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
int main()
{
	int N;
	std::cin >> N;
	std::string c;
	std::cin >> c;
	int count = 0;
	int right = N - 1;
	for (int i = 0; i < N; ++i) {
		if (c[i] == 'W') {
			for (; right >= i + 1; --right) {
				if (c[right] == 'R') {
					c[i] = 'R';
					c[right] = 'W';
					--right;
					++count;
					break;
				}
			}
		}
	}
	std::cout << count << std::endl;


	/*
	int64_t K;
	std::cin >> K;
	if ((K % 2)&&(K % 5)) {
		int col = 1;
		int64_t val = 7;
		while (true) {
			if((val%K)==0){
				break;
			}
			else {
				++col;
				val *= 10;
				val += 7;
			}
		}
		std::cout << col << std::endl;
	}
	else {
		std::cout << -1 << std::endl;
	}
	*/
	return 0;
}

Measured memory_bytes: 3648
#include <cmath>
#include <iostream>
#include <string>

using namespace std;

int main() {
	int N,sum,x;
	cin >> N;
	if (N % 2)
		cout << N / 2 * (N / 2 + 1) << endl;
	else
		cout << N / 2 * N / 2 << endl;
}

Measured memory_bytes: 256
n = gets.to_i
x, y = [], []
n.times do
  xn,yn = gets.split(' ').map(&:to_i)
  x << xn
  y << yn
end
sum = 0
(0...n-1).each do |i|
  (i + 1...n).each do |j|
    _x = (x[j] - x[i])**2
    _y = (y[j] - y[i])**2
    sum += Math.sqrt(_x+_y)
  end
end
puts 2*sum/n

Measured memory_bytes: 3836
object Main extends App {
  val Seq(n, m) = readLine.split(' ').map(_.toInt).toList

  val mtxa = Array.ofDim[Int](n, m)

  for (i <- 0 until n) {
    mtxa(i) = readLine.split(' ').map(_.toInt)
  }

  val vecb = for {
    j <- 0 until m
    bj = readLine.toInt
  } yield bj

  mtxa.foreach(veca => println(veca.zip(vecb).map(t=>t._1 * t._2).sum))
}



Measured memory_bytes: 48180
#pragma region template 1.2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a) \
    REP(i, (a).size()) { cout << (a[i]) << (i == (a).size() - 1 ? "\n" : " "); }
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

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

    ll ans = 0;
    REP1(i, N)
    {
        if (i % 3 != 0 and i % 5 != 0)
        {
            ans += i;
        }
    }
    OUT(ans);
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,N) repi(i,0,(N))
#define repi(i,a,b) for (int i = (a); i < (b); ++ i)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)

#define all(v) (v).begin(), (v).end()
#define ios() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define t
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int,int>;
constexpr long long MOD = 1e9 + 7;
constexpr long long INF = 1LL << 60;
// UP = 0;RIGHT = 1; DOWN = 2; LEFT =3;
const int dx[] = {0, 1, 0, -1},
          dy[] = {1, 0, -1, 0};
template<class T = int> bool chmin(T& a, T b) { bool f = a > b; a = f ? b : a; return f;}
template<class T = int> bool chmax(T& a, T b) { bool f = a < b; a = f ? b : a; return f;}

template<class T> istream& operator>>(istream &is,vector<T> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> ostream& operator<<(ostream &os, const vector<T> &st){
  for(size_t i=0;i<st.size();++i){
    if(i==st.size()-1) os << st[i];
    else os << st[i] << " ";
  }
  return os;
}
template<class T> istream& operator>>(istream &is,vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> ostream& operator<<(ostream &os, const vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i){
    os << st[i];
    if(i!=st.size()-1) os << endl;
  }
  return os;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p){
  return s << "(" << p.first << ", " << p.second << ")";
}


signed main() { 
  ios();
  int N;
  cin >> N;
  vi v(N);
  cin >> v;
  double tmp = 0;
  for (int i = 0; i < N; i ++) {
    tmp += 1.0 / v[i];
  }
  cout << fixed << setprecision(7);
  cout << 1.0 / tmp << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		String result = "No";
		if(n%500<=a) result = "Yes";
		System.out.println(result);
	}

}


Measured memory_bytes: 23252
N = input()
N = int(N)
R_list = [[0]*3 for i in range(N)]
for h in range(N):
    S, P = input().split()
    P = int(P)
    R_list[h][0] = S
    R_list[h][1] = P
    R_list[h][2] = h + 1

R_list = sorted(R_list, key=lambda x:(x[0],-x[1]))
for k in range(N):
    print(R_list[k][2])


Measured memory_bytes: 3060
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    l=[]
    for i in range(M):
        B,C=map(int,input().split())
        l.append((C,B))
    l.sort(reverse=True)
    c=0
    ans=0
    for i in range(M):
        c+=l[i][1]
        if c>N:
            z=bisect_left(A,l[i][0])
            ans+=max(0,z-c+l[i][1])*l[i][0]
            c=z
            break
        else:
            if A[c-1] >= l[i][0]:
                z=bisect_left(A,l[i][0])
                ans+=max(0,z-c+l[i][1])*l[i][0]
                c=z
                break
            else:
                ans+=l[i][0]*l[i][1]
    ans+=sum(A[c:])
    print(ans)
        

if __name__ == '__main__':
    main()


Measured memory_bytes: 62704
S = int(input())
MOD = 10**9 + 7

dp = [0] * (S + 1)
dp[0] = 1

for i in range(S):
    for j in range(3, S + 1):
        if i + j <= S:
            dp[i + j] = (dp[i + j] + dp[i]) % MOD
print(dp[S])


Measured memory_bytes: 9108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
ll dp[101][100007];
ll n,W;
ll w[101],v[101];
ll knapsack(ll pos,ll sum)
{
    if(pos==n){
        if(sum)
            return INF;
        return 0;
    }
    if(dp[pos][sum]!=-1){
        return dp[pos][sum];
    }
    dp[pos][sum]=INF;
    if(sum-v[pos]>=0){
        dp[pos][sum]=min(dp[pos][sum],w[pos]+knapsack(pos+1,sum-v[pos]));
    }
    dp[pos][sum]=min(dp[pos][sum],knapsack(pos+1,sum));
    return dp[pos][sum];
}
int main()
{
	FastIO;
	reset(dp);
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    for(ll i=100000;i>=0;i--){
       ll  ans=knapsack(0,i);
        if(ans<=W){
            cout<<i<<endl;
            break;
        }
    }
	return 0;
}




Measured memory_bytes: 79232
#include <stdio.h>
#include <algorithm>
#include <cfloat>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
typedef long long int          ll;
typedef unsigned long long int ull;
#define BIG_SIZE 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define SIZE 100000

vector<int> G[SIZE];
int         N;
bool        visited[SIZE];
int         visited_order[SIZE], parent[SIZE], lowest[SIZE], number;

void dfs(int current_node, int pre_node) {
    visited_order[current_node] = lowest[current_node] = number;
    number++;

    visited[current_node] = true;

    int next;

    for (int i = 0; i < G[current_node].size(); i++) {
        next = G[current_node][i];
        if (!visited[next]) {
            parent[next] = current_node;
            dfs(next, current_node);
            lowest[current_node] = min(lowest[current_node], lowest[next]);
        } else if (visited[next] == true && next != pre_node) {
            lowest[current_node] =
                min(lowest[current_node], visited_order[next]);
        }
    }
}

void art_points() {
    for (int i = 0; i < N; i++) visited[i] = false;

    number = 1;
    dfs(0, -1);

    int tmp_parent, root_num = 0;

    vector<int> V;

    for (int i = 1; i < N; i++) {
        tmp_parent = parent[i];
        if (tmp_parent == 0) {
            root_num++;
        } else if (visited_order[tmp_parent] <= lowest[i]) {
            V.push_back(tmp_parent);
        }
    }
    if (root_num >= 2) {
        V.push_back(0);
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());

    for (int i = 0; i < V.size(); i++) {
        printf("%d\n", V[i]);
    }
}

int main() {
    int E;

    scanf("%d %d", &N, &E);

    int from, to;

    for (int i = 0; i < E; i++) {
        scanf("%d %d", &from, &to);
        G[from].push_back(to);
        G[to].push_back(from);
    }

    art_points();

    return 0;
}



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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n, k;
	cin>>n>>k;
	string s;
	cin>>s;
	char pc = '1';
	vector<int> v({0});
	for(int i = 0; i < n; i++){
		if(s[i] == pc)v.back()++;
		else v.push_back(1);
		pc = s[i];
	}
	if(v.size()%2 == 0)v.push_back(0);
	k = 2*k + 1; int len = v.size();
	if(len <= k){
		cout<<n<<endl;
		exit(0);
	}
	int sum = accumulate(v.begin(), v.begin() + k, 0);
	int ans = sum;
	for(int i = k + 1; i < len; i += 2){
		sum += v[i] + v[i - 1] - v[i - k] - v[i - k - 1];
		ans = max(ans, sum);
	}
	cout<<ans<<endl;

	return 0;
}

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

int main() {
	int N, M, S[2000], T[2000], MOD = 1000000007;
	static long long DP[2010][2010] = {};
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> S[i];
	for (int i = 0; i < M; i++) cin >> T[i];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (S[i] == T[j]) {
				DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] + 1;
			}
			else {
				DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j];
			}
			DP[i + 1][j + 1] = (DP[i + 1][j + 1] + MOD) % MOD;
		}
	}
	cout << (DP[N][M] + 1 + MOD) % MOD;
}

Measured memory_bytes: 31616
#pragma GCC optimize("Ofast")
#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;
using ll = long long;
using u64 = uint_fast64_t;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln = '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

using Tu = tuple<int, int, int>; 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);   
    int N; cin >> N;
    //N = 160000;
    vector<string> S(N);
    rep(i,N) cin >> S[i];

    map<Tu, ll> dic;
    ll ans = 0;
    rep(i,N) {
        ll A = 0;
        int K = S[i].size();
        rep(j,K) {
            if (S[i][j]=='.') continue;
            A *= 10;
            A += S[i][j] - '0';
        }
        int a = 0, b = 0, c = 0;
        while (A % 2 == 0) {
            A /= 2;
            a++;
        }
        while (A % 5 == 0) {
            A /= 5;
            b++;
        }
        bool ok = false;
        rep(j,K) {
            if (S[i][j]=='.') ok = true;
            else if (ok) c++;
        }
        for (auto j : dic) {
            auto[d,e,f] = j.first;
            ll v = min(a+d,b+e);
            if (v >= c+f) ans += j.second;
        }
        int z = min({a,b,c});
        a -= z;
        b -= z;
        c -= z;
        dic[Tu(a,b,c)]++;
        // clock_t end = clock();
        // double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
        // cout << i << endl;
    }

    cout << ans << ln;
}


Measured memory_bytes: 9372
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int k = int.Parse(input[1]);
        string[] ar = Console.ReadLine().Split(' ');
        int[] a = new int[n + 1];
        int min = 100001;
        int pos = 100001;
        int count = 0;

        for (int i = 1; i <= n; i++)
        {
            a[i] = int.Parse(ar[i - 1]);
            if(min > a[i])
            {
                min = a[i];
                pos = i;
            }

        }
        n -= k;
        count++;

        while(n > 0)
        {
            n -= (k - 1);
            count++;
        }
        Console.WriteLine(count);
    }
}


Measured memory_bytes: 16864
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

// const int dx[8] = {1, 1, 0,-1,-1,-1, 0, 1};
// const int dy[8] = {0, 1, 1, 1, 0,-1,-1,-1};

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int ctoi(char c){return c-'0';}

// TODO: write
int main() {
  int n;cin>>n;
  print(n/2 + n %2);
  return 0;
}



Measured memory_bytes: 256
use std::io;
use std::str::FromStr;

fn read_line<T: FromStr>() -> T {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    let inp_str = line.trim();
    inp_str.parse::<T>().ok().unwrap()
 }

fn main() {
    let n = read_line::<i64>();
    let max = (10 as i64).pow(9)+7;
    let mut power = 1;
    for i in 1..(n+1) {
        power *= i;
        power %= max;
    }
    println!("{}", power );
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

template <class F>
int64_t lower_bound(int64_t i0, int64_t i1, F f) {
    while (i0 < i1) {
        int64_t i = (i0 + i1) / 2;
        if (f(i)) i1 = i; else i0 = i + 1;
    }
    return i0;
}

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

    int n, k;
    cin >> n >> k;

    vector<int64_t> w(n);
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> d[i];
    }

    int64_t x = lower_bound(0, (int64_t)2e+18, [&](int64_t x) {
        int64_t s = 0;
        for (int i = 0; i < n; i++) {
            if (x < w[i]) continue;
            s += (x - w[i]) / d[i] + 1;
        }
        return s >= k;
    });
    cout << x << endl;

    return 0;
}

Measured memory_bytes: 1408
n, p = map(int, input().split())
a = list(map(int, input().split()))

length = len(a)
even = len([i for i in a if i % 2 == 0])
odd = len([i for i in a if i % 2 == 1])

if length == even and p == 1:
    print(0)
elif length == even:
    print(2 ** n)
else:
    print(2 ** n // 2)

Measured memory_bytes: 61932
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = [ni() for _ in range(n)]

    a.sort()

    ans1 = []
    ans2 = []
    if not n % 2:
        small = a[:n // 2]
        large = a[n // 2:]
        for i in range(n // 2):
            ans2.append(large[i])
            ans2.append(small[i])

        tmp_ans = 0
        for i in range(1, n):
            tmp_ans += abs(ans2[i - 1] - ans2[i])

        print(tmp_ans)

    else:
        small1 = a[:n // 2 + 1]
        large1 = a[n // 2 + 1:]
        small1.insert(0, small1[-1])
        del small1[-1]
        for i in range(n // 2):
            ans1.append(small1[i])
            ans1.append(large1[i])
        ans1.append(small1[n // 2])

        small2 = a[:n // 2]
        large2 = a[n // 2:]
        large2.append(large2[0])
        del large2[0]
        for i in range(n // 2):
            ans2.append(large2[i])
            ans2.append(small2[i])
        ans2.append(large2[n // 2])

        tmp_ans1 = 0
        tmp_ans2 = 0
        for i in range(1, n):
            tmp_ans1 += abs(ans1[i - 1] - ans1[i])
            tmp_ans2 += abs(ans2[i - 1] - ans2[i])

        print(max(tmp_ans1, tmp_ans2))

if __name__ == '__main__':
    main()


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

int main(){
    int n; cin >> n;
    vector<int> p(n); for(int i = 0; i < n; i++) cin >> p.at(i);
    
    int count = 0;
    for(int i = 1; i < n - 1; i++){
        int prev = p.at(i-1);
        int now = p.at(i);
        int next = p.at(i+1);
        int max_value = max(prev,max(now,next));
        int min_value = min(prev,min(now,next));
        if(now != max_value && now != min_value) count++;
    }
    cout << count << endl;
}



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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

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

    map<char, int> mp;
    rep(i, 3) mp["JOI"[i]] = i;

    int N;
    cin >> N;
    string s;
    cin >> s;
    vector<int> a(N);
    rep(i, N) {
        a[i] = mp[s[i]];
    }

    const int mod = 10007;
    VV dp(N + 1, V(1<<3, 0));
    dp[0][1] = 1; // at first J has the key
    rep(i, N) {
        rep(s1, 1<<3) {
            rep(s2, 1<<3) {
                if ( (s2 >> a[i] & 1) && (s2 & s1) ) {
                    (dp[i + 1][s2] += dp[i][s1]) %= mod;
                }
            }
        }
    }

    cout << accumulate(all(dp[N]), 0) % mod << endl;

}

Measured memory_bytes: 3288
#include <set>
    #include <map>
    #include <list>
    #include <queue>
    #include <stack>
    #include <cmath>
    #include <ctime>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cctype>
    #include <cstdlib>
    #include <cstring>
    #include <utility>
    #include <numeric>
    #include <complex>
    #include <sstream>
    #include <fstream>
    #include <iomanip>
    #include <cassert>
    #include <iostream>
    #include <iterator>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    typedef vector<int> vint;
    typedef pair<int, int> pint;
    #define rep(i, n) REP(i, 0, n)
    #define all(v) v.begin(), v.end()
    #define REP(i, x, n) for(int i = x; i < n; i++)
    #define INF 2e9
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c,d,x,flag=0,count=0;
  string s,s2,s3;
  cin>>s>>s2>>s3;
  s=s[0];
  s+=s2[0];
  s+=s3[0];
  transform(s.begin(),s.end(),s.begin(),::toupper);
  cout<<s<<'\n';

  
  return(0);
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline

N,X,M = map(int,readline().split())
MAXD = 55

# nex[t][v] = v (mod M)から2 ** tステップ進んだ先の値
# まずnex[0][v] は、v (mod M)から1ステップ進んだ先の値を入れておく
# sums[t][v] = v (mod M)から2 ** tステップ進んだ総和
# まずsums[0][v]は、各項がvそのものになる（1ステップだから）

nex = [[-1] * M for i in range(MAXD + 1)]
sums = [[0] * M for i in range(MAXD + 1)]

# まず、1ステップ進んだ先の値を入れる
for r in range(M):
  nex[0][r] = r * r % M
  sums[0][r] = r

for p in range(MAXD):
  for r in range(M):
    nex[p + 1][r] = nex[p][nex[p][r]]
    sums[p + 1][r] = sums[p][r] + sums[p][nex[p][r]]
    # 最初は、1ステップ（今いる場所）の場合の総和が入っている。次の進み先の総和と足すことで、
    # 今いる場所と次の場所の総和となり、2つ進んだ場合の総和が求められる
    # これで2つ進んだ場合の総和を求めるリストになるため、
    # ここで同じことをやることで、「2つ分の総和とその次の2つ分の総和」->「4つ分の総和」となる
    
res = 0
cur = X
for p in range(MAXD, -1, -1):
  if N & (1 << p):
    res += sums[p][cur]
    cur = nex[p][cur]
    
print(res)

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

using namespace std;

long long int gcd(long long int x, long long int y) {
  return y ? gcd(y, x%y) : x;
}

int main(){
    long long int A,B;
    cin >> A >> B;
    cout << A*B/gcd(A,B) << endl;
}

Measured memory_bytes: 256
import fractions

A, B, C, D = [int(i) for i in input().split()]

lcm = (C*D)//fractions.gcd(C,D)
A = A-1
t1 = A - (A//C + A//D - A//lcm)
t2 = B - (B//C + B//D - B//lcm)
print(int(t2 - t1))


Measured memory_bytes: 5048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define vst vector<string>
ll mx=INT_MAX;
ll mi=INT_MIN;
const ll mod=1e9+7;
int main()
{
    vll v,vv(102,0),vvv[250000],so(250000,0);
    ll i,j,k,n,x=0,s=0;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        ll a;
        cin>>a;v.pb(a);
    }
    vector<bool> vb(n+10,true);
    for(i=0;i<k;i++)
    {
        ll a,b;
        cin>>a;cin>>b;
        if(v[a-1]<=v[b-1]) vb[a-1]=false;
        if(v[a-1]>=v[b-1]) vb[b-1]=false;
    }
    for(i=0;i<n;i++)
    {
        if(vb[i]==true) s++;
    }
    cout<<s;
    
}

Measured memory_bytes: 12140
#[allow(unused_macros)]
macro_rules ! map { ( ) => { IndexMap ( std :: collections :: HashMap :: new ( ) ) } ; ( $ value : expr ; $ ( $ key : expr ) ,* ) => { IndexMap ( vec ! [ $ ( $ key ) ,* ] . into_iter ( ) . map ( | k | ( k , $ value ) ) . collect ::< std :: collections :: HashMap < _ , _ >> ( ) ) } ; ( $ value : expr ; $ ( $ ( $ key : expr ) ,* ) ;* ) => { map ! ( $ ( $ ( $ key ) ,* ) ;* => $ value ) } ; ( $ ( $ head : expr ) ,*; $ ( $ ( $ tail : expr ) ,* ) ;* => $ init : expr ) => { map ! [ map ! ( $ ( $ ( $ tail ) ,* ) ;* => $ init ) ; $ ( $ head ) ,* ] } ; ( $ ( $ head : expr ) ,* => $ init : expr ) => { map ! [ $ init ; $ ( $ head ) ,* ] } ; }
#[derive(Debug, Clone)]
struct IndexMap<K: Eq + std::hash::Hash, V>(pub std::collections::HashMap<K, V>);
#[allow(dead_code)]
impl<K: Eq + std::hash::Hash + std::clone::Clone, V> IndexMap<K, V> {
    fn keys_vec(&self) -> Vec<K> {
        self.keys().cloned().collect()
    }
}
#[allow(dead_code)]
impl<K, V> std::ops::Deref for IndexMap<K, V>
where
    K: Eq + std::hash::Hash,
{
    type Target = std::collections::HashMap<K, V>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
#[allow(dead_code)]
impl<'a, K, V, Q: ?Sized> std::ops::Index<&'a Q> for IndexMap<K, V>
where
    K: std::borrow::Borrow<Q> + Eq + std::hash::Hash,
    Q: Ord + Eq + std::hash::Hash,
{
    type Output = V;
    fn index(&self, index: &Q) -> &V {
        self.0.get(index).expect("no entry found for key")
    }
}
#[allow(dead_code)]
impl<'a, K, V> std::ops::IndexMut<&'a K> for IndexMap<K, V>
where
    K: Ord + Eq + std::hash::Hash + Clone,
    V: Default,
{
    fn index_mut(&mut self, index: &K) -> &mut V {
        self.0.entry(index.clone()).or_insert(Default::default());
        self.0.get_mut(index).expect("no entry found for key")
    }
}

fn main() {
    use std::io::Read;
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    
    let _: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();
    
    let mut hset: IndexMap<_, Vec<_>> = map![];
    for i in 0..m {
        let p: usize = iter.next().unwrap().parse().unwrap();
        let y: u64 = iter.next().unwrap().parse().unwrap();
        
        hset[&p].push((y, i));
    }
    let mut hset2 = map![];
    for key in hset.keys_vec() {
        hset[&key].sort();
    }
    for key in hset.keys_vec() {
        if let Some(vec) = hset.get(&key) {
            hset2[&key] = vec.iter().enumerate().map(|(j, &(_, i))| (i, j)).collect::<Vec<_>>();
        }
    }
    let mut acc = vec![];
    for (key, value) in hset2.iter() {
        acc.extend(value.iter().cloned().map(|(i, j)| (i, key, j)));
    }
    acc.sort();
    for tpl in acc {
        println!("{:>06}{:>06}", tpl.1, tpl.2+1);
    }
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

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

int main() {
    int n;
    ll ans = 0;
    vector<int> m[10][10] = {};
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int a = i;
        if (a >= 10) {
            a = a / pow(10, int(log10(i)));
        }
        int b = i % 10;
        m[a][b].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        int a = i;
        if (a >= 10) {
            a = a / pow(10, int(log10(i)));
        }
        int b = i % 10;

        if (a == 0 || b == 0)
            continue;
        ans += m[b][a].size();
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fr front()
#define tp top()
typedef long long int ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
#define iofast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define iofile freopen("input.txt","r",stdin),freopen("output.txt","w",stdout)
const ll LLINF = 1e18;
const int INF = 2e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1);
const int SIZE = 100005;

int N;
int A[SIZE];
int dp[SIZE];

int main (){
	
	for(int i=0;i<SIZE;i++){
		dp[i]=INF;
	}
	A[0]=0;
	dp[1]=0;
	scanf("%d", &N);
	for(int i=1;i<=N;i++){
		scanf("%d", &A[i]);
		dp[i]=min(dp[i],dp[i-1]+abs(A[i]-A[i-1]));
		if(i-2>=1) dp[i]=min(dp[i],dp[i-2]+abs(A[i]-A[i-2]));
	}
	// for(int i=1;i<=N;i++){
	// 	printf("%d ", dp[i]);
	// }
	// printf("\n");
	printf("%d\n", dp[N]);
	
	return 0;
}

Measured memory_bytes: 1024
# from sys import exit
h1, h2 = [int(n) for n in input().split()]
k1, k2 = [int(n) for n in input().split()]
a, b, c, d = [int(n) for n in input().split()]

A = h1*a + h1//10*c
A += h2*b + h2//20*d
B = k1*a + k1//10*c
B += k2*b + k2//20*d

if A > B:
    print("hiroshi")
elif A < B:
    print("kenjiro")
else:
    print("even")



Measured memory_bytes: 5604