akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false

//小数点以下切り上げ
long long roundup(long long a,long long b){
  return (a+b-1)/b;
}

int main(void){
    
    ll N,K,a;
    vector<ll> A;
    ll Asum=0;
    cin >> N >> K;
    REP(i,N){
        cin >> a;
        A.push_back(a);
        Asum+=a;
    }
    
    ll ng=0,ok=Asum,mid;
    
    while(abs(ok-ng)>1){
        mid = (ok+ng)/2;
        
        ll num=0;
        REP(i,N){
            num += roundup(A[i],mid);
        }
        num-=N;
        
        //cout << ng MM ok MM mid MM num << endl;
        
        if(num>K){
            ng=mid;
        }else{
            ok=mid;
        }
        
    }
    
    cout << ok << endl;
    
    return 0;
}



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

typedef long long ll;;

ll to_num(string s){
  if(s=="Rock"){return 0;}
  if(s=="Fire"){return 1;}
  if(s=="Scissors"){return 2;}
  if(s=="Snake"){return 3;}
  if(s=="Human"){return 4;}
  if(s=="Tree"){return 5;}
  if(s=="Wolf"){return 6;}
  if(s=="Sponge"){return 7;}
  if(s=="Paper"){return 8;}
  if(s=="Air"){return 9;}
  if(s=="Water"){return 10;}
  if(s=="Dragon"){return 11;}
  if(s=="Devil"){return 12;}
  if(s=="Lightning"){return 13;}
  if(s=="Gun"){return 14;}
  return -1;
}

string ans(ll a){
  if(a==0){return "Rock";}
  if(a==1)return "Fire";
  if(a==2)return "Scissors";
  if(a==3)return "Snake";
  if(a==4)return "Human";
  if(a==5)return "Tree";
  if(a==6)return "Wolf";
  if(a==7){return "Sponge";}
  if(a==8){return "Paper";}
  if(a==9){return "Air";}
  if(a==10){return "Water";}
  if(a==11){return "Dragon";}
  if(a==12){return "Devil";}
  if(a==13){return "Lightning";}
  if(a==14){return "Gun";}
  return "!";
}


int main(){
  while(1){
  vector<ll> count(30,0);
  ll n;
  cin>>n;
  if(n==0){break;}
  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    count[to_num(s)]++;
    count[to_num(s)+15]++;
  }
  for(int i=1;i<30;i++){
    count[i]+=count[i-1];
  }
  bool done=false;
  for(int i=0;i<15 && !done;i++){
    if(i==0){
      if(count[i]!=0){
	if(count[i]==n){cout<<"Draw"<<endl; done=true;}
	else if(count[i+7]==n){cout<<"Rock"<<endl; done=true;}
      }
    }
    else{
      if(count[i]-count[i-1]!=0){
	if(count[i]-count[i-1]==n){cout<<"Draw"<<endl; done=true;}
	else if(count[i+7]-count[i-1]==n){cout<<ans(i)<<endl; done=true;}
      }
    }
  }
  if(!done){cout<<"Draw"<<endl;}

  }


  return 0;
}



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

int main(){
                                                                     

    int n, i;

    int k = 0;

    
    cin >> n;

    vector<int> a(n + 1);


    for( i = 1 ; i <= n ; i = i + 1 ){

         cin >> a.at(i);

         }


    for( i = 1 ; i <= n ; i = i + 1 ){

         if( a.at( a.at(i) ) == i ) k += 1;

         }


    cout << k / 2 << endl;


    return 0;

    }

Measured memory_bytes: 640
//
//  respect the past, embrace the future
//  rectangle cutting
//

#include  <algorithm>
#include  <iostream>
#include  <climits>
#include  <cstdlib>
#include  <cstring>
#include  <cmath>
#include  <cstdio>
#include  <unordered_map>
#include  <map>
#include  <set>
#include  <stack>
#include  <string>
#include  <vector>
#include  <queue>

using namespace :: std;

using vpll = vector <pair <long long, long long> >;
using pll = pair <long long, long long>;
using vll = vector <long long>;
using ll = long long;

#define W (long long) (5e3 + 7)
#define N (long long) (2e6 + 7)
#define M (long long) (1e9 + 7)
#define INF (long long) (2e18)
#define F first
#define S second

inline void fastInputOutput () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
}

inline void ReadWriteFromFile () {
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
}

double n, m, x, y;

int32_t main (int argc, char *argv[]) {
  fastInputOutput();
  // ReadWriteFromFile();
  
  cin >> n >> m >> x >> y;
  printf("%.6lf %d", n * m / 2, (x == n / 2 && y == m / 2));
}

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

