akhauriyash/Code-Regression huggingface dataset:
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    static void solve() {
        String s = nextString();

        String ans = s.replace("2017", "2018");
        out.println(ans);
    }

    static PrintWriter out;
    static Scanner sc;

    static int[][] newIntArray(int h, int w, int value) {
        int[][] ret = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                ret[i][j] = value;
            }
        }
        return ret;
    }

    static int nextInt() {
        return Integer.parseInt(sc.next());
    }

    static long nextLong() {
        return Long.parseLong(sc.next());
    }

    static String nextString() {
        return sc.next();
    }

    static int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    static List<Integer> nextIntList(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(nextInt());
        }
        return list;
    }

    static List<Long> nextLongList(int n) {
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(nextLong());
        }
        return list;
    }

    static char[][] nextCharArray(int h, int w) {
        char[][] c = new char[h][w];
        for (int i = 0; i < h; i++) {
            String str = nextString();
            for (int j = 0; j < w; j++) {
                c[i][j] = str.charAt(j);
            }
        }
        return c;
    }

    static <T extends Comparable<? super T>> void sort(List<T> list) {
        Collections.sort(list);
    }

    // greatest common divisor
    static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    // baseのn乗を計算を返す
    static int pow(int base, int n) {
        int ret = 1;
        for (int i = 0; i < n; i++) {
            ret *= base;
        }
        return ret;
    }

    // return n^k mod m
    static long powMod(long n, long k, long m) {
        if (k == 0) {
            return 1;
        } else if (k % 2 == 1) {
            return powMod(n, k - 1, m) * n % m;
        } else {
            long tmp = powMod(n, k / 2, m);
            return tmp * tmp % m;
        }
    }

    // intをlength桁のbit文字列に変換
    static String toBinaryString(int input, int length) {
        return toBinaryString(input).substring(29 - length);
    }

    // intを29桁のbit文字列に変換
    static String toBinaryString(int input) {
        String ret = "";
        int max = 0x10000000;
        for (int i = 0; i < 29; i++) {
            int tmp = input / max;
            ret += tmp;
            input %= max;
            max /= 2;
        }
        return ret;
    }

    public static void main(String[] args) {
        out = new PrintWriter(System.out);
        sc = new Scanner(System.in);

        solve();

        out.flush();
        sc.close();
    }

}


Measured memory_bytes: 21712
import numpy as np
N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
left=0 
right=N-1
while left<right:
  mid=(left+right)//2
  if A[:mid+1].sum()<A[mid+1:].sum():
    left=mid+1
  else:
    right=mid
if (abs(A[:left+1].sum()-A[left+1:].sum()))>(abs(A[:left].sum()-A[left:].sum())):
  print((abs(A[:left].sum()-A[left:].sum())))
else:
  print((abs(A[:left+1].sum()-A[left+1:].sum())))

Measured memory_bytes: 34188
from collections import defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


n = int(input())
A = list(map(int, input().split()))

acc = 0
dic_l = defaultdict(int)
for i in range(n):
    dic_l[A[i]] += 1
    acc += dic_l[A[i]] - 1

for i in range(n):
    print(acc - dic_l[A[i]] + 1)


Measured memory_bytes: 26780
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  long n;
  cin >> n;
  long ans = LONG_MAX;

  long stop = sqrt(n);
  for (int i=1; i<=stop; i++) {
    if (n%i==0) ans = min(ans, i+n/i);
  }
  
  cout << ans-2 << endl;
}


Measured memory_bytes: 888
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;

namespace Project
{
    class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var X = cin.ReadIntArray(5);
            var count = 1;
            foreach(int x in X)
            {
                if (x == 0)
                {
                    WriteLine(count);
                }
                else
                {
                    count += 1;
                }
            }
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } } // intの範囲は-2147483648～2147483648
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N)
        { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N)
        { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N)
        { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }

    }
}


Measured memory_bytes: 27904
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstring>


int main() {
    int n; std::cin >> n;
    std::vector<int> weight(n), value(n);
    for (int i = 0; i < n; i++) {
        std::cin >> value[i] >> weight[i];
    }
    const int D = 11;
    auto chmax = [](int &a, int b) { return a = std::max(a, b); };
    std::vector<std::vector<int>>
        dp(1 << D, std::vector<int>(1e5 + 2, -1e9));
    dp[0][0] = 0, dp[0][weight[0]] = value[0];
    for (int i = 1; i < std::min(1 << D, n); i++) {
        int par = (i - 1) / 2;
        for (int j = 0; j <= 1e5; j++) {
            chmax(dp[i][j], dp[par][j]);
            if (j + weight[i] <= 1e5)
                chmax(dp[i][j + weight[i]], dp[par][j] + value[i]);
        }
    }
    for (int i = 0; i < std::min(1 << D, n); i++) {
        for (int j = 0; j < 1e5; j++) {
            chmax(dp[i][j + 1], dp[i][j]);
        }
    }
    int q; std::cin >> q;
    std::vector<std::pair<int, int>> buf;
    while (q--) {
        int v, lim; std::cin >> v >> lim;
        v--;
        buf.clear();
        while (v >= 1 << D) {
            buf.emplace_back(weight[v], value[v]);
            v = (v - 1) / 2;
        }
        int m = buf.size();
        int ans = 0;
        for (int i = 0; i < (1 << m); i++) {
            int wg = 0, vl = 0;
            for (int j = 0; j < m; j++) {
                if (~(i >> j) & 1) continue;
                wg += buf[j].first;
                vl += buf[j].second;
            }
            int targ = lim - wg;
            if (targ < 0) continue;
            chmax(ans, vl + dp[v][targ]);
        }
        std::cout << ans << std::endl;
    }
    return 0;
}


