akhauriyash/Code-Regression huggingface dataset:
// https://atcoder.jp/contests/abc146/tasks/abc146_d

#include "algorithm"
#include "bitset"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define rep1(i, to) for (ll i = 1; i <= (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define unless(cond) if (!(cond))
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}

const ll INF = 1e18;

template <typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
    [[nodiscard]]
#elif defined(__GNUC__) && \
    (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4)
    __attribute__((warn_unused_result))
#endif
    FixPoint : private F {
 public:
  explicit constexpr FixPoint(F && f) noexcept : F(std::forward<F>(f)) {}

  template <typename... Args>
  constexpr decltype(auto) operator()(Args&&... args) const
#if !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 9
      noexcept(noexcept(
          F::operator()(std::declval<FixPoint>(), std::declval<Args>()...)))
#endif
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
static inline constexpr decltype(auto) makeFixPoint(F&& f) noexcept {
  return FixPoint<F>{std::forward<F>(f)};
}

void solve() {
  ll N;
  cin >> N;

  V<VPL> edge_list(N, VPL(0));

  VL colors(N - 1);

  rep(i, N - 1) {
    ll a, b;
    cin >> a >> b;
    a--, b--;

    edge_list[a].emplace_back(b, i);
    edge_list[b].emplace_back(a, i);
  }

  ll color_ct = 0;
  ll next_color = 1;

  auto dfs = makeFixPoint([&](auto f, ll u, ll p, ll color_p) -> void {
    ll next_color = 1;

    for (auto e : edge_list[u]) {
      ll v = e.fi;
      if (v == p) {
        continue;
      }

      if (next_color == color_p) next_color++;
      colors[e.se] = next_color;
      chmax(color_ct, next_color);

      f(v, u, next_color);
      next_color++;
    }
  });

  dfs(0, -1, -1);

  cout << color_ct << endl;
  rep(i, N - 1) { cout << colors[i] << endl; }
}

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif


Measured memory_bytes: 8704
N, K = map(int, input().split())
head = 0
foot = 0
ans = 0
for i in range(1, N+2):
    head += i-1
    foot += N - (i-1)
    if i >= K:
        ans = (ans + foot - head + 1) % 1000000007
    # print(i, head, foot, ans)
print(ans)

Measured memory_bytes: 9184
//make sure to make new file!
import java.io.*;
import java.util.*;

public class Main{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      StringTokenizer st = new StringTokenizer(f.readLine());
      
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      
      
      if(m >= n){
         out.println("unsafe");
      } else {
         out.println("safe");
      }
      
      
      
      
      
      
      out.close();
   }
   
      
}

Measured memory_bytes: 32568
#include <iostream>

using namespace std;

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (i % 2 == 0 && s[i] == 'R') continue;
    else if (i % 2 == 1 && s[i] == 'L') continue;
    else if (s[i] == 'U' || s[i] == 'D') continue;
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define all(vec) vec.begin(), vec.end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  int cards, gates; cin >> cards >> gates;
  vector<int> smaller(gates), bigger(gates);
  rep(i, gates) cin >> smaller[i], cin >> bigger[i];

  sort(all(smaller));
  sort(all(bigger));

  if(smaller[gates - 1] > bigger[0]) cout << 0 << endl;
  else cout << bigger[0] - smaller[gates - 1] + 1 << endl;
}

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

int main(){
	int m,nmin,nmax;
	while(cin>>m>>nmin>>nmax and m>0){
		int p[m]; rep(i,m) cin>>p[i];
		sort(p,p+m); reverse(p,p+m);

		int ans=nmin,gap=0;
		for(int n=nmin-1;n<nmax;n++){
			if(p[n]-p[n+1]>=gap){
				gap=p[n]-p[n+1];
				ans=n+1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}



Measured memory_bytes: 3156
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7; 

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF_INT (1<<30)
#define INF_LL (1ll<<62)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll now=1,H;

int main(){
    cin>>H;
    while(H>1){
        H/=2;
        now*=2;
    }
    out(now*2-1);

    
    
}

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

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define is insert
#define er erase

using namespace std;

const int MAX_N = 2e5 + 5;

const ll MOD = 1e9 + 7;

int solve();

#define TASK ""

int main()
{
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        //freopen(TASK".in", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    #endif // DEBUG
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

int n;

ll b[MAX_N];

vector<ll> a;

ll dp[MAX_N];
ll sum[MAX_N];

int solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
    }
    b[0] = -1;
    a.pb(-1);
    for (int i = 1; i <= n; ++i)
    {
        if (b[i] != b[i - 1])
        {
            a.pb(b[i]);
        }
    }
    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));
    dp[0] = 1;
    for (int i = 1; i < (int)a.size(); ++i)
    {
        dp[i] = (dp[i - 1] + sum[a[i]]) % MOD;
        sum[a[i]] = (sum[a[i]] + dp[i - 1]) % MOD;
    }
    cout << dp[(int)a.size() - 1] << '\n';
    return 0;
}