int main(){
long double A,B,X;
  cin >> A >> B >> X;
long double ans=0;
  
long double u=0;
long double s=X/A;

  if(s>B*A/2){
    u=2*s/A-B;
    u=B-u;
    
    ans=atan(u/A)*180/PI;
  }else{
    u=s*2/B;

    ans=atan(B/u)*180/PI;

  }
  cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
import itertools
L, R = [int(_) for _ in input().split()]
if R - L > 2017 or L % 2019 > R % 2019:
    print(0)
    exit()

L %= 2019
R %= 2019
ans = min(i * j % 2019 for i, j in itertools.combinations(range(L, R + 1), 2))
print(ans)


Measured memory_bytes: 3060
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
long long getDigit(long long n);      // 数字の桁数を取得する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      ((a)/GCD((a),(b))*(b))
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;

// code
// ------------------------------------------------
int main()
{

  ll n,k;
  cin >> n >> k;

  vll h(n);
  rep(i,n) cin >> h[i];

  ll hight = LLONG_MAX;

  vsort(h);

  rep(i,n-k+1)
  {
    ll buf = h[i+k-1] - h[i];
    hight = min(hight,buf);
  }

  cout << hight << endl;

  return 0;
}
// funcの実体
// ------------------------------------------------
ll getDigit(ll n)
{
  int i = 1;
  while(1)
  {
    n = n / 10;
    if(n == 0)
      break;
    i++;
  }
  return i;
}
ll CalcSumOfDigit(ll n)
{
  ll s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(i,a) for(auto& i:a)
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define pb push_back
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
typedef long long ll;
int re(){int x=0; bool neg=false;char c;while (c!='-' && (c<'0'||'9'<c)) c=getchar();if (c=='-'){neg=true;c=getchar();}while ('0'<=c && c<='9'){x=x*10+c-'0';c=getchar();}if (neg) x=-x;return x;}
void rout(int x) {if (x>9) rout(x/10); putchar(x%10+'0');}
const int N=200010;
int n,c,top;
int h[N],f[N];
struct aa{int a,b;};
aa st[N];
double giao(aa x,aa y) {return 1.0*(y.b-x.b)/(x.a-y.a);}
double L[N];
 main()
{
    //freopen("frog3.inp","r",stdin);
    cin>>n>>c;
    forinc(i,1,n) cin>>h[i];
    st[++top]={-2*h[1],h[1]*h[1]+c};
    forinc(i,2,n)
    {
        int l=1,r=top,res=0;
        while (l<=r)
        {
            int m=(l+r)/2;
            if (L[m]<=1.0*h[i]) res=m,l=m+1;
            else r=m-1;
        }
        f[i]=st[res].a*h[i]+h[i]*h[i]+st[res].b;
        aa t={-2*h[i],f[i]+h[i]*h[i]+c};
        while (top>=2 && giao(t,st[top-1])<=giao(st[top-1],st[top])) top--;
        st[++top]=t;
        L[top]=giao(st[top],st[top-1]);
    }
    cout<<f[n];
}


Measured memory_bytes: 8064
#include <stdio.h>

int main(void)
{
	int a;
	int b;
	int i;
	
	int flag;
	int finish;
	
	finish = 0;
	while (1){
		flag = 0;
		scanf("%d %d", &a, &b);
		if (a == 0 && b == 0){
			break;
		}
		
		if (finish == 1){
			printf("\n");
		}
		
		finish = 1;
		for (i = a; i <= b; i++){
			if (i % 4 == 0 && i % 100 != 0 || i % 400 == 0){
				printf("%d\n", i);
				flag = 1;
			}
		}
		
		if (flag == 0){
			printf("NA\n");
		}
	}
	
	return (0);
}
			
		
		

Measured memory_bytes: 616
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  cout.precision(12);

  long N;
  cin >> N;

  vector<long> x(N), y(N);
  rep(i, N) cin >> x[i] >> y[i];

  map<pair<long, long>, bool> mp;
  rep(i, N) mp[make_pair(x[i], y[i])] = true;

  long max_score = 0;

  rep(i, N) {
    long p = x[i] - x[0];
    long q = y[i] - y[0];
    if (p == 0 and q == 0) continue;
    long current_score = 0;
    rep(i, N) {
      if (mp[make_pair(x[i] + p, y[i] + q)]) current_score++;
    }
    max_score = max(max_score, current_score);
  }

  cout << N - max_score << endl;

  return 0;
}


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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	string S; cin >> S;
	reverse(ALL(S));
	lnt num = 0;
	lnt p[200010] = {};
	p[0] = 1;
	RANGE(i, 1, S.size()){
		p[i] = p[i-1]*10 % 2019;
	}
	map<lnt, lnt> mp;
	mp[0] = 1;
	REP(i, S.size()){
		lnt d = lnt(S[i] - '0');
		num += d*p[i];
		num %= 2019;
		mp[num]++;
	}
	lnt ans = 0;
	for(auto itr: mp){
		ans += itr.second*(itr.second-1)/2;
	}
	cout << ans << ln;
}

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