Measured memory_bytes: 808464
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun sumList(a: Iterable<Long>): List<Long> {
        val result = mutableListOf(0L)
        var i = 0L
        a.forEach {
            i += it
            i %= 2019
            result.add(i)
        }
        return result
    }

    fun <A> countList(a: List<A>): Map<A, Long> {
        val result = mutableMapOf<A, Long>()
        a.forEach {
            result[it] = (result[it] ?: 0L) + 1L
        }
        return result
    }

    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val S = sc.next().map { (it - '0').toLong() }.toLongArray()
        val N = S.count()

        val s = LongArray(N)
        var d = 1
        for (i in 0 until N) {
            s[i] = (S[N - i - 1] * d) % 2019
            d *= 10
            d %= 2019
        }
        val sum = sumList(s.toList())
        var ans = 0L
        countList(sum).forEach {
            ans += (it.value) * (it.value - 1) / 2
        }
        pw.println(ans)
    }
}


Measured memory_bytes: 63776
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k; cin >> n >> k;
    vll p(n), c(n);
    for (ll i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    for (ll i = 0; i < n; i++) cin >> c[i];
    
    ll ans = -HIGHINF - 5;
    for (ll start = 0; start < n; start++) {
        vll loop = {c[p[start]]};
        ll si = p[start];
        while (si != start) {
            loop.emplace_back(loop.back() + c[p[si]]);
            si = p[si];
        }

        ll lsz = loop.size();
        if (k <= lsz) {
            for (ll i = 0; i < min(k, lsz); i++) chmax(ans, loop[i]);
        } else {
            if (loop.back() <= 0) {
                for (ll i = 0; i < lsz; i++) chmax(ans, loop[i]);
            } else {
                ll cyc = k / lsz;
                ll tmp = loop.back() * cyc;
                ll maxd = 0;
                for (ll i = 0; i < k % lsz; i++) chmax(maxd, loop[i]);
                chmax(ans, tmp + maxd);
                if (cyc >= 1) {
                    tmp -= loop.back();
                    maxd = 0;
                    for (ll i = 0; i < lsz; i++) chmax(maxd, loop[i]);
                    chmax(ans, tmp + maxd);
                }
            }
        }
    }
    cout << ans << '\n';
    return 0;
}


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