Measured memory_bytes: 6640
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
   int n,count=0,flag=0,i;
   cin>>n;
   int ara[n],a[n];
   for(int i=0;i<n;i++)
   {
       cin>>ara[i];
       a[i]=ara[i];
   }
   sort(a,a+n);
   for(i=0;i<n;i++)
   {
       if(ara[i]==a[n-1])
       {
           count++;
           if(count>1)
           {
               flag=1;
               break;
           }
       }
   }
   if(flag==1)
   {
       for(i=0;i<n;i++)
       cout<<a[n-1]<<endl;
   }
   else
   {
       for(i=0;i<n;i++)
       {
           if(ara[i]==a[n-1])
           cout<<a[n-2]<<endl;
           else cout<<a[n-1]<<endl;
       }
   }
}


Measured memory_bytes: 3200
n, q = map(int, input().split())
process = [input().split() for _ in range(n)]
#print(process)
time = 0
while process:
    p = process.pop(0)
    if int(p[1]) <= q:
        time += int(p[1])
        print(p[0], time)
    else:
        time += q
        process.append([p[0], int(p[1])-q])

Measured memory_bytes: 19688
require 'prime'
n=gets.to_i
a=gets.split.map(&:to_i)
l=[0]*1000001
a.each do |aa|
  l[aa]+=1
end
s=0
Prime.each(1000000).to_a.each do |i|
  x=i
  c=0
  while x<=1000000
    if l[x]>0
      c+=l[x]
    end
    x+=i
  end
  s=c if s<c
end
#s=l.max
if s<=1
  puts "pairwise coprime"
elsif s==n
  puts "not coprime"
else
  puts "setwise coprime"
end


Measured memory_bytes: 103648
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
	int x;
	vector<int> a;
	for (int i = 0; i < 10; i++){
		scanf("%d", &x);
		a.push_back(x);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < 3; i++){
		printf("%d\n", a[9 - i]);
	}

	return 0;
}

Measured memory_bytes: 2736
class BinaryIndexedTree:
  def __init__(self, size):
    self.data = [0] * (size+1)
    self.size = size
  
  def add(self, i, w):
    while i <= self.size:
      self.data[i] += w
      i += i & -i

  def sum(self, i):
    result = 0
    while i > 0:
      result += self.data[i]
      i -= i & -i
    return result

from bisect import bisect

N,K = map(int, input().split())

A = [int(input()) for i in range(N)]

t = 0
B = [t]
for a in A:
  t += a - K
  B.append(t)

temp = sorted(B)
C = [bisect(temp, b) for b in B]

result = 0
bit = BinaryIndexedTree(N+1)

for c in C:
  result += bit.sum(c)
  bit.add(c,1)

