akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#ifdef WIN32
	#define I64 "%I64d"
#else
	#define I64 "%lld"
#endif

typedef long long ll;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int(s.size()))
#define fname "a"
#define MAXN 303

int n;
int a[MAXN][MAXN];
int g[MAXN][MAXN];

priority_queue < pair<int, pair<int, int> > > q;

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

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

	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j) {
			q.push(mp(a[i][j], mp(i, j)));
		}

	memset(g, -1, sizeof(g));

	ll ans = 0;
	while(!q.empty()) {
		int cost = q.top().f;
		int v1 = q.top().s.f;
		int v2 = q.top().s.s;
		q.pop();
		int ok = 1;
		for (int i = 0; i < n; ++i) {
			if (v1 == i || v2 == i) continue;
			if (a[v1][i] == -1 || a[v2][i] == -1) continue;
			if (a[v1][i] + a[v2][i] < cost) {
				puts("-1");
				return 0;
			}
			if (a[v1][i] + a[v2][i] == cost) {
				ok = 0;
			}
		}
		if (ok) {
			ans += cost;
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1656
import math
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
dat = [a,b,c,d,e]
dattime = map
tindex = 0
tnum = 10

for i in range(5):
    t = dat[i] % 10
    t = 10 if t == 0 else t
    if tnum > t:
        tindex = i
        tnum = t

sum = 0

for i in range(5):
    if i != tindex:
        sum += int( math.ceil(dat[i] / 10) * 10 )
    else:
        sum += dat[i]
print(sum)


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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0LL)
#define mapmin(v) v.rbegin()->first
#define mapmax(v) v.begin()->first
#define pb push_back
#define pf push_front
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK cerr<<"OK\n"
#define OK1 cerr<<"OK1\n"
#define OK2 cerr<<"OK2\n"
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n
#define endl '\n'

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const ll mod=1000000007;
const ll mod2=998244353;

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<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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;}