int main() {
  string a;
  cin >> a;
  vector<char> v(3), r = {'a', 'b', 'c'};
  v.at(0) = a.at(0);
  v.at(1) = a.at(1);
  v.at(2) = a.at(2);
  sort(v.begin(), v.end());
  if(v == r)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 1

#define KABE -1
#define OMOTE 0
#define URA 1

lli abs2(lli a){
	if(a>=0)return a;
	else return -a;
}

char data[100][100];
lli n,m;

void operation(lli nowI,lli nowJ){
	lli next[2][9]={{-1,-1,-1,0,0,0,1,1,1},{-1,0,1,-1,0,1,-1,0,1}};
	for(lli i=0;i<9;i++){
		lli nextI = nowI + next[0][i];
		lli nextJ = nowJ + next[1][i];
		if(data[nextI][nextJ]==KABE)continue;

		data[nextI][nextJ] = (data[nextI][nextJ]+1)%2;
	}
}

int main(){

	cin>>n>>m;
	/*
	for(lli i=0;i<100;i++){
		for(lli j=0;j<100;j++){
			if(i==0 || i==100 || j==0 || j==100){
				data[i][j]==KABE;
			}
			else data[i][j]=OMOTE;
		}
	}

	for(lli i=1;i<=n;i++){
		for(lli j=1;j<=m;j++){
			operation(i,j);
		}
	}
	*/

	lli ans = n*m;
	if(n!=1)ans -= (m-1)*2;
	else{ ans -= 2;}
	if(m!=1)ans -= (n-1)*2;
	else{ans -=2;}
	if(n==1 && m==1)cout<<1<<endl;
	else cout<<ans<<endl;




	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

const int maxN = 200005;
const int MOD = 2019;

class TaskD {
private:
	Debugger debugger;

public:
	void solveOne(int it){
		long long a , b , n;
		cin >> a >> b >> n;
		long long x = min(n, b-1);
		long long ans = (a*x)/b - a*(x/b);
		cout << ans << endl;
		return;

		for(long long x = 0; x <= n; x++){
			long long ans = (a*x)/b - a*(x/b);
			bug2(x, ans);
		}
	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	TaskD solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 3652
N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])

Measured memory_bytes: 147596
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;

int main()
{
	ll N;
	cin >> N;
	vec v(N);
	REP(i, N) {
		cin >> v[i];
	}

	ISORT(v);

	double ans = 0;
	REP(i, N) {
		// cout << ans << endl;
		ans += (double) (v[i] / pow(2, i + 1));
		if (i == N - 1) ans += (double)(v[i] / pow(2, i + 1));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main()
{
    int H,W;
    cin >> H >> W;
    while(H!=0||W!=0)
    {
        for(int v=1;v<=H;v++)
        {
            for(int h=1;h<=W;h++)
            {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
        cin >> H >> W;
    }
    return 0;
}



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

int main() {

  int A = 0;
  int B = 0;
  int C = 0;
  int D = 0;

  cin >> A;
  cin >> B;
  cin >> C;
  cin >> D;

  if ((A + B) > (C + D)) {
    cout << "Left" << endl;
  } else if ((A + B) == (C + D)) {
    cout << "Balanced" << endl;
  } else if ((A + B) < (C + D)) {
    cout << "Right" << endl;
  }
}



Measured memory_bytes: 3596
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
typedef pair<ll, ll>pii;
vector<int>ko[200000];
vector<vector<int> >gr[200000];
int dep[200000];
int las[200000];
int sec[200000];
int md[200000];
int cnt[200000];
ll p2[200001];
void dfs1(int node, int d)
{
	dep[node] = d;
	for (int i = 0; i < ko[node].size(); i++)dfs1(ko[node][i], d + 1);
}
int dfs2(int node)
{
	vector<int>v;
	for (int i = 0; i < ko[node].size(); i++)
	{
		int t = dfs2(ko[node][i]);
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	if (v.size() <= 1)sec[node] = -1;
	else sec[node] = v[1];
	if (v.size() == 0)return md[node] = dep[node];
	else return md[node] = v[0];
}
void dfs3(int node)
{
	gr[dep[node]][las[dep[node]]].push_back(gr[dep[node]].size());
	vector<int>z;
	gr[dep[node]].push_back(z);
	cnt[dep[node]]++;
	vector<int>keep;
	for (int j = dep[node] + 1; j <= sec[node]; j++)
	{
		//printf("   %d %d %d\n", j, las[j], gr[j].size());
		keep.push_back(las[j]);
		gr[j][las[j]].push_back(gr[j].size());
		las[j] = gr[j].size();
		gr[j].push_back(z);
	}
	for (int i = 0; i < ko[node].size(); i++)
	{
		dfs3(ko[node][i]);
	}
	for (int j = dep[node] + 1; j <= sec[node]; j++)
	{
		las[j] = keep[j - dep[node] - 1];
	}
}
pii calc(int n, int node)
{
	if (gr[n][node].size() == 0)return make_pair(1, 1);
	ll a = 1, b = 0, c = 0;
	for (int i = 0; i < gr[n][node].size(); i++)
	{
		pii z = calc(n, gr[n][node][i]);
		c = (c*(z.first + z.second) + b*z.second) % mod;
		b = (b*z.first + a*z.second) % mod;
		a = a*z.first%mod;
	}
	return make_pair((a + c) % mod, b);
}
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		int z;
		scanf("%d", &z);
		ko[z].push_back(i + 1);
	}
	num++;
	dfs1(0, 0);
	dfs2(0);
	for (int i = 0; i <= md[0]; i++)
	{
		vector<int>z;
		gr[i].push_back(z);
	}
	dfs3(0);
	p2[0] = 1;
	for (int i = 1; i <= num; i++)p2[i] = p2[i - 1] * 2 % mod;
	ll ans = 0;
	for (int i = 0; i <= md[0]; i++)ans = (ans + calc(i, 0).second*p2[num - cnt[i]]) % mod;
	printf("%lld\n", ans);
}

Measured memory_bytes: 71296
#include <bits/stdc++.h>
#define M 1000000007
#define INF 999999999
#define EPS 1e-9
#define pb push_back
#define mp make_pair
#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define MAX 1000005
#define fs first
#define sc second
#define N 7
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;
typedef vector <ll> vi;


ll a1[100005]={0};
ll a2[100005]={0};

int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
 cin.tie(0);
string str;
cin>>str;
for(int i=97;i<=122;i++)
{
  int f=0;
  for(int j=0;j<str.size();j++)
  {
    if(str[j]==char(i))
      f=1;
  }
  if(f==0)
  {
    cout<<char(i)<<endl;
    return 0;
  }
}

cout<<"None"<<endl;




return 0;

}

Measured memory_bytes: 512
#include<iostream>
#include<string>
//#include<cstdio>
using namespace std;
int main(){
    string str;
    cin >> str;
    int i;
    int count;
    count = 0;
    int situ;
    situ = 0;
//    char c;
//   c = ' ';
    for(i=0; i<str.length(); i++){

        if (situ == 0){
            //c = str[i];
            count++;
            situ = 1;
        }else if(situ == 1){
            if (str[i] == str[i-1]){
                if(i<str.length()-1){
                    count ++;
                    situ = 2;
                }
            }else{
                //c=str[i];
                count ++;
                situ = 1;
            }
        }else if(situ == 2){
            situ =0;
        }

    }
    cout << count  << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;
//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
 
 
 
 


ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}













bool compare(pi a,pi b){
     if(a.fi-a.se>b.fi-b.se)return  true;
     else if(a.fi-a.se==b.fi-b.se&&a.se<b.se)return true;
     return false;
}




const int N=1000005;
int pr[1000005];
int main()
{
     int n;
     cin>>n;
     ll a[n];
     for(int i=0;i<n;i++)cin>>a[i];
     ll mx=0,idx=-1;
     for(int i=0;i<n;i++){
          if(a[i]>mx){
               mx=a[i];idx=i;
          }
     }
     ll t=mx/2;
     ll b[n];
     for(int i=0;i<n;i++){
          b[i]=abs(a[i]-t);
     }
     int index=-1,mn=INT_MAX;
     for(int i=0;i<n;i++){
          if(i!=idx&&b[i]<mn){
               mn=b[i];index=i;
          }
     }
     cout<<mx<<" "<<a[index];

    

}




 
 

















Measured memory_bytes: 1792
/*
*          Name : chaitanya
*
*     Institute : ANITS,Visakhapatnam
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
const int N = 1000010;
using namespace std;
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

ll f[2000010];

ll lcm(ll a,ll b)
{
  return (a*b)/__gcd(a,b);
}
ll binpow(ll a, ll b) {
     ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
 
ll find_ncr(ll n, ll r)
{
    ll m1=max(r,n-r);
    ll i,j,s,d=1,k;
    s=1;
 
    for(i=m1+1;i<=n;i++)
    {
        s=((s%m)*(i%m))%m;
    }
 
    m1=min(r,n-r);
 
    for(i=1;i<=m1;i++)
    {
        k=binpow(i,m-2);
        d=((d%m)*(k%m))%m;
    }
 
    k=(s%m*(d%m))%m;
 
    return k;
}

int main()
{
  // int x = -1, y = 10000;
  // double z = 0.2;
  // string s2 = "beginner1010";
  // long long b = 1LL << 60;
    
  // // debug(x, y, z, s, b);
    
  // double aux = 1010.0;
  // string code = "code";
    
  // debug(code + "forces",-aux / 10 * 2.3);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n,k;
  cin >> n >> k;
  set <int> s;
  while (k--)
  {
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i)
    {
      int a;
      cin >> a;
      s.insert(a);
    }
  }
  cout << n-s.size();
  return 0;
}



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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  string s;
  cin >> s;
  for (size_t i = 0; i < s.size() - 1; ++i) {
    if (s[i] == s[i + 1]) {
      cout << i + 1 << " " << i + 2 << endl;
      return 0;
    }
    if (i != 0 && s[i - 1] == s[i + 1]) {
      cout << i << " " << i + 2 << endl;
      return 0;
    }
  }
  cout << -1 << " " << -1 << endl;
}


Measured memory_bytes: 512
n, m = map(int, input().split())
if m > 0:
    a = [int(input()) for i in range(m)]
    interval_max = 0
    for i in range(len(a)-1):
        if a[i+1] - a[i] == 1:
            print(0)
            exit()
        interval_max = max(interval_max, a[i+1] - a[i])
else:
    a = []
    interval_max = n
a.insert(0, 0)
a.append(n)
for i in range(len(a)-1):
    interval_max = max(interval_max, a[i+1] - a[i])

fibb = [0]*(max(interval_max+2, 3))
fibb[0] = fibb[1] = fibb[2] = 1
for i in range(3,interval_max+2):
    fibb[i] = (fibb[i-2] + fibb[i-1]) % 1000000007
sum_step = 1
# print(a)
if m == 0:
    sum_step = fibb[n+1]
else:
    for i in range(len(a)-1):
        if i == 0 or i == len(a)-2:
            sum_step *= fibb[a[i+1] - a[i]]
            # print(fibb[a[i+1] - a[i]])
        else:
            sum_step *= fibb[a[i+1] - a[i] - 1]
            # print(fibb[a[i+1] - a[i]] - 1)
        sum_step = sum_step % 1000000007
print(sum_step)
# print(step)

Measured memory_bytes: 7076
N = int(input())
countM = 0
countA = 0
countR = 0
countC = 0
countH = 0
for i in range(N):
    s = input()
    if (s[0] == "M"):
        countM += 1
        continue
    elif (s[0] == "A"):
        countA += 1
        continue
    elif (s[0] == "R"):
        countR += 1
        continue
    elif (s[0] == "C"):
        countC += 1
        continue
    elif (s[0] == "H"):
        countH += 1
print(countM*countA*countR+countM*countA*countC+countM*countA*countH+countM*countR*countC+countM*countR*countH+countM*countC*countH+countA*countR*countC+countA*countR*countH+countA*countC*countH+countR*countC*countH)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  vector<string> A(60);
  vector<int> X = { -1 ,-1 ,-1, 0, 0, 1, 1, 1};
  vector<int> Y = { -1 ,0, 1, -1, 1, -1, 0, 1};
  for(int i = 0;i<a;i++){
    cin >> A.at(i);
  }
  int m = 0;
  for(int i = 0;i<a;i++){
    for(int j = 0;j<b;j++){
      int count = 0;
      if(A.at(i).at(j) == '.'){
        for(int k = 0;k<8;k++){
          int dx = i + X.at(k);
          int dy = j + Y.at(k);
          if(dx >= 0 && dy >= 0 && dx < a && dy < b){
            if(A.at(dx).at(dy) == '#')
              count++;
          }
        }
        A.at(i).at(j) = '0' + count;
      }
    }
  }
  for(int i = 0;i<a;i++){
    cout << A.at(i) << 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 FOR(i, a, b) for(int i = a; i < (int)b; ++i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, k, g, m;
    cin >> n >> k >> g;
    m = g;
    rep (i, n - 1) {
        int a;
        cin >> a;
        g = gcd(g, a);
        m = max(m, a);
    }
    if (m >= k && k % g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}



Measured memory_bytes: 256
N = int(input())
stick = [ int(v) for v in input().split(" ") ]

def check_triangle(i, j, k):
  if i + j > k and j + k > i and i + k > j:
    return True
  return False

num = 0
candidate = []
for i in range(N):
  for j in range(i, N):
    for k in range(j, N):
      if i == j or j == k or i == k:
        continue
      if stick[i] == stick[j] or stick[j] == stick[k] or stick[i] == stick[k]:
        continue
      if check_triangle(stick[i],stick[j],stick[k]):
        #candidate.append([i+1,j+1,k+1])
        num += 1
      
#print(candidate)
print(num)


Measured memory_bytes: 9204
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

A,B,H,M = MI()
H_dig = 30*H + M/2
M_dig = 6*M
dif = H_dig-M_dig
dif = min(360-dif,dif)
rad = 2*math.pi*dif/360
dis = (A**2+B**2-2*A*B*math.cos(rad))**0.5
print(dis)


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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)
#define	INF (1<<29)
//536870912

#define	MOD 1000000007

int	main() {
	int I5=0;
	int I7=0;
	for (int i=0; i<3; i++) {
		int I;
		cin >>I;
		if (5==I)
			I5++;
		else if (7==I)
			I7++;
	}
	if ((2==I5)&&(1==I7))
		cout <<"YES" <<endl;
	else
		cout <<"NO" <<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define RS resize
#define CLR clear
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
using namespace std;

int main(){
	
	vector< int > w(10), k(10);
	
	REP(i, 10) cin >> w[i];
	REP(i, 10) cin >> k[i];
	
	sort(ALL(w), greater< int >());
	sort(ALL(k), greater< int >());
	
	cout << w[0] + w[1] + w[2] << " " << k[0] + k[1] + k[2] << endl;
	
	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
string s;
vector<int> fac[110];
map<string,int> m;
int calc(string s){
    if (m.count(s)) return m[s];
    int n=s.size(),ans=calc(s.substr(1,n-1));
    if (s[0]=='1') ans=inc(ans,ans);
    for (int L=1;L<=n;L++){
        int div=0;
        for (int i=0;i<fac[L].size();i++){
            int T=fac[L][i];
            string t;
            for (int j=0;j<T;j++) t+="1";
            for (int j=0;j<L;j++) if (s[j]=='0') t[j%T]='0';
            div=inc(div,calc(t));
        }
        ans=inc(ans,mul(div,calc(s.substr(L,n-L))));
    }
    return m[s]=ans;
}
int main()
{
    m[string()]=1;
    m[string("0")]=1;
    m[string("1")]=2;
    for (int i=1;i<=100;i++)
    for (int j=i+i;j<=100;j+=i)
        fac[j].push_back(i);
    cin>>s;
    cout<<calc(s)<<endl;
    return 0;
}

Measured memory_bytes: 7424
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] W = new int[N];
		int s = 1000;
		for(int i=0; i<N; i++) {
			W[i] = sc.nextInt();
		}
		sc.close();
		for(int j=0; j<N; j++) {
			int s1 = 0;
			int s2 = 0;
			for(int i=0; i<j; i++) {
				s1 += W[i];
			}
			for(int i=j; i<N; i++) {
				s2 += W[i];
			}
			if( Math.abs(s1-s2) < s) {
				s = Math.abs(s1-s2);
			}
		}
		System.out.println(s);
	}

}

Measured memory_bytes: 35988
x,y = map(int, input().split())

list1 = [1,3,5,7,8,10,12]
list2 = [4,6,9,11]

L = [list1,list2]

ans = "No"

for i in L:
  if x in i and y in i:
    ans = "Yes"

print(ans)

Measured memory_bytes: 8972
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (100000)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

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

/////////////////////////////////////////////////////////

void Main() {
  ll N; cin >> N;
  vector<ll> A(N);
  rep(i, 0, N) cin >> A[i];
  ll res = 0;
  rep(i, 0, N){
    ll x = A[i] / 2;
    A[i] -= 2 * x;
    res += x;
    if(i == N - 1) continue;
    ll y = min(A[i], A[i + 1]);
    A[i] -= y;
    A[i + 1] -= y;
    res += y;
  }
  cout << res << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long n;
  long long ans;
  cin>>n;
  long long arr[n]={0};
  for(long long i=1;i<100;i++)
  {
    for(long long j=1;j<100;j++)
    {
      for(long long k=1;k<100;k++)
      {
        ans=i*i+j*j+k*k+i*j+i*k+k*j;
        if(ans<=n)
        {
          	arr[ans-1]++;
        }
      }
    }
  }
  for(int i=0;i<n;i++)
  {
    cout<<arr[i]<<endl;
  }
    
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int dist[55][55];

int vy[4] = {-1,1,0,0};
int vx[4] = {0,0,-1,1};

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S;
  rep(i,H){
    string s;
    cin >> s;
    S.push_back(s);
  }

  rep(i,55) rep(j,55) dist[i][j] = -1;
  dist[0][0] = 0;

  queue<pair<int,int>> que;
  que.push(make_pair(0,0));
  while(!que.empty()){
    pair<int,int> p = que.front(); que.pop();
    rep(k,4){
      int ny = p.first + vy[k];
      int nx = p.second + vx[k];
      if(0<=nx&&nx<W&&0<=ny&&ny<H && S[ny][nx] != '#' && dist[ny][nx] == -1){
        dist[ny][nx] = dist[p.first][p.second] + 1;
        que.push(make_pair(ny,nx));
      }
    }
  }


  if(dist[H-1][W-1] == -1){
    cout << -1 << endl;
    return 0;
  }

  int kuro = 0;
  rep(i,H) rep(j,W) if(S[i][j] == '#') kuro++;

  int siro = dist[H-1][W-1]+1;

  int ret = H*W - siro - kuro;
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(){
  string s,t;
  cin >> s >> t;
  int counter = 0;
  for(int i = 0; i < 3; i++){
    if (s[i] == t[i]) counter++;
  }
  cout << counter << endl;
  return 0;
}

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

int main()
{
    string s;
    ll sum=0;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='o')
        {
            sum+=100;
        }
    }
    sum+=700;
    cout<<sum<<endl;
}


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

int ri() {
    int n;
    scanf("%d", &n);
    return n;
}

int main() {
	int n = ri();
	std::string s;
	std::cin >> s;
	for (auto &c : s) c -= 'A';
	for (auto &c : s) c = (c + n) % 26;
	for (auto &c : s) c += 'A';
	std::cout << s << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main()
{
	const int Max = 100;
	int matrix[Max][Max] = { 0 };
	int n, m, l;
	int temp;
	
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> m >> l;
		for (int j = 0; j < l; j++) {
			std::cin >> temp;
			matrix[m - 1][temp - 1] = 1;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			std::cout << matrix[i][j];
			if (j != n - 1) {
				std::cout << " ";
			}
		}
		std::cout << std::endl;
	}

	return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
string s,t;
int n;
int sa[2000005],bb[2000005],x[2000005],y[2000005];
bool cmp(int *y,int a,int b,int k){
	int a1=y[a],b1=y[b];
	int a2=a+k>=n?-1:y[a+k];
	int b2=b+k>=n?-1:y[b+k];
	return a1==b1&&a2==b2;
}
void init(){
	// 建立后缀数组
	int m=256;
	for(int i=0;i<m;i++)bb[i]=0;
	for(int i=0;i<n;i++)bb[x[i]=s[i]]++;
	for(int i=1;i<m;i++)bb[i]+=bb[i-1];
	for(int i=n-1;i>=0;i--)sa[--bb[x[i]]]=i;
	for(int k=1;k<=n;k<<=1){
		int p=0;
		for(int i=n-k;i<n;i++)y[p++]=i;
		for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
		for(int i=0;i<m;i++)bb[i]=0;
		for(int i=0;i<n;i++)bb[x[y[i]]]++;
		for(int i=1;i<m;i++)bb[i]+=bb[i-1];
		for(int i=n-1;i>=0;i--)sa[--bb[x[y[i]]]]=y[i];
		swap(x,y);
		m=1;x[sa[0]]=0;
		for(int i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],k)?m-1:m++;
//			x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?m-1:m++;
		if(m>=n)break;
	}
//	for(int i=0;i<n;i++)cout<<sa[i]<<' ';
}
int judge(int i){
	return t.compare(s.substr(i,min(n-i,(int)t.length())));
}
void calc(){
	int l=0,r=n,m;
	while(l<r-2){
		m=(l+r)/2;
		int res=judge(sa[m]);
		if(res==0){puts("1");return;}
		else if(res<0)r=m;
		else l=m;
	}
	for(int i=l;i<=r;i++){
		int res=judge(sa[i]);
		if(res==0){puts("1");return;}
	}
	puts("0");
}
int main(){
//	freopen("a.txt","r",stdin);
	ios::sync_with_stdio(false);cin.tie(0);
	int Q;cin>>s>>Q;n=s.length();
	init();
	while(Q--){
		cin>>t;
		calc();
	}
	return 0;
}


Measured memory_bytes: 27276
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <unistd.h>
#include <bits/stdc++.h>

#define pii pair<int,int>
#define REP(i, n) for (long long i = 0; i < (n); i++) 
using namespace std;

using Graph = vector<vector<int>>;

typedef long long ll;
static const ll INF = 1000000000000000000LL;
static const ll MOD = 1000000007;

//各種類のケーキには「綺麗さ」「おいしさ」「人気度」の 3 つの値をもつ
// 合計の絶対値を取る必要がある
// 

struct Cake
{
    ll beauty,taste,popular;
};

int main()
{
    ll N, M;
    cin >> N >> M;
    vector <ll> x(N);
    vector <ll> y(N);
    vector <ll> z(N);
    REP(i,N)
    {
        cin >> x[i] >> y[i] >> z[i];
    }

    ll res = 0;


    for(int bit = 0; bit < (1 << 3); ++bit)
    {
        vector <ll> sogo(N, 0);
        REP(i, N)
        {
            ll x_i,y_i,z_i;

            if(bit & (1 << 0))
            {
                sogo[i] += -x[i];
            }
            else
            {
                sogo[i] += x[i];
            }
            if(bit & (1 << 1))
            {
                sogo[i] += -y[i];
            }
            else
            {
                sogo[i] += y[i];
            }
            if(bit & (1 << 2))
            {
                sogo[i] += -z[i];
            }
            else
            {
                sogo[i] += z[i];
            }
        }
        sort(sogo.rbegin(), sogo.rend());
        ll tmp = 0;
        REP(i, M)
        {
            tmp += sogo[i];
        }
        res = max(res, tmp);
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]
# 累積 gcd（左と右両方）
left, right = [0] * (n + 1), [0] * (n + 1)
for i in range(n):
    left[i + 1] = gcd(left[i], a[i])
for i in reversed(range(0, n)):
    right[i] = gcd(right[i + 1], a[i])


# 累積
ans = 0
for i in range(n):
    l = left[i]
    r = right[i + 1]
    ans = max(ans, gcd(l, r))
print(ans)


Measured memory_bytes: 16140
a,b=map(int,input().split())
N=int(input())
s=[]
f=[]
h=0
for i in range(N):
    int_s,int_f=map(int,input().split())
    s.append(int_s)
    f.append(int_f)

for j in range(N):
    if s[j]<=a and b<=f[j]:
        h+=1
        break
    elif a<=s[j] and f[j]<=b:
        h+=1
        break
    elif s[j]<b<f[j]:
        h+=1
        break
    elif s[j]<a<f[j]:
        h+=1
        break
print(h)



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

typedef long long ll;

using namespace std;

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

    vector<ll> a(n);

    for (auto &i : a)
        cin >> i;

    for (ll i=n-1; i>=1; i--)
    {
        cout << a[i] << ' ';
    }
    cout << a[0];


    cout << endl;

    return 0;
}



Measured memory_bytes: 3088
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, X: int, Y: int):
    ret = X * min(N, K) + Y * max(0, N - K)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(N, K, X, Y)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	var n int
	fmt.Scan(&n)

	om := make(map[int]int)
	em := make(map[int]int)
	for i := 0; i < n/2; i++ {
		xo := scanInt()
		om[xo]++
		xe := scanInt()
		em[xe]++
	}

	type entry struct{ k, v int }
	ol := make([]entry, len(om))
	index := 0
	for k, v := range om {
		ol[index].k, ol[index].v = k, v
		index++
	}
	sort.Slice(ol, func(i, j int) bool { return ol[i].v > ol[j].v })

	el := make([]entry, len(em))
	index = 0
	for k, v := range em {
		el[index].k, el[index].v = k, v
		index++
	}
	sort.Slice(el, func(i, j int) bool { return el[i].v > el[j].v })

	if ol[0].k != el[0].k {
		fmt.Println(n - ol[0].v - el[0].v)
		return
	}

	if len(ol) == 1 {
		ol = append(ol, entry{-1, 0})
	}
	if len(el) == 1 {
		el = append(el, entry{-1, 0})
	}
	if v1, v2 := n-ol[0].v-el[1].v, n-ol[1].v-el[0].v; v1 < v2 {
		fmt.Println(v1)
	} else {
		fmt.Println(v2)
	}
}


Measured memory_bytes: 7544
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x) cout<<#x<<" = "<<(x)<<endl;
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  string s; cin >> s;
  string m = s.substr(5,2);
  string d = s.substr(8,2);
  int sum = stoi(m) * 30 + stoi(d);
  if (sum <= 4*30+30) COUT("Heisei");
  else COUT("TBD");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct medi { int x, y, c; };
const int INF = 1e9;

int main() {
    int n, s, t;
    cin >> n >> s >> t;
    vector<medi> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].x >> data[i].y >> data[i].c;
        data[i].x *= t; data[i].y *= s;
    }
    
    int n1 = n/2, n2 = n-n1;
    map<int, int> m1, m2;
    for (int bit = 1; bit < (1<<n1); bit++) {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < n1; i++) if (bit&(1<<i)) {
            a += data[i].x; b += data[i].y; c += data[i].c;
        }
        int res = a - b;
        if (m1.count(res)) m1[res] = min(m1[res], c);
        else m1[res] = c;
    }
    for (int bit = 1; bit < (1<<n2); bit++) {
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < n2; i++) if (bit&(1<<i)) {
            a += data[i+n1].x; b += data[i+n1].y; c += data[i+n1].c;
        }
        int res = a - b;
        if (m2.count(res)) m2[res] = min(m2[res], c);
        else m2[res] = c;
    }
    
    int ans = INF;
    for (const auto& e : m1) {
        int sum, cost; tie(sum, cost) = e;
        if (sum == 0) {
            ans = min(ans, cost);
        } else if (m2.count(-sum)) {
            cost += m2[-sum];
            ans = min(ans, cost);
        }
    }
    for (const auto& e : m2) {
        int sum, cost; tie(sum, cost) = e;
        if (sum == 0) ans = min(ans, cost);
    }
    
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

Measured memory_bytes: 384
s = int(input())
mod = 10 ** 9 + 7

#逆元
f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, s+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i) ) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

ans = 0
n = s // 3
for i in range(1, n+1):
    ans += comb(s - 3 * i + i - 1, i - 1)
    ans %= mod

print(ans)

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

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }

    vector<int> sum(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            sum[i] += a[0][j];
        }
        sum[i] += a[1][i];
        for (int k = i + 1; k < n; k++)
        {
            sum[i] += a[1][k];
        }
    }

    int ans = *max_element(begin(sum), end(sum));

    cout << ans;
}

Measured memory_bytes: 256