print(result)

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

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    long long int sum = 0;
    for(int i = 1; i < n+1; i++){
        int digit = 0;
        int tmp = i;
        for(int j = 0; j < 5; j++){
            digit += tmp % 10;
            tmp = tmp / 10;
        }
        if(a <= digit && digit <= b){
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) {
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int main() {
  int L, R, d ;	cin>>L>>R>>d;
  int ans = 0;
  for(int i = L; i <= R; i++) {
    if(i % d ==	0) ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3208
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ss substr
typedef long long ll ;
typedef long double ld ;
typedef pair<ll, ll> pairs ;
typedef map<ll,ll> mapi ;
typedef map<string,string> maps ;


int main()
{
  //freopen("lifeguards.out", "w", stdout) ;
  //freopen("lifeguards.in", "r", stdin) ;
  ios_base::sync_with_stdio(0) ;
  cin.tie(NULL) ;
  cout.tie(NULL) ;
 
 //int t ; cin >> t ; while(t--){} 
 
 int a , b ; cin >> a >> b ;
 if ( a <= 9 && b <= 9 ) cout << a*b ;
 else cout << -1 ; 
   
 }

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;

int main(){

	int n, m, a[30], b[30], c[10], ans=0;
	cin >> n >> m;
	for(int i=0; i<m; i++){
		cin >> a[i] >> b[i];
	}
	for(int i=0; i<n; i++){
		c[i]=i+1;
	}
	bool flag;
	do{
		if(c[0]==1){
			for(int i=0; i<n-1; i++){
				for(int j=0; j<m; j++){
					flag=false;
					if(c[i]==a[j] && c[i+1]==b[j] || c[i]==b[j] && c[i+1]==a[j]){
						flag=true;
						break;
					}
				}
				if(!flag){
					break;
				}
			}
			if(flag){
				ans++;
			}
		}
	}while(next_permutation(c, c+n));
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
 	int b;
 	scanf("%d",&b); 
 	printf("%d",a[b-1]);
 } 

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> m(N);
  for (int i=0; i<N; i++) cin >> m.at(i);
  int total=0, minm=-1;
  for (int i=0; i<N; i++) {
    total += m.at(i);
    if (minm == -1 || minm > m.at(i)) minm = m.at(i);
  }
  cout << N + (X-total) / minm << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pii              pair <int,int>
#define DEBUG(x) cerr << '>' << #x << ':' << x << endl;
typedef long long ll;
//#pragma comment(linker, "/STACK:667772160")
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))

const double eps=1e-9;
const int MOD=1e9+7;
const int N=1e5+30;
const int inf = 1e17+995;

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int mem[N][4],cost[N][3],n;
int dp(int idx,int cur){
    if(idx==n)
        return 0;
    int &ret=mem[idx][cur];
    if(~ret)
        return ret;
    for (int i = 0; i < 3; ++i) {
        if(cur!=i)
            ret=max(ret,cost[idx][i]+dp(idx+1,i));
    }
    return ret;
}
int32_t main() {
boostIO();
cin>>n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin>>cost[i][j];
        }
    }
    memset(mem,-1, sizeof(mem));
    int ans=dp(0,3);
    cout<<ans;
}

Measured memory_bytes: 13568
#include <bits/stdc++.h>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define P(a,b) make_pair(a,b)

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;
const ll Lmax=ll(1e18);
const int Nmax=2e5+1;
const int Nd=61;
const int INF=1e5;
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(){
  ll n,m;
  string s,t;
  cin>>n>>m>>s>>t;
  ll x=lcm(n,m);


  ll n0=n/gcd(n,m),m0=m/gcd(n,m);

  rep(i,gcd(n,m)){
    ll a=i*n0;
    ll b=i*m0;
    if(s[a]!=t[b]){
      cout<<-1<<endl;
      return 0;
    }
  }

  cout<<x<<endl;
  return 0;





  return 0;
}


Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
 
 
int main(){
  string s;
  cin >> s;
  if(s.length() < 26){
    vector<int> alpha(26, 0);
    for(int i=0; i<s.length(); i++){
      alpha[s[i]-'a']++;
    }
    for(int i=0; i<26; i++){
      if(alpha[i] == 0){
        cout << s << (char)(i+'a') << endl;
        return 0;
      }
    }
  }else{
    string ans = "";
    for(int i=25; i>=1; i--){
      if(s[i] > s[i-1]){
        char tmp;
        for(int j=25; j>=i; j--){
          if(s[i-1] < s[j]){
            tmp = s[j];
            break;
          }
        }
        ans = s.substr(0, i-1) + tmp;
        break;
      }
    }
    if(ans == ""){
      cout << -1 << endl;
    }else{
      cout << ans << endl;
    }
  }
  return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[505][505];

int hoge(int a,int b) {
	int x=abs(a-b);
	int i;
	FOR(i,10) if(x&(1<<i)) return i+1;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	
	FOR(y,N) {
		for(x=y+1;x<N;x++) {
			cout<<hoge(x,y)<<" ";
		}
		cout<<endl;
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
#include <algorithm>
#include <iomanip>
using namespace std;

int main(){
  int N,  ans = 0 ;
  cin >> N ;
  double answer = N * 3.141592 * 2 ;
  cout << answer << endl ;
  return 0 ;
}  

Measured memory_bytes: 3784
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    int n, k;
    Edges[] g;

    long MOD = (long) 1e9 + 7;

    void run() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        g = new Edges[n];

        for (int i = 0; i < n; i++) g[i] = new Edges();

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
            g[u].add(v);
            g[v].add(u);
        }

        System.out.println(k * solve(0, new boolean[n]) % MOD);
    }

    long solve(int idx, boolean[] visited) {
        visited[idx] = true;
        long ret = 1;

        long useCnt = idx == 0 ? k - 1 : k - 2;

        for (int next: g[idx]) if (!visited[next]) {
            ret = ret * useCnt % MOD;
            useCnt--;
        }
        for (int next: g[idx]) if (!visited[next]) {
            ret = ret * solve(next, visited) % MOD;
        }
        return ret;
    }

    class Edges extends ArrayList<Integer> {}

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 120824
#include <stdio.h>

int main(){
	char S[5];
	char s,s2;
	int cou=0,cou2=0,flag=0;;
	scanf("%s",S);
	s=S[0];
	for(int i=0;i<4;i++){
		if(s!=S[i] && flag==0){
			s2=S[i];
			flag++;
		}
		if(s==S[i])cou++;
		else if(s2==S[i])cou2++;
	}

	if(cou==2 && cou2 ==2)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#![allow(non_snake_case)]

use std::cmp::min;
use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let vec: Vec<_> = (0..=N).map(|_| read::<u64>()).collect();
    if N == 0 && vec[0] == 1 {
        println!("1");
        return;
    }
    if vec[0] != 0 {
        println!("-1");
        return;
    }
    let mut before = 1;
    for &v in &vec {
        if v > before {
            println!("-1");
            return;
        }
        before -= v;
        before *= 2;
    }
    let mut sum: u64 = vec.iter().sum();
    let mut ans: u64 = 1;
    let mut now_ver: u64 = 1;
    for &v in vec.iter().skip(1) {
        now_ver = min(now_ver.saturating_mul(2), sum);
        ans += now_ver;
        now_ver -= v;
        sum -= v;
    }
    println!("{}", ans)
}


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

#define     bip(a)         __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front ///for list
#define     mp             make_pair
#define     is             insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))

///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));

int main()
{
    string str;
    cin>>str;
    for(int i=0;i<str.length();i++){
        if(str[i]=='?')str[i]='D';
    }
    cout<<str<<endl;
}




Measured memory_bytes: 3752
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
   		char[] a = sc.next().toCharArray();
    	char[] b = sc.next().toCharArray();
    	char[] c = sc.next().toCharArray();	
		System.out.print(a[0]);
		System.out.print(b[1]);
		System.out.print(c[2]);

    }
}

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

