akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    int K; cin >> K;
    cout << N - K +1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define forin(x,y) for(ll i=x;i<y;i++)
#define vii vector<ll>
#define pii  pair<ll,ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf 1e17
#define M (ll)(1e9+7)
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
vector<vii> v,child;

vii vis,par,dep;
ll max_dep=0;
ll ver,edge,from,to;


void bfs()
{
    ll cur = 1;
    queue<ll> q;    q.push(1);
    while(!q.empty())
    {
        cur = q.front(); q.pop();
        vis[cur] = 1;
        for(auto i: v[cur])
        {
            if(vis[i] == false)
            {
                q.push(i);
                dep[i] = dep[cur] +1;
                max_dep = max(max_dep,dep[i]);
                child[cur].pb(i);
                par[i] = cur;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);    cin.tie(0);     cout.tie(0);
    cin>>ver;   edge  = ver-1;  
    v.resize(ver+1);    vis.resize(ver+1,0);  par.resize(ver+1,-1);   dep.resize(ver+1,0);  child.resize(ver+1);
    forin(0,edge)
    {
        cin>>from>>to;  v[from].pb(to);  v[to].pb(from);
    }
    bfs();
    vector<vii> ar(max_dep+1);
    for(ll i=1;i<ver+1;i++)
    {
        ar[dep[i]].pb(i);
    }
    vii dp(ver+1,0);
    
    bool found = false;
    for(ll i=max_dep;i>=0;--i)
    {
        for(auto j : ar[i])
        {
            ll sum = 1;
            ll temp_sum=1;
            if(child[j].empty())
            {
                dp[j] = 2;
            }
            else
            {
                for(auto k: child[j])
                {
                    sum *= dp[k];
                    sum %= M;
                    if(child[k].empty() == false)
                    {
                        for(auto x : child[k])
                        {
                            temp_sum *= dp[x];
                            temp_sum %= M;
                        }
                    }
            
                }
                dp[j] = (sum+temp_sum)%M;
            }
        }
    }
    cout<<dp[1]<<endl;
}


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

using namespace std;

int main()
{
    long long n,m,r,x,y,i,j=0,k,z;
    cin>>n>>m;

    for(i=m;j!=n;i++)
    {
        cout<<i-n+1<<" ";
        j++;
    }
    for(i=m+1;i<=m+n-1;i++)
    {
        cout<<i<<" ";
    }

}


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

int main() {
    int a, b;
    int x, y, z;
    int max;
    cin >> a >> b;
    x = a + b;
    y = a - b;
    z = a * b;

    if(x >= y){
        max = x;
    }
    else {
        max = y;
    }
    if(max <= z){
        max = z;
    }
    cout << max << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    long int N,A[200000];
    long long int a=0;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(i!=0){
            if(A[i-1]>A[i]){
                a+=A[i-1]-A[i];
                A[i]+=A[i-1]-A[i];
            }
        }
    }
    cout<<a<<endl;
}

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

using namespace std;

int main(int argc, char const *argv[]){
    int n;
    cin >> n;
    vector<int> d;
    for(int i=0;i<n;i++){
        int _d;
        cin >> _d;
        d.push_back(_d);
    }
    sort(d.begin(), d.end());
    int b,s;
    b = d[d.size()/2];
    s = d[d.size()/2-1];
    cout << b-s << endl;
    return 0;
}

Measured memory_bytes: 892
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# from functools import reduce
# from math import gcd as gcd_base  # from fractions import gcd
# gcd = lambda *numbers: reduce(gcd_base, numbers)  # 3 数以上の最大公約数

# lcm_base = lambda x, y: (x * y) // gcd_base(x, y)
# lcm = lambda *numbers: reduce(lcm_base, numbers, 1)  # 3 数以上の最小公倍数
# 最小公倍数
# def gcd(a, b):
#     if a < b:
#         a, b = b, a
#     while a % b != 0:
#         a, b = b, a % b
#     return b



def many_lcm(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = tmp * l[i]//gcd(tmp, l[i])
    return tmp
N = INT()
A = LIST()

lm = many_lcm(A)
ans = 0
for a in A:
    ans += lm // a
    
print(ans % mod)



Measured memory_bytes: 6224
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, M;
    cin >> N >> M;
    vector<bool> broken(N + 1);
 
    for (int i = 0; i < M; i++) {
        int a; cin >> a;
        broken[a] = true;
    }
 
    vector<int> dp(N + 2);
    const int mod = 1e9 + 7;
    dp[N] = 1;
    for (int j = N - 1; j >= 0; j--) {
        if (broken[j]) dp[j] = 0;
        else dp[j] = (dp[j + 1] + dp[j + 2]) % mod;
    }
    cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 640
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e6 + 5;
const double eps = 1e-9;
using namespace std;

void solve()
{
  ll a, b, c, d;
  nl(a), nl(b), nl(c), nl(d);
  if (d < b || a < b)
  {
    printf("No\n");
    return;
  }
  if (d == b || b <= c+1) {
    if ((a % b) > c)
      printf("No\n");
    else
      printf("Yes\n");
    return;
  }
  ll g = __gcd(b, d);
  if (g <= b-1-c || a-((a-c-1)/b)*b < b) {
    printf("No\n");
    return;
  }
  printf("Yes\n");
  // ll delta = d - b;
  // if (c >= a && delta != 0)
  // {
  //   ll l = (c + 1 - a + delta - 1) / delta;
  //   a += l * delta;
  // }
  // if (b == d)
  // {
  //   if (c >= a)
  //   {
  //     printf("Yes\n");
  //     return;
  //   }
  //   ll nx = (a - c) % b + c;
  //   if ((a - c) % b == 0)
  //     nx += b;
  //   if (nx - b < 0)
  //     printf("No\n");
  //   else
  //     printf("Yes\n");
  //   return;
  // }
  // ll nx = (a - c) % b + c;
  // if ((a - c) % b == 0)
  //   nx += b;
  // if (nx - b < 0)
  // {
  //   printf("No\n");
  //   return;
  // }
  // if (b <= c + 1)
  // {
  //   printf("Yes\n");
  //   return;
  // }
  // if (b - 1 >= nx && nx >= c + 1)
  // {
  //   printf("No\n");
  //   return;
  // }
  // ll cur = a;
  // if (cur % b >= c + 1)
  // {
  //   printf("No\n");
  //   return;
  // }
  // a %= b, delta %= b;
  // if (__gcd(b, delta) == 1)
  // {
  //   printf("No\n");
  //   return;
  // }
  // //cur = 0;
  // //ll tmp = (c + 1 - a + b) % b;
  // unordered_set<ll> ax;
  // ll tmp = c + 1;
  // for (int i = 0; i <= tmp; i++)
  // {
  //   cur = (cur + delta) % b;
  //   if (ax.find(cur) != ax.end())
  //     break;
  //   ax.insert(cur);
  //   if (cur >= tmp)
  //   {
  //     printf("No\n");
  //     return;
  //   }
  // }
  // printf("Yes\n");
}

int main()
{
  int t;
  ni(t);
  while (t--)
    solve();
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
						For(j,m-1) cout<<a[i][j]<<' ';\
						cout<<a[i][m]<<endl; \
						} 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
	return x*f;
} 
char s[10000];
int c[10000]={};
int main()
{
//	freopen("C.in","r",stdin);
//	freopen(".out","w",stdout);
	int c4=0,c2=0,c1=0;	
	int n=read(),m=read();
	if (n%2==0&&m%2==0) {
		c4=n*m/4;
	}
	else if(n%2==1&&m%2==1) {
		c1=1;
		c4=(n/2)*(m/2);
		c2=(n-1)+(m-1); c2/=2;
	}
	else {
		c4=(n/2*2)*(m/2*2)/4;
		c2=(n*m-c4*4)/2;
	}
	For(i,n) {
		scanf("%s",s+1);
		For(j,m) c[s[j] ]++;
	}
	Fork(i,'a','z') {
		int p=min(c4,c[i]/4);
		c[i]-=4*p;
		c4-=p;
	}
	Fork(i,'a','z') {
		int p=min(c2,c[i]/2);
		c[i]-=2*p;
		c2-=p;
	}
	Fork(i,'a','z') {
		int p=min(c1,c[i]/1);
		c[i]-=p;
		c1-=p;
	}
	if (c1+c2+c4) {
	 puts("No");
	}else	puts("Yes");
	
	
	
	return 0;
}


Measured memory_bytes: 256
a,b,c = map(int,input().split())

if a <= b <= c :
    print(a,b,c)
elif a <= c <= b :
    print(a,c,b)
elif b <= a <= c :
    print(b,a,c)
elif b <= c <= a :
    print(b,c,a)
elif c <= a <= b :
    print(c,a,b)
elif c <= b <= a :
    print(c,b,a)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll t;
  cin>>t;
  for(ll i=0;i<t;i++){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a<b) {
      cout<<"No"<<endl;
      continue;
    }
    else if(b>d){
      cout<<"No"<<endl;
      continue;
    }
    else if(b<=c){
      cout<<"Yes"<<endl;
      continue;
    }
    ll fb=b;
    if(b<d) swap(b,d);
    while(b%d!=0){
      ll md=b%d;
      b=d;
      d=md;
    }
    ll max_v=fb-d+(a%d);
    if(max_v>c) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
  }
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main implements Runnable {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    int n = 0;
    List<Long> semiAns = new ArrayList<>();

    public void run() {
        n = sc.nextInt();
        dfs(0);
        long count = 0;
        for (Long semiAn : semiAns) {
            String s = semiAn.toString();
            if (s.contains("3") && s.contains("5") && s.contains("7")) {
                count++;
            }
        }
        System.out.println(count);
    }

    private void dfs(long x) {
        if (x > n) {
            return;
        }
        if (x != 0) {
            semiAns.add(x);
        }
        dfs(10 * x + 3);
        dfs(10 * x + 5);
        dfs(10 * x + 7);
    }
}