int main() {
    vector<vector<int>> c(3,vector<int>(3));
    rep(i,3) {
        rep(j,3) cin>>c[i][j];
    }
    vector<int> a(3,0),b(3);
    b[0]=c[0][0]-a[0];
    b[1]=c[0][1]-a[0];
    b[2]=c[0][2]-a[0];
    a[1]=c[1][0]-b[0];
    a[2]=c[2][0]-b[0];
    rep(i,3) {
        rep(j,3) {
            if (c[i][j]!=a[i]+b[j]) {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
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; }
//#define int long long

int n, m;
vector<vector<int>> g;

void solve() {
	cin >> n >> m;
    g.resize(n);
    rep(i, m) {
        int a, b; cin >> a >> b; --a; --b;
        g[a].push_back(b);
    }
    vector<int> res;
    int shortest = n + 1;
    for(int s = 0; s < n; ++s) {
        vector<int> dist(n, -1);
        vector<int> prev(n, -1);
        queue<int> que;
        que.push(s); dist[s] = 0;
        while(que.size()) {
            int v = que.front(); que.pop();
            for(int nv: g[v]) {
                if(dist[nv] == -1) {
                    dist[nv] = dist[v] + 1;
                    prev[nv] = v;
                    que.push(nv);
                }
            }
        }
        for(int t = 0; t < n; ++t) {
            if(t == s || dist[t] == -1) continue;
            for(int nv: g[t]) {
                if(nv != s) continue;
                vector<int> tmp;
                tmp.push_back(s);
                int u = t;
                while(u != s) {
                    tmp.push_back(u);
                    u = prev[u];
                }
                if(shortest > tmp.size()) {
                    shortest = tmp.size();
                    res = tmp;
                }
            }
        }
    }
    if(shortest == n + 1) {
        cout << -1 << endl;
    } else {
        cout << shortest << endl;
        for(int v: res) {
            cout << v + 1 << endl;
        }
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
using Graph = vector<vector<int>>;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	int N;
    cin>>N;
    ll H[N];
    rep(i,N) cin>>H[i];
    for(int i=N-1; i>0; i--){
        if((H[i]-H[i-1])==-1){
            H[i-1]--;
        }else if((H[i]-H[i-1])<=-2){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#define MAX 100

int main(){
  int i,n,x,y,v,j;
  int A[MAX][MAX];
  scanf("%d",&n);

  for( i=0;i<n;i++){
    for(j=0;j<n;j++){
      A[i][j]=0;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d%d",&x,&y);
    for(j=0;j<y;j++){
      scanf("%d",&v);
      A[x-1][v-1]=1;
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j)printf(" ");
      printf("%d",A[i][j]);
    }
    printf("\n");
  }
  return 0;
}



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

using namespace std;

typedef long long ll;

int main(){
        ll N;
        cin>>N;
        int keta=0;
        ll NN=N;
        while(NN>0){
                keta++;
                NN/=10;
        }
        int res=9*(keta-1);
        NN=0;
        for(int i=0;i<keta-1;i++){
                NN+=9*pow(10, i);
        }
        for(int i=9;i>=0;i--){
                //cout<<NN+i*pow(10, keta-1)<<endl;
                if((NN+i*pow(10, keta-1))<=N){
                        res+=i;
                        break;
                }
        }
        cout<<res<<endl;
        return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*pi*/double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll i,fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
llfor;ll ans=0;////////////////////////////////////////////////////////////
int main(){
 ll n,m,k;
 sc(n);sc(m);sc(k);
 ll re;
 rep(i,0,m+1){
  rep(j,0,n+1){
   re=i*j+(m-i)*(n-j);
   if(re==k||re==n*m-k){
    //cout<<i<<" "<<j<<endl;
    py;return 0;
   }
  }
 } 
 pn;
return 0;}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=1e6+5;
vector<ll> V;
int pre[maxn];
int main() {
    vector<int> N(3);
    for(int i=1;i<=3;i++) cin>>N[i-1];
    sort(N.begin(),N.end());
    cout<<((N[0]==5&&N[1]==5&&N[2]==7)?"YES":"NO")<<endl;
    return 0;
}

Measured memory_bytes: 3604
n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    for i in range(n):
        if i==0:
            ans = a[0]
        else:
            ans *= a[i]
            if 1000000000000000000<ans:
                break
    if ans > 1000000000000000000:
        print(-1)
    else:
        print(ans)


Measured memory_bytes: 21780
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w = map(int, input().split())
n = h*w
fld = ''.join([input().rstrip()for _ in range(h)])
edges = [[]for _ in range(n)]


def to_v(i, j):
    return i*w+j


for i in range(h):
    for j in range(w):
        v = to_v(i, j)
        dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for di, dj in dirc:
            x, y = i+di, j+dj
            if x < 0 or h <= x or y < 0 or w <= y:
                continue
            v2 = to_v(x, y)
            if fld[v] != fld[v2]:
                edges[v].append(v2)
                edges[v2].append(v)


def dfs(v, c=0):
    if visited[v]:
        return
    visited[v] = 1
    cnt[c] += 1
    for v2 in edges[v]:
        dfs(v2, c ^ 1)


visited = [0]*n
ans = 0
for v in range(n):
    if visited[v]:
        continue
    cnt = [0, 0]
    dfs(v)
    ans += cnt[0]*cnt[1]
print(ans)


Measured memory_bytes: 230708
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
t=sum(b)-sum(a)
x,y=0,0
for i in range(n):
    if a[i]<b[i]:
        x+=(b[i]-a[i]+1)//2
    else:
        y+=a[i]-b[i]
if t>=0 and x<=t and y<=t:
    ans='Yes'
else:
    ans='No'
print(ans)


Measured memory_bytes: 41456
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <numeric>
#include <complex>
#include <cassert>
#include <climits>

using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const int INF = (1<<30);
const i64 INFL = (1LL<<62);
const i64 MOD = 1000000007;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> i64 mod_pow(i64 a, i64 n, T mod) { mod=(i64)mod; i64 res=1, p=a%mod; while(n){ if(n&1) res=res*p%mod; p=p*p%mod; n>>=1; } return res; }
void print() { std::cout << std::endl; }
template <typename T, typename... A> void print(const T& first, const A&... rest) { cout << sizeof...(rest) << endl; std::cout << first; if (sizeof...(rest)) std::cout << " "; print(rest...); }
template <typename... A> void print(const A&... rest) { print(rest...); }
template <typename A> void print(const std::vector<A>& v) { std::for_each(v.begin(), v.end(), [](A x) { std::cout << x << " "; }); std::cout << std::endl; }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  cout << max(0, a - 2*b) << endl;

  return 0;
}

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

const int mask = (1 << 17) - 1;
const int mod = 1e9 + 7;

int f[47][mask + 7];

int append(int status, int x) {
    return ((status << x) | (1 << (x - 1))) & mask;
}

int main() {
    int n, x, y, z;
    scanf("%d%d%d%d", &n, &x, &y, &z);

    int S = 0;
    S = append(S, x);
    S = append(S, y);
    S = append(S, z);

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= mask; j++)
        for (int k = 1; k <= 10; k++) {
            //f[i - 1][j] -> f[i][append(j, k)];
            int new_status = append(j, k);
            if ((new_status & S) == S) continue;
            f[i][new_status] = (f[i][new_status] +f[i - 1][j]) % mod;
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) ans = 10LL * ans % mod;

    for (int i = 0; i <= mask; i++) ans = (ans - f[n][i]) % mod;
    printf("%d\n", (ans + mod) % mod);
    return 0;
}


Measured memory_bytes: 22272
#include <stdio.h>

int readB(char S[4001], int i, int j, int N)
{
  	int	k;
  	
  	k = j + (j - i);
  	if(0 <= k && k < N)
  	{
  	    if(S[k] == 'B')
  	        return (1);
  	}
  	return (0);
}

int readR(char S[4001], int i, int j, int N)
{
  	int	k;
  	
  	k = j + (j - i);
  	if(0 <= k && k < N)
  	{
  	    if(S[k] == 'R')
  	        return (1);
  	}
  	return (0);
}

int readG(char S[4001], int i, int j, int N)
{
  	int	k;
  	
  	k = j + (j - i);
  	if(0 <= k && k < N)
  	{
  	    if(S[k] == 'G')
  	        return (1);
  	}
  	return (0);
}

long long readBG(char S[4001], int i, int N)
{
  	int	j;
  	long long sum;

    sum = 0;
  	for(j=i+1; j<N; j++)
    {
      	if(S[j] == 'B')
          	sum += readG(S, i, j, N);
      	else if(S[j] == 'G')
          	sum += readB(S, i, j, N);
    }
    return (sum);
}

long long readRB(char S[4001], int i, int N)
{
  	int	j;
  	long long sum;

    sum = 0;
  	for(j=i+1; j<N; j++)
    {
      	if(S[j] == 'R')
          	sum += readB(S, i, j, N);
      	else if(S[j] == 'B')
          	sum += readR(S, i, j, N);
    }
    return (sum);
}

long long readRG(char S[4001], int i, int N)
{
  	int	j;
  	long long sum;

    sum = 0;
  	for(j=i+1; j<N; j++)
    {
      	if(S[j] == 'R')
          	sum += readG(S, i, j, N);
      	else if(S[j] == 'G')
          	sum += readR(S, i, j, N);
    }
    return (sum);
}

int	main(void)
{
  	int	N;
  	char S[4001];
 	int	i;
 	long long sum;
 	long long R;
 	long long G;
 	long long B;
  
  	scanf("%d", &N);
    scanf("%s", S);

    R = 0;
    G = 0;
    B = 0;
    sum = 0;
  	for(i=0; i<N; i++)
    {
      	if(S[i] == 'R')
      	{
      	    R++;
          	sum += readBG(S, i, N);
      	}
      	else if(S[i] == 'G')
        {
            G++;
            sum += readRB(S, i, N);
        }
      	else
      	{
      	    B++;
          	sum += readRG(S, i, N);
      	}
    }
    printf("%lld", R * G * B - sum);
  	return(0);
}

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

using namespace std;

const int N = 1e5+10;
int bit[2*N+1];
int sz;
int l[N],r[N];
vector<int> G[N];
int cnt;

void init(int n){
    cnt = 0;
    sz = 2*n + 1;
}

void dfs(int v){
    l[v] = ++cnt;
    for(int i=0;i<G[v].size();i++){
        int u = G[v][i];
        dfs(u);
    }
    r[v] = ++cnt;
}

void add(int i,int x){
    while(i<=sz){
        bit[i] += x;
        i += i&-i;
    }
}

int getSum(int i){
    int ans = 0;
    while(i>0){
        ans += bit[i];
        i -= i&-i;
    }
    return ans;
}


int main(){
    int n;
    while(cin>>n){
        init(n);
        for(int i=0;i<n;i++){
            int k;
            cin>>k;
            for(int j=0;j<k;j++){
                int child;
                cin>>child;
                G[i].push_back(child);
            }
        }
        dfs(0);
        int q;
        cin>>q;
        for(int i=0;i<q;i++){
            int op;
            cin>>op;
            if(op == 0){
                int v,w;
                cin>>v>>w;
                add(l[v],w);
                add(r[v],-w);
            }else{
                int v;
                cin>>v;
                cout<<getSum(r[v] - 1)<<endl;
            }
        }
    }

    return 0;
}



Measured memory_bytes: 13236
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
const long long INF = 1e18;
long long dp[N][N];
int main() {
	int n;
	scanf("%d", &n);
	vector<pair<int, int>> all;
	for (int i = 1; i <= n; ++ i) {
		int h, p;
		scanf("%d%d", &h, &p);
		all.push_back({h, p});
	}
	sort(all.begin(), all.end(), [&] (pair<int, int> a, pair<int, int> b) {return min(a.first, b.first - a.second) > min(b.first, a.first - b.second);});
	for (int i = 1; i <= n; ++ i) {
		int h, p;
		tie(h, p) = all[i - 1];
		for (int j = 0; j <= i; ++ j) dp[i][j] = INF;
		for (int j = 0; j < i; ++ j) {
			dp[i][j] = min(dp[i - 1][j], dp[i][j]);
			if (dp[i - 1][j] <= h) dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j] + p);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++ i) if (dp[n][i] < INF) ans = i;
	printf("%d\n", ans);
}


Measured memory_bytes: 194048
from fractions import gcd

N, M = map(int, input().split())
S = input()
T = input()
s = len(S)
t = len(T)

st = gcd(s, t)
good = s * t // st

if S[::s // st] == T[::t // st]:
    print(good)
else:
    print(-1)

Measured memory_bytes: 5344
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

X = [[0] * W for _ in range(H)]
for i in range(H):
    start = 0
    cnt = 0
    for j in range(W):
        if s[i][j] == "." and j == W - 1:
            cnt += 1
            for k in range(start, W):
                if s[i][k] == ".":
                    X[i][k] = cnt
        elif s[i][j] == ".":
            cnt += 1
        elif s[i][j] == "#":
            for k in range(start, j):
                if s[i][k] == ".":
                    X[i][k] = cnt
            start = j
            cnt = 0

Y = [[0] * W for _ in range(H)]
for i in range(W):
    start = 0
    cnt = 0
    for j in range(H):
        if s[j][i] == "." and j == H - 1:
            cnt += 1
            for k in range(start, H):
                if s[k][i] == ".":
                    Y[k][i] = cnt
        elif s[j][i] == ".":
            cnt += 1
        elif s[j][i] == "#":
            for k in range(start, j):
                if s[k][i] == ".":
                    Y[k][i] = cnt
            start = j
            cnt = 0

XY = []
for i in range(H):
    for j in range(W):
        XY.append(X[i][j] + Y[i][j] - 1)

print(max(XY))

Measured memory_bytes: 385556
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)

using namespace std;
typedef long long int ll;
typedef pair<int,int> PI;

struct edge{
    ll to, cost;
};

void dijkstra(int s, int n, vector<edge>* G, ll* cost){
    priority_queue<PI,vector<PI>,greater<PI> > q;
    REP(i,n) cost[i+1] = INF;
    cost[s] = 0;
    q.push(PI(0, s));

    while(!q.empty()){
        PI p = q.top();
        q.pop();
        if(p.first > cost[p.second]) continue;
        for (int i=0;i<G[p.second].size();i++){
            if(cost[G[p.second][i].to] > cost[p.second]+G[p.second][i].cost){
                cost[G[p.second][i].to] = cost[p.second]+G[p.second][i].cost;
                q.push(PI(cost[G[p.second][i].to], G[p.second][i].to));
            }
        }
    }
}

int N, M;
int a, b, c;
vector<edge> V[1001];
int main(void){
    cin >> N >> M;
    REP(i,M){
        cin >> a >> b >> c;
        V[a].push_back((edge){b,c});
        V[b].push_back((edge){a,c});
    }

    ll count = 0;
    for(int i=1;i<=N;i++){
        ll cost[N+1];
        dijkstra(i,N,V,cost);
        for(int j=0;j<V[i].size();j++){
            if(V[i][j].to > i and cost[V[i][j].to]<V[i][j].cost) count++;
        }
    }

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




Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,mp[2010],v[2010][2010],ru[2010],a[2010];
vector<int>zh[2010];
int gcd(int x,int y){
	if(!y)return x;
	return gcd(y,x%y);
}
void dfs(int x){
	int i;
	//printf("%d\n",x);
	mp[x]=1;
	for(i=1;i<=n;i++)if(!mp[i]&&v[x][i]){
		ru[i]++;zh[x].push_back(i);
		dfs(i);
	}
}
void ts(){
	int i,x;
	priority_queue<int>q;
	for(i=1;i<=n;i++)if(!ru[i])q.push(i);
	while(!q.empty()){
		x=q.top();q.pop();
		printf("%d ",a[x]);
		for(i=0;i<zh[x].size();i++)q.push(zh[x][i]);
	}
}
int main(){
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	 for(j=i+1;j<=n;j++)if(gcd(a[i],a[j])!=1)v[i][j]=v[j][i]=1;
	for(i=1;i<=n;i++)if(!mp[i])dfs(i);
	ts();
}

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

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

bool check(int x) {
	string s = to_string(x);
	int sum = 0;
	for(char ch : s) {
		sum+= ch-'0';
	}
	return (x%sum ==0);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	cout << (check(n) ? "Yes" : "No");
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define sz(x)       (int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
double dp[3005][3005];
double p[3005];
int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>p[i];
    }

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

    dp[1][1]=p[1];
    dp[1][0]=(1.0-p[1]);
    for(int i=2;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j==i)
                dp[i][j]=(dp[i-1][j-1]*p[i]);
            else if(j==0)
                dp[i][j]=dp[i-1][j]*(1-p[i]);
            else
                dp[i][j]=(dp[i-1][j-1]*p[i])+(dp[i-1][j]*(1.0-p[i]));
            //cout<<dp[i][j]<<" "<<i<<" "<<j<<" "<<p[i]<<" "<<dp[i-1][j-1]<<" "<<(1-p[i])<<" "<<dp[i-1][j]<<endl;
        }
    }

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

    cout<<fixed<<setprecision(12)<<ans;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll N;
ll L[100010],R[100010],len[100010];

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

  cin>>N;
  rep(i,N){
    cin>>L[i]>>R[i];
    len[i]=R[i]-L[i];
  }

  ll ladd=0,radd=0;
  multiset<ll> ls,rs;
  ls.insert(L[0]);
  rs.insert(L[0]);
  ll h=0;
  repl(i,1,N){
    ll l=*ls.rbegin(),r=*rs.begin();
    ladd-=len[i];
    radd+=len[i-1];
    l+=ladd; r+=radd;
    if(L[i]<l){
      ls.insert(L[i]-ladd); ls.insert(L[i]-ladd);
      ll l1=*ls.rbegin();
      ls.erase(ls.find(*ls.rbegin()));
      h+=(l1+ladd)-L[i];
      rs.insert(l-radd);
    }else if(L[i]>r){
      rs.insert(L[i]-radd); rs.insert(L[i]-radd);
      ll r1=*rs.begin();
      rs.erase(rs.find(*rs.begin()));
      h+=L[i]-(r1+radd);
      ls.insert(r-ladd);
    }else{
      ls.insert(L[i]-ladd); rs.insert(L[i]-radd);
    }
  }

  cout<<h<<endl;

  return 0;
}


Measured memory_bytes: 12032
KN = input().split()
A = input().split()
kn = [int(s) for s in KN]
a = [int(i) for i in A]
b = kn[0] + a[0] - a[-1]
num = 0
while num < len(a) -1:
    a[num] = a[num+1] - a[num]
    num += 1
a[len(a)-1] = b
print(int(KN[0])-max(a))

Measured memory_bytes: 26420
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		int n=stdIn.nextInt(),a[]=new int[100],l=0,b=0,i,j,t;
		for(i=0;i<n;i++) a[i]=stdIn.nextInt();
		for(i=0;n-1>i;i++) {
			for(j=n-1;j>i;j--) {
				if(a[j]>a[j-1]) {
					t=a[j];
					a[j]=a[j-1];
					a[j-1]=t;
				}
			}
		}
		for(i=0;i<n;i+=2) l+=a[i];
		for(i=1;i<n;i+=2) b+=a[i];
		System.out.print(l-b);
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;

int main() {
        int n, h;
        scanf("%d%d", &n, &h);
        priority_queue<pair<long long, int>> pq;
        for (int i = 0; i < n; i ++) {
                long long a, b;
                scanf("%lld%lld", &a, &b);
                pq.emplace(a, 0);
                pq.emplace(b, 1);
        }
        long long ans = 0;
        while (!pq.empty()) {
                pair<long long, int> get = pq.top();
                pq.pop();
                if (!get.second) {
                        ans += (h + get.first - 1) / get.first;
                        break;
                } else {
                        ans ++;
                        h -= get.first;
                        if (h <= 0) break;
                }
        }
        printf("%lld\n", ans);
        return 0;
}



Measured memory_bytes: 6256
#include <bits/stdc++.h>
 
using namespace std;
 
template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}
 
long long  gcd(long long  a, long long b) {
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}
 
class Solution {
public:
	void solve() {
		long long a, b;
		cin >> a >> b;
		long long x = gcd(a, b);
		long long y = 1;
		for(long long i=2; i*i <= x; i++){
			if(x % i == 0)y++;
			while(x % i == 0){
				x /= i;
			}
		}
		if(x != 1)y++;
		cout << y << endl;
 
		return;
	};
};
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, raw_input().split())
l = map(int, raw_input().split())
ind = -1
for i in range(n - 1):
	if l[i] + l[i + 1] >= k:
		ind = i
		break
if ind == -1:
	print "Impossible"
else:
	print "Possible"
	for i in range(1, ind + 1):
		print i 
	for i in range(n - 1, ind, -1):
		print i 

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

using bellman_cost = int;
template<class V, class E>
struct Graph
{
	int sz;
	vector<V> v;
	vector<vector<E>> e;
	Graph(int n) : sz(n), v(n), e(n) {}
	template<class... Args>
	inline void assign_vertex(int pos, Args... args) {
		v[pos] = V(args...);
	}
	template<class... Args>
	inline void add_edge(int pos, Args... args) {
		e[pos].emplace_back(args...);
	}
	inline int size() {
		return sz;
	}
};

template<class T>
struct Vertex_Cost
{
	T cost;
	bool valid = false;
	Vertex_Cost(T v1) : cost(v1) {}
	Vertex_Cost() {}
};
using vertex = Vertex_Cost<bellman_cost>;

template<class T>
struct Edge_Cost
{
	int to;
	T cost;
	Edge_Cost(int t, T c) : to(t), cost(c) {}
	Edge_Cost() {}
};
using edge = Edge_Cost<bellman_cost>;
using graph = Graph<vertex, edge>;

template<class T, class V, class E>
void Bellmanford(Graph<V, E>& G, int s, T INF_COST)
{
	auto &v = G.v;
	auto &e = G.e;
	for (auto& vv : v) vv.cost = INF_COST;
	v[s].cost = 0;
	v[s].valid = true;
	for (int i = 0; i + 1 < (int) v.size(); i++) {
		for (int j = 0; j < (int) v.size(); j++) {
			for (auto& x: e[j]) {
				if (v[j].cost == INF_COST) continue;
				v[x.to].cost = min(v[x.to].cost, v[j].cost + x.cost);
				v[x.to].valid = true;
			}
		}
	}
	vector<int> not_valid;
	for (int i = 0; i < (int) v.size(); i++) {
		for (auto& x: e[i]) {
			if (v[i].cost == INF_COST) continue;
			if (v[x.to].cost > v[i].cost + x.cost) {
				not_valid.push_back(x.to);
			}
		}
	}	
	for (auto& x: not_valid) {
		auto dfs = [&](auto f, int pos) {
			if (!v[pos].valid) return;
			v[pos].valid = false;
			for (auto& y: e[pos]) {
				f(f, y.to);
			}
		};
		dfs(dfs, x);
	}
}


void solve(long long N, long long M, long long P, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C) {
	graph g(N);
	for (int i = 0; i < M; i++) {
		g.add_edge(A[i]-1, B[i]-1, -(C[i] - P));
	}
	Bellmanford(g, 0, INT_MAX);
	if (!g.v[N-1].valid) cout << -1 << endl;
	else cout << max(-g.v[N-1].cost , 0) << endl;
}

signed main() {
	long long N;
	scanf("%lld",&N);
	long long M;
	scanf("%lld",&M);
	long long P;
	scanf("%lld",&P);
	std::vector<long long> A(M);
	std::vector<long long> B(M);
	std::vector<long long> C(M);
	for(int i = 0 ; i < M ; i++){
		scanf("%lld",&A[i]);
		scanf("%lld",&B[i]);
		scanf("%lld",&C[i]);
	}
	solve(N, M, P, std::move(A), std::move(B), std::move(C));
	return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

const int MAX_N = 100010;

bool isPrime[MAX_N];
void eratosthenes(int n){
    for(int i=0; i<=n; i++) isPrime[i] = true;
    isPrime[0] = false, isPrime[1] = false;

    for(int i=2; i*i<=n; i++){
        if(isPrime[i]){
            for(int j=2; i*j<=n; j++){
                isPrime[i*j] = false;
            }
        }
    }
}

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

    eratosthenes(100005);

    int x; cin>>x;

    for(int i=x; ; i++){
        if(isPrime[i]){
            cout << i << endl;
            break;
        }
    }

    return 0;
}

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


namespace std{
  template <class M, class N>
  constexpr common_type_t<M, N> gcd(M m, N n){ return __gcd(n, m);}
}


template <typename Monoid, bool COMMUTATIVE = false>
class SegmentTree{
  using value_type = typename Monoid::value_type;
  
protected:
  const int depth, size, hsize;
  std::vector<value_type> data;

public:
  SegmentTree(int n):
    depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1),
    size((1 << depth) - 1),
    hsize(size / 2 + 1),
    data(size + 1, Monoid::id())
  {}

  inline auto operator[](int i) const {return at(i);}
  inline auto at(int i) const {return data[hsize + i];}
  
  inline auto get(int x, int y) const { // [x,y)
    std::vector<int> memo;
    value_type ret = Monoid::id();
    
    int l = x + hsize, r = y + hsize;
    while(l < r){
      if(r & 1){
        if(COMMUTATIVE) ret = Monoid::op(ret, data[--r]);
        else memo.push_back(--r);
      }
      if(l & 1) ret = Monoid::op(ret, data[l++]);
      l >>= 1, r >>= 1;
    }

    if(not COMMUTATIVE){
      std::reverse(memo.begin(), memo.end());
      for(auto i : memo) ret = Monoid::op(ret, data[i]);
    }
    
    return ret;
  }

  inline void update(int i, const value_type &x){
    i += hsize;
    data[i] = x;
    while(i > 1) i >>= 1, data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init_with_vector(const std::vector<T> &val){
    data.assign(size + 1, Monoid::id());
    for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
    for(int i = hsize-1; i >= 1; --i) data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init(const T &val){
    init_with_vector(std::vector<value_type>(hsize, val));
  }  

  auto debug(){
    return data;
  }
};

template <typename T>
struct GcdMonoid{
  using value_type = T;

  static value_type IDENTITY;

  constexpr inline static value_type id(){
    return IDENTITY;
  }

  constexpr inline static value_type op(const value_type &a, const value_type &b){
    return std::gcd(a, b);
  }
};

using Mon = GcdMonoid<int>;
template <> int GcdMonoid<int>::IDENTITY = 0;


int main(){
  int N; scanf("%d", &N);

  std::vector<int> A(N);
  for(int i = 0; i < N; ++i) scanf("%d", &A[i]);

  SegmentTree<Mon> seg(N);
  seg.init_with_vector(A);

  int ans = 0;

  for(int i = 0; i < N; ++i){
    ans = std::max(ans, std::gcd(seg.get(0, i), seg.get(i+1, N)));
  }

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

  return 0;
}


Measured memory_bytes: 1664
//namespace problems {
//    vector<string> solve(string str) {
//        if (str.size() == 1) return {str};
//        int z = 0;
//        int e = 0;
//        for (auto &c: str) {
//            if (c == '1') e++;
//            else z++;
//        }
//        if (e != z) return {str};
//        return {str.substr(0,1), str.substr(1,str.size()-1)};
//    }
//}
//
//#include <iostream>
//#include <vector>
//#include <complex>
//
//using std::cin;
//using std::cout;
//using std::endl;
//using std::vector;
//using std::string;
/*

  cin >> n >> m >> l;
  
  vector<vector<int>> roads;
 
  for (int i = 0; i < m; i++) {
      int a,b,c;
      cin >> a >> b >> c;
      roads.push_back({a,b,c});
  }
  
  cout << sum << endl;

 */
#include <complex>
#include <iostream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iterator>
#include <tuple>
#include <set>
#include <map>

using namespace std;

bool myfunction (int i, int j) { return (i > j); }

int main() {
    int n;
    cin >> n;
    
    cout << ceil(n / 2.0) - 1 << endl;
//    for (int i = 0; i < n; i++) {
//        int val;
//        cin >> val;
//        m[val]++;
//    }
    
    int lo = 1, hi = 2;
    int res = 0;
    
    int cur = 3;
    
//    while (hi < n) {
//        if (cur == n) {
//            res++;
//            cur -= lo;
//            lo++;
//        } else if (cur < n) {
//            hi++;
//            cur += hi;
//        } else {
//            cur -= lo;
//            lo++;
//        }
//    }
    
    //cout << res << endl;
    
    //for (int i = 0; i < res.size(); i++) cout << res[i] << endl;
    
     return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int D, T, S; cin >> D >> T >> S;
  if ((D/S) < T) {
    cout << "Yes" << endl;
  } else if (D/S == T && D % S == 0){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
from collections import defaultdict
import math

N = int(input())
m = defaultdict(lambda : 0)
BIG_NUMBER = 1000000007
bad_iwashi_count = 0

for _ in range(N):
    A,B = map(int,input().split())
    #0の場合
    if A == 0 and B == 0:
        bad_iwashi_count += 1
        continue
    if A == 0:
        m[(-1,0,1)]+=1
        continue
    if B == 0:
        m[(1,1,0)]+=1
        continue
    #0以外
    gcd_ = math.gcd(A,B)
    A = A//gcd_
    B = B//gcd_
    if A < 0 and B > 0: m[(-1,-A,B)]+=1
    elif B < 0 and A > 0: m[(-1,A,-B)]+=1
    elif A < 0 and B < 0 :m[(1,-A,-B)]+=1
    elif A > 0 and B > 0 :m[(1,A,B)]+=1

total = 1
for key in list(dict(m).keys()):
    total *= pow(2,m[key],BIG_NUMBER) + pow(2,m[-key[0],key[2],key[1]],BIG_NUMBER) -1
    total %= BIG_NUMBER
    m.pop(key)
    m.pop((-key[0],key[2],key[1]))
print((total+bad_iwashi_count-1)%BIG_NUMBER)

'''
3
1 2
-1 1
2 -1
'''

Measured memory_bytes: 56484