void YES(bool b) {cout << ((b)?"YES\n":"NO\n");}
void Yes(bool b) {cout << ((b)?"Yes\n":"No\n");}
void yes(bool b) {cout << ((b)?"yes\n":"no\n");}
void Yay(bool b) {cout << ((b)?"Yay!\n":":(\n");}

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n,p,ans=0;
	string s;
	cin >> n >> p >> s;
	if(10%p==0){
		rep(r,n){
			if((s[r]-'0')%p==0){
				ans+=r+1;
			}
		}
		cout << ans << endl;
		return 0;
	}
	vll d(n+1);
	ll ten=1;
	map<ll,ll> m;
	m[0]++;
	for(ll i=n-1;i>=0;i--){
		ll a=(s[i]-'0')*ten%p;
		d[i]=(d[i+1]+a)%p;
		ten*=10;
		ten%=p;
		ans+=m[d[i]];
		m[d[i]]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2564
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
using namespace std;

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

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

	int n,m,x,y;
	cin >> n >> m >> x >> y;
	vector <int> xn(n),ym(m);
	REP(i, n) cin >> xn[i];
	REP(i, m) cin >> ym[i];

	if (x >= y) {
		cout << "War";
		return 0;
	}
	
	VSORT(xn);
	VSORT(ym);

	if (xn[n-1] >= ym[0]) {
		cout << "War";
		return 0;
	}
	if (x >= ym[0]) {
		cout << "War";
		return 0;
	}
	if (xn[n-1] >= y) {
		cout << "War";
		return 0;
	}

	cout << "No War" << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
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;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

int main(){
  int n; cin >> n;
  vector<pair<int,int>> v(n);
  rep(i,n){
    int a; cin >> a;
    v[i] = make_pair(a,i+1);
  }
  
  sort(v.begin(),v.end());
  
  for(auto v1:v){
    cout << v1.second << " ";
  }
  
  return 0;
}

Measured memory_bytes: 1536
let n = Scanf.scanf " %d" (+) 0
let a_s = Array.init n @@ fun _ -> Scanf.scanf " %d" pred
let j = ref 0
let _ = for i = 1 to n do j := a_s.(!j); if !j = 1 then (Printf.printf "%d\n" i; exit 0) done; print_endline "-1"

Measured memory_bytes: 5504
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int M = int.Parse(Console.ReadLine());
		long[]D = new long[M];
		long[]C = new long[M];
		long Dsum = 0;
		long Csum = 0;
		for(var i=0;i<M;i++){
			string[] str = Console.ReadLine().Split();
			D[i] = long.Parse(str[0]);
			C[i] = long.Parse(str[1]);
			Dsum += D[i]*C[i];
			Csum += C[i];
		}
		long ans = Csum-1+(Dsum-1)/9;
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 18100
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;


int main()
{
	int p, m, c;
	cin >> p >> m >> c;
	cout << p + m + c << endl;
	return 0;
}

Measured memory_bytes: 3096
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
AK = np.array(read().split(),np.int32)

A = AK[::2]; K = AK[1::2]

G = 0

for t in range(50000):
    q = A//K; r = A%K
    q += 1
    r += (-r)%q
    A -= r
    if t%1000==0:
        ind = r!=0
        if np.count_nonzero(~ind):
            G ^= np.bitwise_xor.reduce(A[~ind]//K[~ind])
            A=A[ind];K=K[ind]
            if len(A)==0:
                break

answer = 'Takahashi' if G else 'Aoki'
print(answer)

Measured memory_bytes: 21520
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
  int key;
  struct node *p;
  struct node *l;
  struct node *r;
}Node1;
typedef struct node  *Node;
Node root = NULL;
 
Node createNode(){
  Node z = malloc(sizeof(struct node));
  z->l = NULL;
  z->r = NULL;
  z->p = NULL;
  z->key = 0;
  return z;
}
 
int insert(int key){
   
  Node z = createNode();
  Node y = NULL;
  Node x = root;
  z->key = key;
   
  while(x != NULL){
    y = x;
    if(z->key < x->key) x = x->l;
    else x = x->r;
  }
  z->p = y;
  if(y == NULL) root = z;
  else if(z->key < y->key) y->l = z;
  else y->r = z;
}
   
void inorder(Node p){
     
  if(p != NULL){
    inorder(p->l);
    printf(" %d",p->key);
    inorder(p->r);
  }
}
 
void preorder(Node p){
  if(p != NULL){
    printf(" %d",p->key);
    preorder(p->l);
    preorder(p->r);
  }
}
 
int main(void){
 
  int i,key,n;
  char str[20];
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%s",str);
 
    if(str[0] == 'i'){
      scanf("%d",&key);
      insert(key);
    }
    else if(str[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 24040
import numpy as np
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
N,P = map(int,input().split())
numbers = factorize(P)
common=1
for pair in numbers:
    if pair[1]//N:  
        common*=(pair[0]**(pair[1]//N))
print(common)

Measured memory_bytes: 21652
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

long long dp[101][100001];
int main(){
int N,W;
cin>>N>>W;
long long w[101],v[101];
for(int i=1;i<N+1;i++){
cin>>w[i]>>v[i];
}
dp[0][0]=0;
for(int i=1;i<N+1;i++){
for(int wei=1;wei<W+1;wei++){
if(wei>=w[i]){
dp[i][wei]=max(dp[i-1][wei-w[i]]+v[i],dp[i-1][wei]);
}
else{
dp[i][wei]=dp[i-1][wei];
}
}
}
cout<<dp[N][W]<<endl;
}

/*long long dp[100001][3];
int main(){
int N;
long long a[100001][3];
cin>>N;
for(int i=1;i<N+1;i++){
for(int j=0;j<3;j++){
cin>>a[i][j];
}
}
for(int i=0;i<N+1;i++){
for(int j=0;j<3;j++){
dp[i][j]=0;
}
}
for(int i=1;i<N+1;i++){
for(int k=0;k<3;k++){
for(int j=0;j<3;j++){
if(j!=k){
dp[i][k]=max(dp[i][k],dp[i-1][j]+a[i][k]);
}
if(j==k){
dp[i][k]=dp[i][k];
}
}
}
}
long long answer=0;
for(int j=0;j<3;j++){
answer=max(answer,dp[N][j]);
}
cout<<answer<<endl;
}*/





Measured memory_bytes: 78336
def main():
    N = int(input())
    count = 0
    for n in range(N):
        tmp = [int(n) for n in input().split()]
        if tmp[0] == tmp[1]:
            count += 1
        else:
            count = 0
        if count == 3:
            print('Yes')
            return
    print('No')


main()


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

using namespace std;

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

  long N, K;
  cin >> N >> K;

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

  bool notyet = true;
  long res;

  for (long leftPop = 0; leftPop <= min(K, N); leftPop++) {
    for (long rightPop = 0; rightPop <= min(K - leftPop, N - leftPop); rightPop++) {
      vector<long> tmp;
      rep(l, leftPop) tmp.push_back(V[l]);
      rep(r, rightPop) tmp.push_back(V[N-1-r]);
      sort(tmp.begin(), tmp.end());
      long restOperation = K - leftPop - rightPop;
      long i = 0;
      while (i < restOperation and i < tmp.size() and tmp[i] < 0) i++;
      long result = 0;
      for (; i < tmp.size(); i++) result += tmp[i];
      if (notyet or res < result) {
        notyet = false;
        res = result;
      }
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;

int n = 0 ;
int a[100020] = {0} ;
priority_queue<int> seq ;
vector<pii> seq2 ;

int solve()
{
  int ans = 0 ;
  for ( int i = 0 ; i < n ; i++ )
  {
    seq.push( a[i] ) ;
  }
  while( seq.size() )
  {
    int cmp = seq.top() ;
    int mem = 1 ;
    seq.pop() ;
    while( seq.size() )
    {
      int cmp2 = seq.top() ;
      if ( cmp != cmp2 ) break ;
      seq.pop() ;
      mem++ ;
    }
    seq2.push_back( pii( cmp,mem ) ) ;
  }
  for ( int i = 0 ; i < seq2.size() ; i++ )
  {
    pii cmp = seq2[i] ;
    if ( cmp.first < cmp.second ) ans += ( cmp.second - cmp.first ) ;
    if ( cmp.first > cmp.second ) ans += cmp.second ;
  }
  return ans ;
}

int main()
{
  cin >> n ;
  for ( int i = 0 ; i < n ; i++ )
  {
    cin >> a[i] ;
  }
  printf("%d\n", solve()) ;
  return 0 ;
}


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

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

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

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") { 
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}
int n;

int L;

int x[Sz];
            
const int N = 1e5 + 1;
   
int nxt[18][N];
           
int main()
{                                  
  # ifdef Local
    //localInput();
  # endif
  Read_rap();
  cin >> n;    
  for (int i = 1; i <= n; i++)
    cin >> x[i];
  cin >> L;
  for (int i = n - 1; i >= 1; i--) {
    static int ptr = n;
    while (x[ptr] - x[i] > L)
      ptr--;                        
    nxt[0][i] = ptr;    
    for (int j = 1; j <= 17; j++)
      nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
  }
        
  int q; cin >> q;
  while (q--) {
    int l, r; cin >> l >> r;

    if (l > r)
      swap (l, r);

    int ans = 0;
    for (int i = 17; i >= 0; i--) {  
      if (nxt[i][l] && nxt[i][l] <= r)
        l = nxt[i][l], ans += (1<<i);
    }
    if (l < r)
      ans++; 
    cout << ans << endl;
  }
         
                           



  return 0;
}






// Coded by Z..



Measured memory_bytes: 9088
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	// AtCoder Beginner Contest 081
	// https://atcoder.jp/contests/abc081/tasks
	final static int MOD = 10007;
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		int k = sc.nextInt();
		long[] balls = new long[200001];
		long res = 0;
		
		// 先計算數量
		for (int i = 0; i < n; i++) {
			int num = sc.nextInt();
			balls[num]++;
		}
		
		// 排序，有球者將由小排到大
		// [0, ...., 1, 2, 2]
		Arrays.sort(balls);
		
		// 從後面數K個是應該存在的，其他都是應該砍掉的
		for (int i = 0; i < 200001 - k; i++) {
			res += balls[i];
		}
		
		System.out.println(res);
	}
	
	static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine()); 
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try{ 
                str = br.readLine(); 
            } catch (IOException e) { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}


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

int main() {
    string S;
    cin >> S;
    if (S=="RRR") cout << "3" << endl;
    else if (S=="SSS") cout << "0" << endl;
    else if (S=="RRS" || S=="SRR") cout << "2" << endl;
    else cout << "1" << endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 2000000000
#define REP(i,b,n) for(int i = (b); i < n; i++)
#define rREP(i,b,n) for(int i = n; i >= b; i--)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const string lowercase = "abcdefghijklmnopqrstuvwxyz";
const string uppercase = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int gcd(int a, int b){return b ? gcd(b, a % b): a;}

int main()
{
    int d, g;
    cin >> d >> g;
    int p[10], c[10];
    int ans = INF;
    REP(i,0,d) cin >> p[i] >> c[i];
    REP(i,0,1<<d){
        int sum = 0;
        int num = 0;
        REP(j,0,d){
            if(i>>j & 1){
                sum += (j+1) * 100 * p[j] + c[j];
                num += p[j];
            }
        }
        bool valid = true;
        int rest = 0;
        if(sum < g){
            rREP(j,0,d-1){
                if(!(i>>j & 1)){
                    rest += (g - sum) / ((j+1) * 100);
                    if((g - sum) % ((j+1) * 100) > 0) rest++;
                    if(rest >= p[j]) valid = false;
                    break;
                }
            }
        }
        if(valid) ans = min(num+rest, ans);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 n;cin >> n;
    vector<int> a(n,0);
    rep(i,n)cin >> a[i];
    vector<bool> sum(40001,0);
    for(int bit = 0;bit < (1 << n);bit++){
        int s = 0;
        rep(i,n)if(bit & (1 << i))s+=a[i];
        sum[s] = true;
    }
    int q;
    cin >> q;
    rep(i,q){
        ll in;cin >> in;
        if(sum[in])cout << "yes\n";
        else cout << "no\n";
    }
    return 0;
}


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

int main(){

  int N, i;
  long long Sum = 0;
  string s;
  map<string, long long> S;
  cin >> N;
  
  for(i=0; i<N; i++){
    cin >> s;
    sort(s.begin(), s.end());
    S[s]++;
  }
  
  for(auto p : S){
    Sum += p.second * (p.second - 1) / 2;
  }
  cout << Sum << endl;
  return 0;
}

Measured memory_bytes: 11332
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, m;
	cin>>n>>m;
	map<int, vector<pair<int,int> > >mp;
	for(int i =0;i<m;i++)
	{
		int pref, year;
		cin>>pref>>year;
		mp[pref].push_back(make_pair(year,i + 1));
	}
	map<int, vector<pair<int,string> > > c;
	for(auto it : mp){
		vector<pair<int,int> > red = it.second;
		sort(red.begin(),red.end());
		string rez;
		for(int i =0;i<12;i++)
			rez.push_back('0');
			
		int at = 5;
		int pref = it.first;
		while(at >= 0 && pref > 0)
		{
			int number = pref % 10;
			rez[at] = char(number + '0');
			at--;
			pref/=10;
		}
		for(int i =0;i<red.size();i++){
			string nov = rez;
			int city = red[i].second;
			int at = 11;
			int pos = i + 1;
			while(at >= 6 && pos > 0)
			{
				int number = pos % 10;
				nov[at] = char(number + '0');
				at--;
				pos/=10;
			}
			c[it.first].push_back(make_pair(city,nov));
		}
	}
	vector<pair<int,string> > outl;
	for(auto it : c)
	{
		vector<pair<int, string> > red;
		red = it.second;
		for(int i =0;i<red.size();i++)
			outl.push_back(make_pair(red[i].first, red[i].second));
	}
	sort(outl.begin(), outl.end());
	for(int i =0;i<outl.size();i++)
		cout<<outl[i].second<<endl;
	return 0;
}

Measured memory_bytes: 29680
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define P pair<ll,ll>
#define Graph vector<vector<P>>
#define fi first
#define se second
constexpr ll mod=1000000007;
constexpr ll INF=(1ll<<60);
constexpr double pi=3.14159265358979323846;
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;}

int main(){
    string s;cin>>s;
    ll n=s.size();
    ll ans=0;
    rep(i,(n+1)/2){
        if(s[i]!=s[n-1-i]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
int main(){
    int n,q;
    cin >> n >> q;
    queue<pair<string,int> > Q;
    for(int i=0;i<n;++i){
        pair<string,int> ps;
        cin >> ps.first >> ps.second;
        Q.push(ps);
    }
    int now=0;
    while(!Q.empty()){
        pair<string,int> ps=Q.front();Q.pop();
        if(ps.second<=q){
            now+=ps.second;
            cout << ps.first << ' ' << now << endl;
        }else{
            now+=q;
            ps.second-=q;
            Q.push(ps);
        }
    }
}



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

#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
typedef long long ll;
typedef pair<int,int> pii;

const int maxn=505;
const int mod=998244353;
int n,suma,sumb,ans;
int a[maxn],b[maxn],fac[maxn],ifac[maxn],dp[maxn][maxn];

int main(){
	scanf("%d",&n);
	fac[0]=fac[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=400;i++){
		fac[i]=1LL*fac[i-1]*i%mod;
		ifac[i]=1LL*(mod-mod/i)*ifac[mod%i]%mod;
	}
	REP(i,400)ifac[i]=1LL*ifac[i-1]*ifac[i]%mod; 
	dp[0][0]=1;
	rep(i,n){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=suma;j>=0;j--)for(int k=sumb;k>=0;k--){
			int cur=dp[j][k];
			if(!cur)continue;
			int mul=1;
			rep(t,b[i]){
				dp[j+a[i]][k+t]-=1LL*cur*mul%mod*ifac[t]%mod;
				if(dp[j+a[i]][k+t]<0)dp[j+a[i]][k+t]+=mod;
				mul=1LL*mul*a[i]%mod;
			}
		}
		suma+=a[i];
		sumb+=b[i];
	}
	REP(j,suma){
		int mul=suma;
		rep(k,sumb+1){
			mul=1LL*mul*ifac[j]%mod*fac[j-1]%mod;
			ans-=1LL*dp[j][k]*mul%mod*fac[k]%mod;
			if(ans<0)ans+=mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define N 3005
using namespace std;
const int mo=1e9+7;
int n,m,f[N][2],g[N][2],ans;
void inc(int &x,int y){ x=x+y>=mo ? x+y-mo : x+y;}
int main()
{
	int i,j;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++) f[i][0]=1;
	f[0][1]=1;
	while(m--){
		for(i=0;i<=n;i++) g[i][0]=f[i][0],g[i][1]=f[i][1],f[i][0]=f[i][1]=0;
		for(i=0;i<=n;i++)
			for(j=0;j<2;j++){
				if(i){
					inc(f[i][i==1 ? 1 : j],g[i][j]);
					inc(f[i-1][i==1 ? 1 : j],g[i][j]);
				  }
				if(i<n){
					inc(f[i][j],g[i][j]);
					inc(f[i+1][j],g[i][j]);
				  }
			  }
	  }
	for(i=0;i<=n;i++) inc(ans,f[i][1]);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
def main():
    h,*s=open(0)
    h,w=map(int,h.split())
    a=tuple([0]*w for _ in range(h))
    b=tuple([0]*w for _ in range(h))
    c=tuple([0]*w for _ in range(h))
    d=tuple([0]*w for _ in range(h))
    for i in range(h*w):
        i,j=divmod(i,w)
        a[i][j]=a[i][j-1]+1if s[i][j]=='.'else 0
        b[i][~j]=b[i][-j]+1if s[i][-j-2]=='.'else 0
        c[i][j]=c[i-1][j]+1if s[i][j]=='.'else 0
        d[~i][j]=d[-i][j]+1if s[~i][j]=='.'else 0
    print(max(a[i][j]+b[i][j]+c[i][j]+d[i][j]-3for i in range(h)for j in range(w)))
main()

Measured memory_bytes: 178440
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n, k, a;
vi v;

int main() {
	fastio; cin >> n >> k;
	FOR(i, 1, n) {
		cin >> a;
		v.pb(a);
	}
	sort(all(v));
	int ans = 0;
	FOR(i, 0, k-1) ans += v[i];
	cout << ans;
}


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

typedef long long ll;

int n, m;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    if (m & 1) {
        for (int i = 1; i <= m / 2; ++i) {
            cout << i << ' ' << m + 1 - i << endl;
        }
        for (int i = 1; i <= (m + 1) / 2; ++i) {
            cout << m + i << ' ' << (m + 1) * 2 - i << endl;
        }
    } else {
        for (int i = 1; i <= m / 2; ++i) {
            cout << i << ' ' << m + 2 - i << endl;
        }
        for (int i = 1; i <= m / 2; ++i) {
            cout << m + 1 + i << ' ' << (m + 1) * 2 - i << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3656
from collections import defaultdict
n = int(input())
O = defaultdict(list)
for i in range(n):
    F = list(map(int, input().split()))
    for j in range(10):
        if F[j] == 1:
            O[j].append(i)
P = []
for _ in range(n):
    _P = list(map(int, input().split()))
    P.append(_P)

max_x = -1 * 10 ** 10
for i in range(1, 1024):
    v = i
    K = [] # Kaburi
    for j in range(10):
        if v % 2 == 1:
            K.extend(O[j])
        v //= 2
    #print(K)
    x = 0
    for l in range(n):
        k = K.count(l)
        x += P[l][k]
    max_x = max(max_x, x)
print(max_x)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef int64_t Int;
using namespace std;
const int64_t MOD = 1e9+7;

//---------- べき乗 ----------
int64_t power(int64_t a, int64_t n){
    if(n == 0) return 1;
    
    int64_t res = 1;
    while(n > 0){
        if(n % 2 == 1) res = res * a % MOD;
        a = a * a % MOD; n /= 2;
    }
    return res;
}

//---------- 逆元 ----------
int64_t inv(int64_t a){
    return power(a, MOD-2);
}

//---------- 素因数分解 ----------
map<int64_t, int> prime_factor(int64_t n) {
  map<int64_t, int> res;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if(n != 1) res[n] = 1;
  return res;
}

int main(){
    int N;  cin >> N;
    vector<Int> A(10010);
    rep(i, N) cin >> A[i];

    map<Int, int> LCM;

    rep(i,N){
        map<Int, int> f = prime_factor(A[i]);
        for(auto itr = f.begin(); itr != f.end(); itr++){
            pair<Int, int> p = *itr;
            LCM[p.first] = max(LCM[p.first], p.second);
        }
    }

    int64_t lcm = 1;
    for(auto itr = LCM.begin(); itr != LCM.end(); itr++){
        pair<Int, int> p = *itr;
        rep(i, p.second){
            lcm = lcm * p.first % MOD;
        }
    }
    
    int64_t ans = 0;
    rep(i, N){ ans = (ans + (lcm * inv(A[i]) % MOD)) % MOD;}
    cout << ans << endl;
}

Measured memory_bytes: 896
N = int(input())
A = [input() for _ in range(N)]
count = [0] * 4
for a in A:
  if a == 'AC':
    count[0] += 1
  elif a == 'WA':
    count[1] += 1
  elif a == 'TLE':
    count[2] += 1
  else:
    count[3] += 1

print(f"AC x {count[0]}")
print(f"WA x {count[1]}")
print(f"TLE x {count[2]}")
print(f"RE x {count[3]}")

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

using namespace std;

int n;
int a[21];

int main()
{
    scanf("%d",&n);
    int ans = 0;
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    for(int i = 2;i < n;i++)
    {
        if((a[i] > a[i + 1] && a[i] < a[i - 1]) || (a[i] < a[i + 1] && a[i] > a[i - 1]))
           ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main() {
  string S;
  cin >> S;
  S = S.erase(S.size() - 2, 2);
  while (S.size() >= 0) {
    if (S.substr(0, S.size() / 2) == S.substr(S.size() / 2)) {
      printf("%d\n", (int)S.size());
      return 0;
    }
    S = S.erase(S.size() - 2, 2);
  }
}

Measured memory_bytes: 3256
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    height = [0]*n
    for i in range(m):
        a, b = map(lambda x: int(x)-1, input().split())
        height[a] = max(height[a], h[b])
        height[b] = max(height[b], h[a])
    
    count = 0
    for i, j in zip(h, height):
        if i > j:
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 19920
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long n = sc.nextLong();

        long m = Math.min(b-1,n);

        Cal c = new Cal();
        long value = c.calc(a,b,m);
        System.out.println(value);
        sc.close();
    }
}

class Cal
{
    public long calc(long a,long b,long x)
    {
        double value = Math.floor((a*x)/b) - a * Math.floor(x/b);
        return (long) value;
    }
}

Measured memory_bytes: 35784
n=int(input())
s=list(input())
t=list(input())
if s==t:
    print(n)
else:
    cnt=0
    for i in range(n):
        for j in range(n-i):
            if s[i+j]!=t[j]:
                break
            if j==n-i-1:
                cnt=n-i
    print(2*n-cnt)
            
        


Measured memory_bytes: 38384
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ans = Math.max(a+b, Math.max(a-b, a*b));
        System.out.println(ans);
        sc.close();

    }

}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
//#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
        

fast();
//ll t;cin>>t;while(t--)
{
    ll n;
    cin>>n;
    ll a[n],pre[n];
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
      if(i==0)
        pre[i]=a[i];
      else
        pre[i]=(a[i]+pre[i-1]);
    }
    for(auto t:pre)cerr<<t<<" ";cerr<<endl;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
      ans+=((pre[n-1]-pre[i])%mod*a[i]%mod)%mod;
      ans=ans%mod;
    }
    cout<<ans<<endl;

}
return 0;
}

Measured memory_bytes: 6740
#include<bits/stdc++.h>
#define ll      long long
#define pii     pair<int, int>
#define f       first
#define s       second
#define read	freopen("input.txt", "r", stdin)
#define write	freopen("output.txt", "w", stdout)
#define mx      5e9

using namespace std;

int main()
{
	// read;
	// write;

    int n;
    cin>>n;

    int a[n], b[n], c[n], dpa[n], dpb[n], dpc[n];
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    dpa[0] = a[0];
    dpb[0] = b[0];
    dpc[0] = c[0];
    for(int i=1;i<n;i++){
        dpa[i] = a[i] + max(dpb[i-1], dpc[i-1]);
        dpb[i] = b[i] + max(dpa[i-1], dpc[i-1]);
        dpc[i] = c[i] + max(dpb[i-1], dpa[i-1]);
    }
    cout<<max(dpa[n-1], max(dpb[n-1], dpc[n-1]));
}
    



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 100100
/*------------------------------------------------------------*/

int main(){
	string s;
	cin>>s;
	FOR(i,0,s.length()-9)cout<<s[i];
}

Measured memory_bytes: 256
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 99)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)


Measured memory_bytes: 85716
x = input().split()
# x = ['1', '2', '+', '3', '4', '-', '*']

s = []
for i in range(len(x)):
    if x[i] == '+':
        a = int(s[-1])+int(s[-2])
        del s[-2:]
        s.append(a)
    elif x[i] == '-':
        b = int(s[-2])-int(s[-1])
        del s[-2:]
        s.append(b)
    elif x[i] == '*':
        c = int(s[-1])*int(s[-2])
        del s[-2:]
        s.append(c)
    else:
        s.append(x[i])

print(s[0])



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

int main(){
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i=0;i<N;i++){
        cin >> d.at(i);
    }    
    sort(d.begin(),d.end());
    int ans =1;
    for(int i=1;i<N;i++){
        if(d.at(i)!=d.at(i-1)) ans++;
    } 
    cout << ans << endl;
}


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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 4e5 + 5;

int n, t[4*maxn], a[maxn];

void build(int a[], int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = a[tl];
  } else {
    int tm = (tl + tr) / 2;
    build(a, v*2, tl, tm);
    build(a, v*2+1, tm+1, tr);
    t[v] = __gcd(t[v*2], t[v*2+1]);
  }
}

int g(int v, int tl, int tr, int l, int r) {
  if (l > r) 
    return 0;
  if (l == tl && r == tr) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  return __gcd(g(v*2, tl, tm, l, min(r, tm)), g(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
  if (tl == tr) {
    t[v] = new_val;
  } else {
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      update(v*2, tl, tm, pos, new_val);
    else
      update(v*2+1, tm+1, tr, pos, new_val);
    t[v] = __gcd(t[v*2], t[v*2+1]);
  }
}

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

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

  build(a, 1, 0, n-1);

  int ans = 0;
  ans = max(g(1, 0, n-1, 1, n-1), g(1, 0, n-1, 0, n-2));
  for (int i=1; i<n-1; i++) {
    int cur = __gcd(g(1, 0, n-1, 0, i-1), g(1, 0, n-1, i+1, n-1));
    ans = max(ans, cur);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3200
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[1001],b[10001];
int n;
map<int,int> ma;
int fn(int h)
{
  if(h<=0)
    return 0;
  if(ma.count(h))
    return ma[h];
    int ans=INT_MAX;
      for(int i=0;i<n;++i)
      {
        ans=min(ans,fn(h-a[i])+b[i]);
      }
     ma[h]=ans;
  return ans;
    }
int main()
{
  int h;cin>>h>>n;
  for(int i=0;i<n;++i)
    cin>>a[i]>>b[i];
  cout<<fn(h);
}

Measured memory_bytes: 1536
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    //https://atcoder.jp/contests/abc141/tasks/abc141_a
    public class QuestionA
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列の入力
            string s = Console.ReadLine();

            //// 整数の入力
            //long n  = long.Parse(Console.ReadLine());

            //// 文字列配列の入力
            //string[] inputStrArray = Console.ReadLine().Split(' ');

            //// 整数配列の入力
            //var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            string result = "";

            if (s == "ABC")
            {
                result = "ARC";
            }
            else
            {
                result = "ABC";
            }

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


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

//#define FILENAME ""

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back

#define F first
#define S second

using namespace std;

//#define int long long

const int N = 1e4 + 5;
const int inf = 1e9 + 5;
const double pi = acos(-1);

typedef long long ll;

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

const int mod = 1e9 + 7;

#define ios ios_base::sync_with_stdio(0);cin.tie(0);

int n, a[105], nw[N], can[N];

main() {
    #ifdef FILENAME
        freopen(FILENAME".in", "r", stdin);
        freopen(FILENAME ".out", "w", stdout);
    #endif
    ios;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    can[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 10000; j++) {
            nw[j] = can[j];
        }
        for (int j = 0; j <= 10000; j++) {
            if (can[j]) nw[j + a[i]] = 1;
        }
        for (int j = 0; j <= 10000; j++) {
            can[j] = nw[j];
        }
    }
    int ans = 0;
    for (int i = 0; i <= 10000; i++) {
        if (can[i] && i % 10 > 0) ans = i;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
/*******  All Required define Pre-Processors and typedef Constants *******/
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define Dcout(a) cout << setprecision(20) << a << endl
#define MP make_pair
#define PB push_back
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
using ll = long long;
using PAIR = pair<int, int>;
using Graph = vector<vector<int>>;
const ll INF = (1LL << 60);
const double pi=acos(-1.0);
#define debug cout << "line : " << __LINE__ << " debug" << endl
/****** Template of some basic operations *****/
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; }
/**************************************/
/******** User-defined Function *******/

/**************************************/
/********** Main()  function **********/
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    map<int, int> mp;
    rep(i,n) mp[a[i]]++;

    ll cnt1 = 0;
    ll cnt2 = 0;
    for(auto x: mp){
        if(x.second % 2 == 1) cnt1++;
        else cnt2++;
    }

    ll ans = cnt1 + cnt2 - ((cnt2 % 2) == 1);

    cout << ans << endl;
}
/********  Main() Ends Here *************/


Measured memory_bytes: 8164
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int n,d;
  cin >> n >> d;
  int ans = 0;
  while(n>0){
    n -= 2 * d + 1;
    ans++;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <cstring>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define vi vector < int >
#define vll vector < long long >
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))
#define fname "searching"

const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;

ll solve(){
    ll n, m;
    cin >> n >> m;
    ll f = min(n, m / 2);
    ll ans = f + (m - 2 * f) / 4;
    return ans;
}

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

    cout << solve() << "\n";
    
    return 0;
}

Measured memory_bytes: 256
MOD = 998244353
N, S = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
dp1 = Array.new(S + 1, 0)
dp2 = Array.new(N + 1, 0)

A.each_with_index do |a,i|
  S.downto(1) do |j|
    dp1[j + a] = (dp1[j + a] + dp1[j]) % MOD if j + a <= S
  end
  dp1[a] = (dp1[a] + (i + 1)) % MOD if a <= S
  dp2[i + 1] = (dp2[i] + dp1[S]) % MOD
end
puts dp2[N]

Measured memory_bytes: 2044
N, Y = map(int, input().split())
ans1000 = -1
ans5000 = -1
ans10000 = -1
for i in range(N+1):
  for j in range(N+1-i):
    if i*1000+j*5000+(N-i-j)*10000 == Y:
      ans1000 = i
      ans5000 = j
      ans10000 = N-i-j
print(ans10000, ans5000, ans1000)

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

int R_0,W_0,C,R;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> R_0 >> W_0 >> C >> R,R_0){
        int X=max(0,((C*W_0-R_0)+R-1)/R);
        cout << X << endl;
    }
}


Measured memory_bytes: 3128
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (2019)

using namespace std;

typedef long long int Int;

Int L,R;

Int solve(void) {
    if(R-L>=2019)
        return 0;

    Int ans = MOD;
    for(Int i = L;i < R;i++) {
        for(Int j = i+1;j <= R;j++) {
            ans = min(ans,i*j % MOD);
        }
    }

    return ans;
}

int main(void) {
    cin>>L>>R;

    cout<<solve()<<endl;

    return 0;
}





Measured memory_bytes: 256