Measured memory_bytes: 29132
#include <stdio.h>
int gcd(long long int x,long long int y)
{
    long long int tem;
    while(y!=0)
    {
        tem=y;
        y=x%y;
        x=tem;
    }
    return x;
}
int main()
{
    long long int a,b,x,y,l,g;
    while(scanf("%lld%lld",&a,&b)==2)
    {
        g=gcd(a,b);
        l=(a*b)/g;
        printf("%lld %lld\n",g,l);
    }
    return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#define PI 3.14159265359
typedef long long ll;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
using namespace std;

int chan[31][200001];

int main(){
	int n, c;
	cin >> n >> c;
	for (int i = 0; i < n; i++){
		int s, t, x;
		cin >> s >> t >> x;
		for (int i = s*2-1; i < t*2; i++){
			chan[x][i] = 1;
		}
	}
	int ans = 0;
	for (int i = 0; i <= 200000; i++){
		int sum = 0;
		for (int j = 1; j <= 30; j++){
			sum += chan[j][i];
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 27072
#include <stdio.h>
 
#define N 1000000007

long long  question(long long a){
    long long ans = 1;
    for (long long i = 1; i <= a; i++)
    {
        ans = ans * i % N;
    }
    
    return ans;
}

long long  question2(long long a, long long b){
    long long ans = 1;
    for (long long i = a; i <= b; i++)
    {
        ans = ans * i % N;
    }
    
    return ans;
}


long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(void) {
    long long n, a, b;
    long long nq, nm, an, bn;
    scanf("%lld%lld%lld", &n, &a, &b);

    nm = modpow(2, n, N);
    an = question2(n-a+1, n) * (modpow(question(a)%N , N-2, N)) % N;
    bn = question2(n-b+1, n) * (modpow(question(b)%N , N-2, N)) % N;

    printf("%lld", (nm + N -1 + N - an + N - bn) %N );
    
    return 0;
}



Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>
#include <random>
#include <cmath>
using namespace std;
using namespace __gnu_pbds;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define uid uniform_int_distribution<lli>
#define lli long long int
#define ff first
#define ss second
#define pb push_back
#define popf pop_front()
#define popb pop_back()
#define all(vec) vec.begin(), vec.end()
#define fol(i,a,b) for(int i=a;i<b;i++)
#define forr(x,arr) for(auto& x:arr)
#define sz(x) (x.size())
#define mod 1000000007
#define INF 1000000000000000010
#define vi vector<int>
#define vlli vector<lli>
#define endl "\n"
#define ofk order_of_key
#define fbo find_by_order
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class my>
using indexed_set = tree<my,null_type,less<my>,rb_tree_tag,tree_order_statistics_node_update>;

template <class my>
inline my aabs (const my &a)   { return (a > 0)  ? a : -a;         }
inline lli gcd(lli a, lli b)   { return (b == 0) ? a : gcd(b,a%b); }
inline lli LSOne(lli k)        { return (k&(-k));                  }

inline int inv(lli o, int m = mod) {
  int b = m, u = 0, v = 1, t, a=o%m;
  while (a) {
    t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  if (u < 0) u += m;
  return u;
}
inline int add(const int &a, const int &b, int m=mod) { return ( a + b ) % m;           }
inline int sub(const int &a, const int &b, int m=mod) { return ( a - b + m ) % m;       }
inline int mul(const int &a, const int &b, int m=mod) { return int ( 1LL * a * b % m ); }
inline int mpow(int a, int b, int m=mod) {
    int ans = 1;
    a=((a%m)+m)%m;
    while (b) {
        if (b & 1) ans = mul(ans, a, m);
        a = mul(a, a, m);
        b >>= 1;
    }
    return ans;
}

void tejas_919()
{
    lli n, k, m, q, u=0, v=0, temp=1, max1=-1, max2=-1, ans=mod, a, b, val=0;
    cin>>n;
    int arr[n+5]={}, brr[n+5]={};
    fol(i,1,n+1) cin>>arr[i];
    fol(i,0,n+5) brr[i]=1;
    for(int i=n; i>0; i--)
    {
        temp=0;
        for(int j=i; j<=n; j+=i) if(brr[j]) temp++;
        if(temp%2!=arr[i]) brr[i]=0;
    }
    fol(i,1,n+1) if(brr[i]) u++;
    cout<<u<<endl;
    fol(i,1,n+1) if(brr[i]) cout<<i<<" ";
    cout<<endl;
}

int main()
{
    fastio cout<<endl;
    cout << fixed << setprecision(10);
    int t=1;
    //cin>>t;
    while(t--)
        tejas_919();
}


Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int A,B;
int b[5001];
vector<int> a[1001];
int main(){
  scanf("%d %d",&A,&B);
  for(int i=0;i<A;i++){
    int ai;
    scanf("%d",&ai);
    a[ai].push_back(i);
  }
  for(int i=0;i<B;i++) scanf("%d",&b[i]);
  int res = 0;
  for(int i=0;i<B;i++){
    if(a[b[i]].empty()) continue;
    int id = a[b[i]][0];
    int co = 1;
    for(int j=i+1;j<B;j++){
      if(a[b[j]].empty()) break;
      int st = 0,ed = (int)a[b[j]].size()-1,h;
      int nid=-1;
      while(st<=ed){
	h = (st+ed)/2;
	if(a[b[j]][h]>id){ nid = a[b[j]][h]; ed = h-1; }
	else st = h+1;
      }
      if(nid == -1) break;
      id = nid;
      co++;
    }
    res = max(res,co);
  }
  printf("%d\n",res);
}

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

using namespace std;

#define COUT_PRECISION 10

namespace abreto
{

const int maxn = 2048;

int N, X, Y;
int cnt[maxn];

void count(void)
{
    for (int i = 1; i < N; i++)
        for (int j = i + 1; j <= N; j++)
        {
            int d = min(j - i, abs(X - i) + abs(j - Y) + 1);
            cnt[d]++;
        }
}

void main(void)
{
    cin >> N >> X >> Y;
    if (X > Y)
        swap(X, Y);
    count();
    for (int k = 1; k < N; k++)
        cout << cnt[k] << '\n';
}

} // namespace abreto

int main(void)
{
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(COUT_PRECISION);
    abreto::main();
    return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.readLine

object Main {

  def main(args: Array[String]) = {

    var n = readLine.split(" ").map(_.toInt)
    while( n(0) != 0 || n(1) != 0) {
      val h = n(0)
      val w = n(1)

      for(i <- 0 to h-1) {
        val str = if(i%2==0) "#."*w else ".#"*w
        println(str.take(w))
      }
      println()
      n = readLine.split(" ").map(_.toInt)
    }
  }
}

Measured memory_bytes: 45496
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <map>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <numeric>
 
using namespace std;


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

    long long N; cin >> N;
    cout << (N*(N-1)>>1)  << endl;
}


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

#define ll long long
#define PB push_back
#define PII pair<int, int>
#define MP make_pair
#define all(x) x.begin(), x.end()
#define REP(x, y, z) for(int x = (y); x <= (z); x++)
#define REPP(x, y, z) for(int x = (y); x >= (z); x--)
#define F first
#define S second
#define MSET(x, y) memset(x, y, sizeof(x)) 
#define EB emplace_back
#define maxn
#define IOS ios::sync_with_stdio(false); cin.tie(0);

//structure

//declaration

//functions

int main(void)
{
	#ifdef DBG
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
	#endif

	IOS;

	string str;
  	cin >> str;
  
  	REP(i, 1, str.size())
      cout << 'x';
  cout << '\n';

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ab = a * b;
    int cd = c * d;
    if (ab == cd) {
        cout << ab << "\n";
    } else if (ab > cd) {
        cout << ab << "\n";
    } else {
        cout << cd << "\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
  int a, b;
  cin >> a >> b;

  if (a == 1) {
	a = 14;
  }
  if (b == 1) {
	b = 14;
  }
  if (a > b) {
	cout << "Alice" << endl;
  }
  else if (a < b) {
	cout << "Bob" << endl;
  }
  else {
	cout << "Draw" << endl;
  }
}

Measured memory_bytes: 256
"""
入力例1

5 2
8 7 6
rsrpr

このとき、r1回目から3回目に対して勝敗が
oxo
となるようにするとよさそう。
"""
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
ans = 0
memo = []   # 勝つ手を出したかどうかを保存しとく。
for i in range(N):
    if i >= K and T[i] == T[i - K] and memo[i - K]:
        memo.append(False)
        continue
    if T[i] == 'r':
        ans += P
    elif T[i] == 's':
        ans += R
    else:
        ans += S
    memo.append(True)
print(ans)


Measured memory_bytes: 79740
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;
int main()
{
    int n;
    cin>>n;
    pair<pair<string,int>,int> p[110];
    rep(i,n){
        cin>>p[i].first.first>>p[i].first.second;
        p[i].first.second*=-1;
        p[i].second=i+1;
    }
    sort(p,p+n);
    rep(i,n) cout<<p[i].second<<endl;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n;
  vector<ll> a(311111);
  cin>>n;
  for(int i=0;i<3*n;i++)cin>>a[i];
  sort(a.rbegin(),a.rend());
  ll ans=0;
  int cnt=1;
  for(int i=0;i<n;i++){
    ans+=a[cnt];
    cnt+=2;
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
	int n, m, x;
	int a[100];
	cin >> n >> m >> x;
	for (int i = 0; i <= m - 1; i++) {
		cin >> a[i];
	}

	int cost1 = 0;
	int cost2 = 0;
	//真ん中より後ろ
	for (int i = 0; i <= m - 1; i++) {
		for (int j = 1; j <= (n - 1) - x; j++) {
			if (a[i] == (x + j)) {
				cost1 += 1;
			}
		}
	}
	//真ん中より前
	for (int i = 0; i <= m - 1; i++) {
		for (int j = 1; j <= x - 1; j++) {
			if (a[i] == (x - j)) {
				cost2+= 1;
			}
		}
	}

	if (cost1 > cost2) {
		cout << cost2 << endl;
	}
	else {
		cout << cost1 << endl;
	}
	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include <iostream>

using namespace std;

const int MaxN = 100005;

long long n, A, B;
long long v[MaxN];

bool Enough(long long bombCnt) {
  long long bigUsed = 0;
  for (int i = 1; i <= n; ++i) {
    long long bigNeeded = (v[i] - bombCnt * B) / (A - B);
    bigNeeded = max(bigNeeded, 1LL * 0);
    long long damageDone = bigNeeded * A + (bombCnt - bigNeeded) * B;
    if (damageDone < v[i]) {
      ++bigNeeded;
    }

    bigUsed += bigNeeded;

    if (bigUsed > bombCnt) {
      return false;
    }
  }

  return true;
}

long long BinSearch(long long lf = 1, long long rg = (long long) 1e9) {
  long long ans = -1;
  while (lf <= rg) {
    long long med = (lf + rg) / 2;

    if (Enough(med)) {
      rg = med - 1;
      ans = med;
    }
    else {
      lf = med + 1;
    }
  }

  return ans;
}

int main() {
  cin >> n >> A >> B;
  long long biggest = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
    biggest = max(biggest, v[i]);
  }

//  long long rgVal = biggest / A + 5;
  cout << BinSearch() << '\n';
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=1; i<(int)(n); i++)
int main(){
long N, X, M, l, r, ans=0; cin >> N >> X >> M; 
long S[3*M]={}, L[3*M]={}, A[3*M]={};
A[0]=X; REP(i, 3*M){ A[i]=(A[i-1]*A[i-1])%M; }
S[0]=X; REP(i, 3*M){ S[i]=S[i-1]+A[i]; }
L[0]=-1; REP(i, 3*M){ L[i]=-1; }
L[X]=0;
REP(i, 3*M){ 
  if(L[A[i]]!=-1){ l=L[A[i]]; r=i; break; }
  else{ L[A[i]]=i; }
}
if(N<=2*M){ cout << S[N-1] << "\n"; return 0; }
long w=r-l, p=S[r]-S[l], W=N-l-1;
ans=S[l]; ans+=p*(W/w); ans+=(S[l+W%w]-S[l]);
cout << ans << "\n";
}


Measured memory_bytes: 10668
import sys
input = sys.stdin.readline

s_map = {}
N = int(input())
for _ in range(N):
    s = input().rstrip('\r\n')
    num = s_map.get(s)
    if num == None:
        num = 1
    else:
        num += 1
    s_map[s] = num
M = int(input())
for _ in range(M):
    s = input().rstrip('\r\n')
    num = s_map.get(s)
    if num == None:
        num = -1
    else:
        num -= 1
    s_map[s] = num
s_map_sorted = sorted(s_map.items(), key=lambda x:x[1], reverse=True)
ans = max(0, s_map_sorted[0][1])
print(ans)

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

template <typename T>
void print(const T &v);

struct event
{
    ll t, type, val; // 時間，モード，座標
    bool operator<(const event &a)
    {
        return t < a.t;
    }
};

int main()
{
    ll N, Q;
    cin >> Q >> N;
    vector<event> eves;
    vector<ll> D(N);
    rep(i, Q)
    {
        ll s, t, x;
        cin >> s >> t >> x;
        eves.push_back({s - x, 1, x});  // insert
        eves.push_back({t - x, -1, x}); // erase
    }
    rep(i, N)
    {
        cin >> D[i];
    }
    sort(eves.begin(), eves.end());

    int k = 0;
    multiset<ll> st;
    rep(i, N)
    {
        // D[i]以下のイベントを全て処理する(stにinsert, erase)
        while (k < eves.size() && eves[k].t <= D[i])
        {
            if (eves[k].type == 1)
            {
                st.insert(eves[k].val);
            }
            else
            {
                st.erase(st.find(eves[k].val));
            }
            k++;
        }

        // stの最小値を調べて出力
        if (st.empty())
        {
            cout << -1 << endl;
        }
        else
        {
            cout << *st.begin() << endl;
        }
    }
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 22632
#include <stdio.h>

int main() {
	int pos,a,b;
	scanf("%d %d %d", &pos, &a, &b);
	int disa, disb;
	if(pos > a){
		disa = pos - a;
	}else{
		disa = a - pos;
	}
	if(pos > b){
		disb = pos - b;
	}else{
		disb = b - pos;
	}
	if(disa > disb){
		puts("B");
	}else{
		puts("A");
	}
	
	
	return 0;
}


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



int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    int x;
    cin>>x;
    if(x==0)cout<<1;
    else cout<<0;



	return 0;
}

Measured memory_bytes: 3188
N,K=$<.read.split.map(&:to_i)

if K == 0
    puts N*N
    exit
end

ret = 0
2.upto(N) do |i|
    x = [i-K,0].max
    r,q = N.divmod(i)
    # p [r,q, r * x, [q-K+1,0].max]
    ret += r * x + [q-K+1,0].max
end
puts ret

# arr = Array.new(N) { Array.new(N,0) }
# N.times do |i|
#     N.times do |j|
#         arr[i][j] = (i+1)%(j+1)
#     end
# end

# arr.each do |l|
#     l.each do |n|
#         print sprintf("%3d", n)
#     end
#     puts ''
# end

Measured memory_bytes: 14332
##templete
n, @A, @B, @C = gets.chomp.split(" ").map { |e| e.to_i }

@l = []
n.times do |i|
  @l[i] = gets.chomp.to_i
end

@ans = 1000000000000
@count = 0

def abs(x)
  if x < 0
    return -x
  else
    return x
  end
end

def absd(x)
  if x <= 0
    return 0
  else
   return x
  end
end


def dfs(d, v)
  if d == -1
    calc(v)
    @count += 1

    return
  end

  for i in 0..3 do
    v[d] = i
    dfs(d-1, v)
  end
end


def calc(vec)
  a = 0
  a_leng = 0
  b = 0
  b_leng = 0
  c = 0
  c_leng = 0
  n = vec.length
  for i in 0..n-1 do
    ll = vec[i]
    if ll == 0
      a += 1
      a_leng += @l[i]
    elsif ll == 1
      b += 1
      b_leng += @l[i]
    elsif ll == 2
      c += 1
      c_leng += @l[i]
    end
  end

  a_temp = a > 0 ? (a-1) * 10 + abs(a_leng - @A) : 10**9
  b_temp = b > 0 ? (b-1) * 10 + abs(b_leng - @B) : 10**9
  c_temp = c > 0 ? (c-1) * 10 + abs(c_leng - @C) : 10**9
  temp = a_temp + b_temp + c_temp
  @ans = @ans > temp ? temp : @ans
end

dfs(n-1, [])

puts @ans


Measured memory_bytes: 3836
N = int(input())
S = input()

ans = 0

for i in range(1000):

    flag = 0
    for s in S:
        if flag == 0 and s == str( i // 100 ):
            flag = 1
        elif flag == 1 and s == str( (i % 100) // 10 ):
            flag = 2
        elif flag == 2 and s == str( i % 10  ):
            flag = 3
            break

    if flag == 3:
        ans += 1

print (ans)


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

using namespace std;
#define ll long long int

int main()
{
    ll n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    ll ans=0;
    for(int i=0;i<k;i++)
        ans+=a[i];
    cout<<ans;
}


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


#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  int64_t n;
  cin >> n;
  int count = 0;
  int a;
  for(int64_t i=0;i<n;i++){
    cin >> a;
    if(i%2==0 && a%2==1) count++;
  }
  cout << count << endl;
  return 0;
}




Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define dcout cout << fixed << setprecision(15)
#define rep(i, a) for(int i = 0; i < a; i++)
#define arep(i, x) for(auto i : x)
#define all(v) v.begin(), v.end()
#define int long long
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
using namespace std;
signed main() {
    int n, k;
    cin >> n >> k;
    VE l;
    rep(i, n) {
        int enter;
        cin >> enter;
        l.pb(enter);
    }
    sort(all(l), greater<int>());
    int ans = 0;
    rep(i, k) {
        ans += l[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
use proconio::input;
use std::collections::HashMap;

const LIMIT: usize = 1_000_005;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n],
    }

    a.sort();
    let a = a;

    // dbg!(&a);

    let mut map = HashMap::new();
    for ai in a.iter().copied() {
        let entry = map.entry(ai).or_insert(0i64);
        *entry += 1;
    }
    let map = map;

    // dbg!(&map);

    let mut v = vec![false; LIMIT];
    let mut ans = 0i64;
    for ai in a {
        if v[ai] {
            continue;
        }

        if map[&ai] == 1 {
            ans += 1;
        }

        let mut tmp = ai;
        while tmp < LIMIT {
            v[tmp] = true;
            tmp += ai;
        }
    }

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


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

int main()
{
	int a, s, r;
	cin>>a;
	for(int d=0;d<a;d++)
	{
		int x, x2;
		cin>>x>>x2;
		if(x==x2)
		{
			s+=1;
		}
		else
		{
			if(s>=3)
			{
				r+=1;
			}
			s=0;
		}
	}
	if(s>=3||r>=1)
	{
		cout<<"Yes";
	}
	else
	{
		cout<<"No";
	}
	return 0;
}


Measured memory_bytes: 3548
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
  int n, m; cin >> n >> m;
  vector<string> a(n), b(m);
  rep(i, n) cin >> a[i];
  rep(i, m) cin >> b[i];
  bool ans = false;
  rep(i, n - m + 1) {
    rep(j, n - m + 1) {
      bool isMatched = true;
      rep(k, m) {
        rep(l, m) {
          if (a[i + k][j + l] != b[k][l]) isMatched = false;
        }
      }
      if (isMatched) {
        ans = true;
        break;
      }
    }
    if (ans) break;
  }
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int i,n,debt = 100000;
  scanf("%d",&n);
  for(i = 0;i < n;i++) {
    debt = debt*1.05;
    if((debt % 1000) != 0) {
      debt = (debt/1000 + 1)*1000;
    }
  }
  printf("%d\n",debt);
  return 0;
}

Measured memory_bytes: 592
#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++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
bool dp[100100];
 
 
int main () {
    int N, M;
    cin >> N >> M;

    int ans =0;
    if(N>1) ans +=N*(N-1)/2;
    if(M>1) ans +=M*(M-1)/2;

    cout << ans << endl; 

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
template<class T> inline bool chmax(T& a, T b) { if(a < b){ a=b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if(a > b){ a=b; return 1; } return 0;}

int main(){
	string s;
	int k;
	cin >> s >> k;
	
	set<string> sub;
	REP(i,s.size()){
		for(ll j=1; j<=k; j++){
			sub.insert(s.substr(i,j));
		}
	}
	
	int index=1;
	string ans;
	for(auto x:sub){
		if(index==k){
			ans = x;
			break;
		}
		index++;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 4724
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int MOD = 1000000007;
const ll INF = 1LL << 60;
int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   ll n;
   cin >> n;
   ll count = 0;
   for(ll i = 1;i <= n;i++) {
      if(i%3==0||i%5==0) {

      } else {
         count+=i;
      }
   }
   cout << count << endl;
}

Measured memory_bytes: 3656
n, q = map(int, input().split())
s = input()

mae = [0 for i in range(n)]
ato = [0 for i in range(n)]
bef = 'Z'
for i in range(n):
    if bef == 'A' and s[i] == 'C':
        mae[i-1] = -1
    bef = s[i]
bef = 'Z'
for i in range(n-1, -1, -1):
    if bef == 'C' and s[i] == 'A':
        ato[i+1] = -1
    bef = s[i]

for i in range(1, n):
    mae[i] += mae[i-1]
for i in range(n-2, -1, -1):
    ato[i] += ato[i+1]
num = -mae[-1]

ans = []
for i in range(q):
    li, ri = map(int, input().split())
    li, ri = li-1, ri-1
    minus = 0
    if li > 0:
        minus += mae[li-1]
    if ri < n-1:
        minus += ato[ri+1]
    ans.append(num+minus)

for i in range(q):
    print(ans[i])

Measured memory_bytes: 61724
def main():
    N = int(input())

    ctr = [[0] * 10 for _ in range(10)]
    for x in range(1, N + 1):
        s = str(x)
        ctr[int(s[0])][int(s[-1])] += 1

    ans = 0
    for i in range(10):
        for j in range(10):
            ans += ctr[i][j] * ctr[j][i]
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
  int K;cin >> K;
  string S;cin >> S;
  int N = S.size();
  for(int i=0;i<min(K,N);i++){
    cout << S[i];
  }
  if(K<S.size()){
    cout << "...";
  }
  cout << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define fr(i,n) for(int i=0;i<(n);i++)
#define Fr(i,n) for(int i=0;i++<(n);)
#define ifr(i,n) for(int i=(n)-1;i>=0;i--)
#define iFr(i,n) for(int i=(n);i>0;i--)

const ll MOD=1e9+7;

ll ad(ll x,ll y=0){
    return (x+y)%MOD;
}

ll mlt(ll x,ll y=1){
    return (x*y)%MOD;
}

ll pwr(ll x,ll y){
    ll pw[32]={},w=1;
    pw[0]=x;
    fr(i,31) pw[i+1]=mlt(pw[i],pw[i]);
    fr(i,32){
        w=mlt(w,1+(y%2)*(pw[i]-1));
        y/=2;
    }
    return w;
}

ll inv(ll x){
    return pwr(x,MOD-2);
}

ll fc[200010]={1};
ll fct(ll x){
    if(fc[x]==0) fc[x]=mlt(x,fct(x-1));
    return fc[x];
}

ll ifc[200010]={1};
ll ifct(ll x){
    if(ifc[x]==0) ifc[x]=inv(fct(x));
    return ifc[x];
}

ll comb(ll n,ll r){
    if(n<0 || r<0 || n<r) return 0;
    return mlt(fct(n),mlt(ifct(r),ifct(n-r)));
}

int main(){
  ll n,a[100010],b,k=0,c[2];
  bool f[100010]={};
  cin>>n;
  fr(i,n+1){
    cin>>a[i];
    if(f[a[i]]) b=a[i];
    f[a[i]]=1;
  }
  fr(i,n+1) if(a[i]==b) c[k++]=i;
  c[1]=n-c[1];
  Fr(i,n+1){
    cout<<ad(comb(n+1,i)+MOD-comb(c[0]+c[1],i-1))<<endl;
  }
}

Measured memory_bytes: 5248
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main() {
    ll N, M, X;
    int i, j;

    cin >> N >> M >> X;

    vector<int> C(N+1);
    vector<vector<int> > A(N+1, vector<int>(M+1));

    for(i=1; i<=N; i++) {
        cin >> C[i];
        for(j=1; j<=M; j++) {
            cin >> A[i][j];
        }
    }

    int ans = INF;

    for(i=1; i<=(1<<N+1); i++) {
        int cost = 0;
        vector<int> sum(M+1, 0);
        for(j=1; j<=N; j++) {
            if(((i>>j)&1)) {
                cost+=C[j];
                for(int k=1; k<=M; k++) {
                    sum[k]+=A[j][k];
                }
            }
        }
        bool ok = true;
        for(j=1; j<=M; j++) {
            if(sum[j] < X) {
                ok = false;
            }
        }
        if(ok) {
            ans = min(ans, cost);
        }
    }
    if(ans == INF) cout <<  -1 << endl;
    else cout << ans << endl;

    return 0;
    
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int A[3];
  for(int i=0;i<3;i++){
    cin >> A[i];
  }
  sort(A,A+3);
  int ans=10000;
  do{
    ans=min(ans,abs(A[0]-A[1])+abs(A[1]-A[2]));
  }while(next_permutation(A,A+3));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
typedef pair<ll,ll> l_l;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back


ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}

int main(){
    ll e;cin>>e;
    cout<<e*e<<endl;
    
    return 0;
}







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

const ll mod=1000000007;

int main() {
  int n,count=0;
  cin >> n;
  map<string,int> mp;
  r(i,n){
    string s;
    cin >> s;
    mp[s]++;
  }
  for(auto it=mp.begin();it!=mp.end();it++){
    count++;
  }
  cout<<count<<endl;
}

Measured memory_bytes: 19116
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;
	std::vector<LL>A(N);
	std::vector<std::vector<LL>>x(N), y(N);
	rep(i, N)
	{
		in >> A[i];
		x[i].resize(A[i]); y[i].resize(A[i]);
		rep(j, A[i]) in >> x[i][j] >> y[i][j];
	}

	LL ans = 0;
	rep(bit, (1LL << N))
	{
		LL cnt = 0;
		std::vector<bool>isHonest(N, false);
		rep(i, N)
		{
			if (bit & (1LL << i))
			{
				isHonest[i] = true;
				++cnt;
			}
		}

		bool flag = true;
		rep(i, N)
		{
			if (!isHonest[i]) continue;
			rep(j, A[i])
			{
				if (isHonest[x[i][j] - 1] != (y[i][j] == 1))
				{
					flag = false;
					break;
				}
			}
			if (!flag) break;
		}
		if (flag) ans = std::max(ans, cnt);
	}

	out << ans << std::endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define repn(i, x) for (int i = 1; i <= (int)(x); i++)
#define repr(i, x) for (int i = ((int)(x) - 1); i >= 0; i--)
#define reprn(i, x) for (int i = ((int)(x)); i > 0; i--)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
void solve() {
	int64 n; cin >> n;
	vector<int64> a(n);
	bool ng_flag = true;
	rep (i, n) {
		int64 tmp; cin >> tmp;
		tmp--;
		if (tmp == 0) ng_flag = false;
		a[i] = tmp;
	}
	if (ng_flag) {
		cout << -1 << endl; 
		return;
	}
	int64 target = 0;
	int64 ans = 0;
	rep (i , n) {
		if (a[i] != target) {
			ans++;
		} else {
			target++;
		}
	}
	cout << ans << endl;
	return;
}

int main() {
	solve();
  return 0;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int,input().split()))
kind = []
var = 0

def d_color(num):
     if 1<=num and num<=399:
         return "a"
     elif 400<=num and num<=799:
         return "b"
     elif 800<=num and num<=1199:
         return "c"
     elif 1200<=num and num<=1599:
         return "d"
     elif 1600<=num and num<=1999:
         return "e"
     elif 2000<=num and num<=2399:
         return "f"
     elif 2400<=num and num<=2799:
         return "g"
     else:
         return "h"

for i in range(n):
    if a[i]<3200:
        kind.append(d_color(a[i]))
    else:
        var += 1

kind = list(set(kind))

MIN ,MAX = len(kind),len(kind)+var
if MIN == 0:
    MIN =1 

print(MIN,MAX)

Measured memory_bytes: 3064
import collections

S = input()
Q = int(input())

rev = False
deque = collections.deque()
for c in S:
    deque.append(c)
for _ in range(Q):
    read = input()
    if read == '1':
        rev = not rev
    else:
        _, f, c = read.split()
        if not rev:
            if f == '1':
                deque.appendleft(c)
            else:
                deque.append(c)
        else:
            if f == '1':
                deque.append(c)
            else:
                deque.appendleft(c)

ret = ''.join(deque if not rev else reversed(deque))
print(ret)


Measured memory_bytes: 74968
#include <bits/stdc++.h>
typedef long long int ll;
#define vaibhavv06               \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define int long long
#define MM(a, b) memset(a, b, sizeof(a))
const ll MOD = 1000000007;
using namespace std;

int32_t main()
{
	vaibhavv06;
	int n; 
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	int minn = arr[0];
	int ans=1;
	for(int i=1;i<n;i++){
		if(arr[i]<=minn){
			ans++;
			minn = min(arr[i],minn);
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main () {
  int count, n, q;

  scanf("%d", &n);
  int A[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &A[i]);
  }

  scanf("%d", &q);
  int Q[q];
  for (int i = 0; i < q; i++) {
    scanf("%d", &Q[i]);
  }

  int left = 0;
  int right = n;
  int mid;

  count = 0;

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

    while (left < right) {

      mid = (left + right) /2;

      if (A[mid] == Q[i]) {
        count++;
        break;
      } else if (A[mid] > Q[i]) {
        right = mid;
      } else if (A[mid] < Q[i]) {
        left = mid + 1;
      }

    }

    left = 0;
    right = n;

  }

  printf("%d\n", count);

}

Measured memory_bytes: 3168
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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 a[3];
  rep (i, 3) {
    cin >> a[i];
  }
  int five, seven;
  seven = five = 0;
  rep (i, 3) {
    if (a[i] == 5) five++;
    if (a[i] == 7) seven++;
  }
  if (five == 2 && seven == 1) YES;
  else NO;


  return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

long calc(int x, int y, int z) {
    long lo = 0;
    long hi = x;
    long ans = 0;
    while (lo <= hi) {
        long m = (lo + hi) / 2;
        long d = m * y + (m + 1) * z;
        if (d <= x) {
            ans = max(ans, m);
            lo = m + 1;
        }
        else hi = m - 1;
    }
    return ans;
}

void main() {
    auto xyz = readints;
    int x = xyz[0], y = xyz[1], z = xyz[2];

    writeln(calc(x, y, z));
}


Measured memory_bytes: 256