#define int long long
#define endl "\n"
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);


main(){
	FIO
	int n;
	cin>>n;
	if(n<30){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
	}
}

Measured memory_bytes: 3656
n, m = map(int, input().split())
stairs = [i for i in range(1, n+1)]
a = [0 for _ in range(m)]
for i in range(m):
  a[i] = int(input())
a = set(a)
  
dp = [0] * (n + 1)
dp[0] = 1

for i in range(1, n+1):
  if i in a:
    continue
  dp[i] = dp[i] + dp[i-1]
  if i > 1:
    dp[i] = dp[i] + dp[i-2]

print(dp[n] % 1000000007)

Measured memory_bytes: 466584
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,ls[30],mx1,mx2,x[370][30],c[30],ans[370][30],a,la,val,mi[30];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=26;i++)scanf("%d",&c[i]),ls[i]=0,mi[i]=c[i]*2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=26;j++)
        {
            scanf("%d",&x[i][j]);
        }
    }
    for(int st=1;st<=26;st++)
    {
        for(int i=1;i<=26;i++)ls[i]=0;
        ls[st]=1;
        ans[1][st]=st;
        for(int i=2;i<=n;i++)
        {
            mx1=0,mx2=1;
            for(int j=1;j<=26;j++)
            {
                int k=((i-ls[j])*c[j])+x[i][j];
                if(mx1<k)mx1=k,mx2=j;
                else if(mx1==k)if(ls[j]<ls[mx2])mx2=j;
            }
            //printf("[%d]",mx1);
            ls[mx2]=i;
            ans[i][st]=mx2;
            mi[st]+=mx1;
        }
    }
    int p1=INT_MIN,p2=1;
    for(int i=1;i<=n;i++)if(p1<mi[i])p1=mi[i],p2=i;
    for(int i=1;i<=n;i++)printf("%d\n",ans[i][p2]);
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

template<uint32_t mod>
struct ModInt{
	uint32_t a;
	ModInt& s(uint32_t vv){
		a=vv<mod?vv:vv-mod;
		return *this;
	}

	ModInt(int64_t x=0){s(x%mod+mod);}

	ModInt& operator+=(const ModInt &x){return s(a+x.a);}
	ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);}
	ModInt& operator*=(const ModInt &x){
		a=uint64_t(a)*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;}
	ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;}
	ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;}
	ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;}
	bool operator==(const ModInt &x)const{return a==x.a;}
	bool operator!=(const ModInt &x)const{return a!=x.a;}
	bool operator<(const ModInt &x)const{return a<x.a;}

	ModInt operator-()const{return ModInt()-*this;}
	ModInt pow(int64_t n)const{
		ModInt res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}

	ModInt inv()const{return pow(mod-2);}
};

template<uint32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<uint32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<1000000007>;
//using mint=ModInt<998244353>;

int N;
int A[333333];

signed main(){
	cin>>N;
	rep(i,N)cin>>A[i];
	mint ans=0;
	rep(k,60){
		int cnt=0;
		rep(i,N)if(A[i]>>k&1)cnt++;
		ans+=mint(1ll<<k)*cnt*(N-cnt);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

int main(){
  
  int n;
  cin>>n;
  int a[n];
  int min_v=100'000;
  int max_v=0;
  REP(i,n){
    cin>>a[i];
    min_v = min(min_v, a[i]);
    max_v = max(max_v, a[i]);
  }
  if(max_v-min_v>1){
    cout<<"No"<<endl;
    return 0;
  }
  //max_v-min_vは、0か1
  if(max_v==min_v){
    if(1<=max_v && max_v<=n/2){
      cout<<"Yes"<<endl;
    }else if(max_v==n-1){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
    return 0;
  }
  //以下max_v-min_vは、1
  int p=0;//唯一の色の帽子をかぶっている猫の数
  int q;
  REP(i,n){
    if(a[i]==min_v){
      p++;
    }
  }
  q = max_v - p;
  if(q<=0){
    cout<<"No"<<endl;
    return 0;
  }
  if(n-p>=2*q){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


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

int solve(long long n) {
    if (n == 1) {
        return 0;
    }
    vector<int> f;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n > 1) f.push_back(n);

    int ans = 0;
    int i = 0;
    while (i < f.size()) {
        int j = i + 1;
        while (j < f.size() && f.at(j) == f.at(i)) j++;
        int count = j - i;
        i = j;
        int sum = 0;
        for (int x = 1; count >= sum + x; x++, ans++) sum += x;
    }
    return ans;
}

int main() {
    long long n;
    cin >> n;
    cout << solve(n) << endl;
}

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(si, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}


vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find
// Find()
int parent[N], ran[N];

int find(int x)
{
    if(parent[x]==x)return x;
    else return parent[x]=find(parent[x]);
}
// Union()
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;

    if(ran[x]<ran[y])
        parent[x]=y;
    else{
        parent[y]=x;
        if(ran[x]==ran[y])ran[x]++;
    }
}

// Main Code

int main()
{
  string s;
  cin>>s;
  if(s.length()%2 == 0)
  {
    int j =s.length();
    while(j > 0)
    {
      j = j -2;
      bool f = true;
      rep(i, 0, j/2)
      {
        if(s[i] != s[i+(j/2)])
        {
          f = false;
          break;
        }
      }
      if(f){
      cout<<j<<endl;
      return 0;
    }
    }
  }
  else
  {
    int j = s.length()+1;
    while(j > 0)
    {
      j = j -2;
      bool f = true;
      rep(i, 0, j/2)
      {
        if(s[i] != s[i+(j/2)])
        {
          f = false;
          break;
        }
      }
      if(f){
      cout<<j<<endl;
      return 0;
    }
    }
  }
  return 0;
}


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

int top, N[1000];

void push(int);
int pop(void);

int main(){
  int x,y;
  char n[100];
  top = 0;

  while(scanf("%s", n) != EOF){
    if(n[0] == '+'){
      x = pop();
      y = pop();
      push(x + y);
    }
    else if(n[0] == '-'){
      y = pop();
      x = pop();
      push(x - y);
    }
    else if(n[0] == '*'){
      x = pop();
      y = pop();
      push(x * y);
    }
    else{
      push(atoi(n));
    }
  }

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

  return 0;
}


void push(int x){
  N[++top] = x;
}

int pop(){
  top--;
  return N[top + 1];
}



Measured memory_bytes: 2064
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

ll gcd(ll a, ll b){
  if(b<a) swap(a, b);
  ll r = a % b;
  if(r==0) return b;
  while(r!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
ll lcm(ll a, ll b){
  return (a*b)/gcd(a,b);
}
int main(int argc, char const *argv[]) {
  ll n, m;std::cin >> n >> m;
  vll a(n);
  re(i, n){
    std::cin >> a[i];
    a[i] /= 2;
  }
  ll l = 1;
  re(i, n){
    l = lcm(l, a[i]);
    if(l>m||l>1000000000){
      std::cout << 0 << '\n';
      return 0;
    }
  }
  ll x = l;
  ll t = 0;
  while(x%2==0) x/=2, t++;
  re(i, n){
    ll tmp = 0;
    while(a[i]%2==0) a[i]/=2, tmp++;
    if(tmp!=t){
      std::cout << 0 << '\n';
      return 0;
    }
  }
  ll ans = m/l;
  if(ans%2==0) std::cout << ans/2 << '\n';
  else std::cout << ans/2+1 << '\n';
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
int main(){
    double a,b,h,m,pi = 3.141592653589793;
    cin>>a>>b>>h>>m;
    cout<<setprecision(10)<<sqrt(a*a+b*b-2*a*b*cos((h/12+m/60/12)*2*pi-m/60*2*pi))<<"\n";
}

Measured memory_bytes: 4188
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;

int main(void) {
  char inp[20];
  scanf("%s",inp);
  string str(inp);
  string ans;

  for (size_t i = 0; i < str.size(); i++) {
    if (str[i] == 'B'){
      if(! ans.empty()){
       ans.pop_back();
      }
    }else{
      ans += str[i];
    }

  }
  printf("%s\n",ans.c_str());
  return 0;
}


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

using namespace std;

void b_fizzbuzz_sum(void) {
	long long n;
	cin >> n;
	long long sum;
	sum = n * (n + 1) / 2;
	for (int i = 1; i <= n; i++) {
		if ((i % 3 == 0) || (i % 5 == 0)) {
			sum -= i;
		}
	}
	cout << sum << endl;
}

int main()
{
    b_fizzbuzz_sum();

    return 0;
}

Measured memory_bytes: 3604
use proconio::input;

#[allow(unused_imports)]
use std::collections::HashSet;

use std::cmp;


fn main() {
    input! {
        n: usize,
        k: usize,
    }
    solve(n, k);
}

fn prepare(m: usize, k: usize, p :u64) -> Vec<Vec<u64>> {
    let mut v : Vec<Vec<u64>> = Vec::<Vec<u64>>::with_capacity(m + 1);
    let v0 : Vec<u64> = vec![1; 1];
    v.push(v0);
    for i in 1..m+1 {
        
       let mut vi : Vec<u64>;
        if i < 2 * k {
            let jmax = cmp::min(i, k);
            vi = vec![0; jmax+1];
            for j in 0..jmax+1 {
                vi[j] = 
                if j == 0 || j==i {
                    1
                } else {
                    (v[i-1][j-1] + v[i-1][j]) % p
                };
                if i-j <= jmax {
                    vi[i-j] = vi[j];
                }
            }
            v.push(vi);
        } else {
            vi = vec![0; k+1];
            for j in 0..k+1 {
                vi[j] = 
                if j == 0 || j==i {
                    1
                } else {
                    (v[i-1][j-1] + v[i-1][j]) % p
                };
            }
            v.push(vi);
        }
    }
    return v;
}

fn solve(n: usize, k: usize) {
    let p : u64 = (10u32.pow(9u32) + 7) as u64;

    // 1. Calculate values of combinations
    let m = cmp::max(k-1, n-k+1);
    let c = prepare(m, k, p);

    // 2. Calculate possible ways
    for i in 1..k+1 {
        let b = c[k-1][i-1];
        let r = if i > n-k+1 { 
            0
        } else {
            c[n-k+1][i]
        };
        let t = b * r % p;
        println!("{}", t);
    }
}


Measured memory_bytes: 17756
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] A = new int[N];
		int sum = 0, ans = 0;
		for(int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
			sum += A[i];
		}
		Set<Integer> cd = new HashSet<>();
		for(int i = 1; i <= Math.sqrt(sum); i++)
			if(sum % i == 0) {
				cd.add(i);
				cd.add(sum/i);
			}
		for(int i : cd) {
			int min = Integer.MAX_VALUE;
			int[] B = new int[N];
			for(int j = 0; j < N; j++)
				B[j] = A[j] % i;
			Arrays.sort(B);
			int[] S = new int[N+1];
			for(int j = 0; j < N; j++)
				S[j+1] = S[j] + B[j];
			if(S[N-S[N]/i] <= K)
				ans = Math.max(ans, i);
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 29436
import sys

A = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

*B, = map(int, input().split())
A[0][0] = B[0]
A[0][1] = B[1]
A[0][2] = B[2]

*B, = map(int, input().split())
A[1][0] = B[0]
A[1][1] = B[1]
A[1][2] = B[2]

*B, = map(int, input().split())
A[2][0] = B[0]
A[2][1] = B[1]
A[2][2] = B[2]

N = int(input())
for _ in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if A[i][j]==b:
                A[i][j] = -1


#斜めのチェック
if A[0][0]==-1 and A[1][1]==-1 and A[2][2]==-1:
    print("Yes")
    sys.exit()


if A[0][2]==-1 and A[1][1]==-1 and A[2][0]==-1:
    print("Yes")
    sys.exit()

#縦のチェック
for i in range(3):
    if A[0][i]==-1 and A[1][i]==-1 and A[2][i]==-1:
        print("Yes")
        sys.exit()

for i in range(3):
    if A[i][0]==-1 and A[i][1]==-1 and A[i][2]==-1:
        print("Yes")
        sys.exit()
print("No")


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

int l, r, d;

int main(void)
{
    cin >> l >> r >> d;

    int cnt = 0;
    for (int i = l; i <= r; i++){
        if (i%d==0){
            cnt++;
        }
    }
    
    
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>

int tmp[100000];

int main( void ) {
    int N;
    int A[100000];

    int i, k;

    scanf("%d", &N);
    for (i=0;i<N;++i) {
        scanf("%d", &A[i]);
        tmp[ A[i]-1 ] = i + 1;
    }
    for (i=0;i<N;++i) {
        printf("%d ", tmp[i] );
    }

    return 0;
}

Measured memory_bytes: 1536
from bisect import insort_left
from fractions import gcd
N,X=[int(a) for a in input().split(" ")]
xs = sorted([int(a) for a in input().split(" ")])
insort_left(xs, X)
intervals = [a-b for a, b in zip(xs[1:],xs[:-1])]
curr = intervals[0]
for i in intervals:
    curr = gcd(curr, i)
print(curr)

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

using namespace std;
const int N = 200005;
const int mod = 1000000007;
typedef long long LL;
int a[N], sum = 0, n;
LL tot = 0;
int main()
{
 	cin >> n;
 	for(int i = 1; i <= n; i ++)
 	{
		cin >> a[i];
		tot += a[i];
 	}
 	for(int i = 1 ; i <= n; i ++)
 	{
 		tot -= a[i];
 		sum = (sum + int((tot % mod * a[i]) % mod)) % mod;
	}
	cout << sum;
	 return 0;
}

Measured memory_bytes: 4420
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

void printVector(vector<int> vec);

int main() {
	int H, N;
	cin >> H >> N;
	int totalDamage = 0;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		totalDamage += A;
	}
	if (totalDamage >= H) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

void printVector(vector<int> vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	string d;
	int m;
	int count=0;
	int h[100];
	
	while(cin>>d){
		cin>>m;
		if(d[0]=='-')
			break;
		for(int i=0;d[i]!='\0';i++)
			count++;
		for(int i=0;i<m;i++){
			cin>>h[i];
			string left = d.substr(0, h[i]);
			string right=d.substr(h[i],count);
			d=right+left;
		}
		cout<<d<<endl;
	}
} 
	
	
	

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>

#include <bitset>
#include <cassert>
#include <queue>
#include <random>
#include <stack>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n;i++)
#define repf(i, a, b) for (int i = (int)a; i < (int)b;i++)
#define repv(x, arr) for (auto& x:arr)
#define all(v) (v).begin(), (v).end()
#define vec(name, num) vector<ll> name((num), 0);
#define mp(a,b) make_pair(a,b)
#define op(i) cout << (i) << endl;
#define F first
#define S second

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;

const ll mod = 1e9 + 7;


int main(){
    map<ll, ll> cnt;
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
        cnt[A[i]]++;
    }
    ll ans = 0;
    ll two = 0;
    for (auto itr = cnt.begin(); itr != cnt.end();itr++){
        pll p = *itr;
        ans += p.S -1;
        if (p.S%2==0){
            two++;
        }
    }
    ans += two%2;
    cout << N-ans << endl;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define debug(x) cout << #x" = " << x << endl;
#define pp(x,y) cout << "pp: " << x << " " << y << endl;
#define rank __RAnK
inline ll read(){
	register ll x=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc())if(c=='-')f=-1;
	for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
	return x*f;
}
#define rd read
void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
void writeln(ll x){write(x);puts("");}
const int maxn = 524288+233;
const int g = 5,mod = 924844033; 
int qpow(int a,int b){
	int ans = 1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)ans=1ll*ans*a%mod;
	return ans;
}

struct FFT{
	int n,logn,rev[maxn];
	void init(int len){
		n = 1;logn=0;
		while(n < len) n<<=1,logn++;
		Rep(i,1,n) rev[i] = (rev[i>>1] >> 1) | ((i&1) << (logn-1));
	}
	void fft(int a[],int flag){
		rep(i,0,n) a[i]=(a[i]%mod+mod)%mod;
		rep(i,0,n) if(rev[i]<i) swap(a[i],a[rev[i]]);
		for(int i=1;i<n;i<<=1){
			int wn= qpow(g,(mod-1)/(i<<1));
			for(int j=0;j<n;j+=(i<<1)){
				int w=1;
				for(int k=0;k<i;++k,w=1ll*w*wn%mod){
					int x=a[j+k],y=1ll*w*a[i+j+k]%mod;
					a[j+k]=(x+y)%mod;
					a[i+j+k]=(x-y+mod)%mod;
				}
			}
		}if(flag==1) return ;
		reverse(a+1,a+n);
		ll inv=qpow(n,mod-2);
		Rep(i,0,n)a[i]=1ll*a[i]*inv%mod;
	}
}wzp;
vector<int> edge[maxn];
int n;
int size[maxn],a[maxn],b[maxn];
int fac[maxn],ifac[maxn];
void dfs(int u,int fa){
	size[u] = 1;
	for(auto v:edge[u]){
		if(v==fa) continue;
		dfs(v,u);
		a[size[v]]--;
		size[u] += size[v];
	}
	if(u!=1)a[n-size[u]]--;
}
int main(){
	n = rd();
	rep(i,1,n){
		int a = rd(),b = rd();
		edge[a] . push_back(b);
		edge[b] . push_back(a);
	}
	mem(a,0);dfs(1,0);a[n] = n;
	fac[0] = 1;
	Rep(i,1,n) fac[i] = 1ll * fac[i-1] * i % mod;
	ifac[n] = qpow(fac[n],mod-2);
	Dep(i,n-1,0)ifac[i] = 1ll * ifac[i+1] * (i+1) % mod;
	Rep(i,1,n) a[i] = 1ll * a[i] * fac[i] % mod;
	Rep(i,0,n) b[i] = ifac[i];
	reverse(b+0,b+1+n);
	wzp.init(2*(n+1));
	wzp.fft(a,1);
	wzp.fft(b,1);
	rep(i,0,wzp.n) a[i]=1ll*a[i]*b[i]%mod;
	wzp.fft(a,-1);
	Rep(i,1,n) a[i] = 1ll * a[i+n] * ifac[i] % mod;
	Rep(i,1,n) writeln(a[i]);

/*	k=1的时候,(1..n) a[i] * b[i-1]
	i-j=k
	i+(n-j)=n+k */
	
	return 0;
}
/*
For i = k to n
a[i] * i! 
-----------
k! * (n-k)!
For(i=k to n)

---
k!

*/

Measured memory_bytes: 42368
s = list(input())
ans = 10**5
for i in set(list(s)):
  q = s[:]
  cnte = 0
  while len(set(q)) > 1:
    new = [""]*(len(q)-1)
    for j in range(len(q)-1):
      if q[j] == i or q[j+1] == i:
        new[j] = i
      else:
        new[j] = q[j]
    q = new
    cnte += 1
  if cnte < ans:
    ans = cnte
print(ans)

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

vector<ll> ans;

void dfs(int d, ll now){
  ans.push_back(now);

  if(d==10) return;

  for(int j = -1; j<=1; j++){
    int add = (now % 10) + j;
    if(add>=0 && add <= 9) dfs(d+1, now*10+add);
  }
}
int main(){
  for(int i=1; i<=9; i++){
    dfs(1,(ll)i);
  }
  sort(ans.begin(),ans.end());
  int k; cin>>k;
  cout<<ans[k-1]<<endl;
}


Measured memory_bytes: 5168
a = int(input())  # 500
b = int(input())  # 100
c = int(input())  # 50
x = int(input())  # 500 * A + 100 * B + 50 * C

result = []
for a_i in range(a+1):
  for b_i in range(b+1):
    for c_i in range(c+1):
      x_tmp = x - 500 * a_i - 100 * b_i - 50 * c_i
      if x_tmp == 0:
      	result.append([a_i, b_i, c_i])
print(len(result))


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

int main() {
  int N,i,j,k,l=0;
  cin >> N;
  
  for(i=0;i<(N+1)/2;i++){
    k=0;
    for(j=1;j<=(2*i+1);j++){
      if((2*i+1)%j==0){
        k++;
      }
    }
    if(k==8){
      l++;
    }
  }
  cout << l << endl;
}



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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define int ll
#define pb push_back
#define lb lower_bound

void pre() {
}

void solve() {
//    int n;
//    cin >> n;
//    vi a(n);
//    for (auto &i:a)cin >> i;
    int h, w;
    cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1;
        return;
    }
    cout << (h * w + 1) / 2;
}

signed main() {
    pre();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256