akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

int64_t N, M, Q;
std::vector<int64_t> a, b, c, d;

int64_t score(std::vector<int64_t> A)
{
	int64_t res = 0;
	for (int64_t i = 0; i < Q; i++)
	{
		if (A[b[i]] - A[a[i]] == c[i]) res += d[i];
	}
	return res;
}

int64_t dfs(std::vector<int64_t> &A)
{
	if ((int64_t)A.size() == N) return score(A);

	int64_t res = 0;
	int64_t prev = A.empty() ? 1 : A.back();
	for (int64_t i = prev; i <= M; i++)
	{
		A.push_back(i);
		res = std::max(res, dfs(A));
		A.pop_back();
	}
	return res;
}

void solve()
{
    std::cin >> N >> M >> Q;
	a.resize(Q);
	b.resize(Q);
	c.resize(Q);
	d.resize(Q);
	for (int64_t i = 0; i < Q; i++)
	{
		std::cin >> a[i] >> b[i] >> c[i] >> d[i];
		// a, bはindex
		a[i]--;
		b[i]--;
	}
	std::vector<int64_t> A;
	int64_t ans = dfs(A);
	std::cout << ans << std::endl;
}

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


Measured memory_bytes: 3564
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int a,b;
    char str[15];
    scanf("%d%d",&a,&b);
    scanf("%s",str);
    int i;
    bool j = 1;
    for(i=0;i<a+b+1;i++)
    {
        if(i==a && str[i]!='-')
            j = 0;
        if(i!=a && (str[i]<'0' || str[i]>'9'))
            j = 0;
    }
    if(j)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


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

using namespace std;

#define int long long 
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };

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

int imos[102];

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

    int N;
    int p[100];
    cin >> N;
    int res = 1;
    for(int i = 0; i < N; ++i) {
        cin >> p[i];
        ++imos[1]; --imos[p[i] + 1];
    }
    for(int i = 1; i <= 100; ++i) imos[i + 1] += imos[i];
    for(int i = 1; i <= 100; ++i) {
        if(i <= imos[i]) res = i;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3112
#include<stdio.h>
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if ( a==b) {
        printf("%d", c);
    }
    else if (b==c){
        printf("%d",a);
    }
    else if (a==c){
        printf("%d",b);
    }
    return 0;
}

Measured memory_bytes: 128
import itertools

def distance(x1, x2, y1, y2):
    return (((x1 - x2) ** 2) + ((y1 - y2) ** 2)) ** 0.5

N = int(input())
x = [list(map(int, input().split())) for i in range(N)]

n = range(N)
ptns = list(itertools.permutations(n,N))

ans = 0

for route in ptns:
    for idx, val in enumerate(route):
        if idx == len(route) - 1:
            break
        dep = route[idx]
        arr = route[idx + 1]
        dist = distance(x[dep][0], x[arr][0], x[dep][1], x[arr][1])
        ans += dist

print(ans / len(ptns))

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

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        int* array = new int [n];
        for (int i = 0; i < n; i++) {
            cin >> array[i];
        }
        int count = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    count++;
                }
            }
        }
        cout << count << endl;
        delete[] array;
    }
}

Measured memory_bytes: 0
#include<vector>
#include<list>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i;
  int n,b,c,d,e,f;
  while(cin>>n&&n){
    f=-1;
    for(i=0;i<n;i++){
      cin>>b>>d>>e;
      if(f==-1||f<d+e){
	f=d+e;
	c=b;
      }
    }
    cout<<c<<" "<<f<<endl;
  }
  return 0;
}

Measured memory_bytes: 868
#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int, input().split()))
    if max(l) < sum(l) - max(l):
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 61624
#include <stdio.h>
#include <stdlib.h>

#define min(a, b) (a)<(b)?(a):(b)

int compar(const void *a, const void *b){
  return *((int*)a)-*((int*)b);
}

int main()
{
  int i, j, k, n, wmin, cost = 0;
  scanf("%d", &n);
  int w[n], c[n], u[n];
  for (i=0; i<n; i++) {
    scanf("%d", w+i);
    u[i] = w[i];
    c[i] = 0;
    if (i==0 || wmin>w[i]) wmin=w[i];
  }
  qsort((void*)u, n, sizeof(int), compar);
  int loop[n], xi;
  k = n;
  while (k>0) {
    for (i=0; c[i]==1; i++);
    c[i]=1;
    k--;
    loop[0]=i;
    int len=1;
    while (1) {
      for (xi=0; u[xi]!=w[i]; xi++);   // xi = u.index(w[i])
      if (c[xi]==1) break;
      c[xi] = 1;
      k--;
      loop[len++]=xi;
      i = xi;
    }

    if (len==1) continue;
    int lmin=w[loop[0]];

    for (i=0; i<len; i++) {
      if (lmin>w[loop[i]]) lmin=w[loop[i]];
      cost += w[loop[i]];
    }
    if (lmin==wmin) cost += lmin*(len-2);
    else            cost += min(lmin+(len+1)*wmin, lmin*(len-2));
  }
  printf("%d\n", cost);

  return 0;
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//for(int i = 0; i<n; i++)
 
 
int main()
{
    string s;
    int w;
    cin>>s>>w;
    for(int i = 0; i < (int)s.size(); i += w){
         cout << s[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()

def check(N, S, P, state):
    sw = [0] * len(P)
    for i in range(N):
        if (state >> i) & 1:
            for m, s in enumerate(S):
                sw[m] += i + 1 in s
    return all((sw[i] % 2 == P[i] for i in range(len(P))))


def main():
    N, M = MI()
    S = []
    for _ in range(M):
        S.append(MIT()[1:])
    P = MIT()
    ans = 0
    for state in range(2**N):
        ans += check(N, S, P, state)
    return ans


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 5192
N,M =map(int,input().split())
H = list(map(int,input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
Alist = [1]*N
for i in range(M):
    if H[AB[i][0]-1] >= H[AB[i][1]-1]:
        Alist[AB[i][1]-1] = 0
    if H[AB[i][0]-1] <= H[AB[i][1]-1]:
        Alist[AB[i][0]-1] = 0
print(Alist.count(1))

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

using namespace std;

int main(){

    int n;
    cin >> n;
    n %= 10;
    if(n==3){
        cout << "bon" << endl;
    }else if(n==0||n==1||n==6||n==8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  int sum = 0;
  int n = N;
  
  while (n > 0) {
    sum += n % 10;
    n /= 10;
  }
  
  if ((N % sum) == 0) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}
  
  
    


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


int a,b,c,d;

int main(){
	cin >> a >> b >>c >> d;
	
	if(a != c) cout << 1 << endl;
	else cout << 0 << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
const ll inf=1e18;

int main() {
  ll m,k;
  cin >> m >> k;
  if(m==0) {
    if(k==0) {
      cout << "0 0" << endl;
    }
    else {
      cout << -1 << endl;
    }
  }
  else if(m==1) {
    if(k==0) {
      cout << "0 0 1 1" << endl;
    }
    else {
      cout << -1 << endl;
    }
  }
  else if(m>1) {
    if(k>=(1<<m)) {
      cout << -1 << endl;
    }
    else {
      for(ll i=0;i<(1<<m);i++) {
        if(i!=k) {
          cout << i << " ";
        }
      }
      cout << k << " ";
      for(ll i=(1<<m)-1;i>-1;i--) {
        if(i!=k) {
          cout << i << " ";
        }
      }
      cout << k << endl;
    }
  }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define sz(a) (ll)(a.size())
#define pll pair<ll,ll>
char a[1005][1005];
ll dp[1005][1005];
ll p = 1000000007;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll i,j,n,m;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
			cin>>a[i][j];
	}
	dp[0][0]=0;
	for(i=1;i<m;i++)
	{
		if(a[0][i]=='#')
			break;
		else 
			dp[0][i]=1;
	}
	for(i=1;i<n;i++)
	{
		if(a[i][0]=='#')
			break;
		else 
			dp[i][0]=1;
	}
	for(i=1;i<n;i++)
	{
		for(j=1;j<m;j++)
		{
			if(a[i][j]!='#')
				dp[i][j] = (dp[i-1][j]%p+dp[i][j-1]%p)%p;
		}
	}
	cout<<dp[n-1][m-1]<<endl;
	return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    int n, l; cin >> n >> l;
    int sum = 0;
    for(int i = 0; i < n; i++) sum += l + i;

    int tmp = abs(l);
    int eat = 0;
    for(int i = 1; i < n; i++){
        if(abs(l + i) < tmp){
            tmp = abs(l + i);
            eat = i;
        }
    }
    cout << sum - (eat + l) << endl;


    return 0;
}


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

using namespace std;

typedef long long          ll;
typedef unsigned long long ull;
typedef vector<int>	       vi;
typedef vector<bool>       vb;
typedef map<int, int>      mii;
typedef pair<int, int>     ii;

#define INF                0x3f3f3f3f
#define INFLL              0x3f3f3f3f3f3f3f3f
#define each(x, s)         for(auto& x : s)
#define loop(x)	           for(int i = 0;i < x;i++)
#define vloop(v, x)        for(int v = 0;v < x;v++)
#define avg(l, r)          l + (r - l) / 2
#define iter(a)            a.begin(), a.end()
#define riter(a)           a.rbegin(), a.rend()
#define endl               "\n"

const ll mod = 1000000007;

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

	int n, k;
	cin >> n >> k;
	vector<ll> a;
	int z = 0, x;
	loop(n) {
		cin >> x;
		if (x) a.push_back(x);
		else z++;
	}
	if (z + k > n) cout << 0 << endl;
	else {
		sort(iter(a), [](ll x, ll y) {
			return abs(x) == abs(y) ? x > y : abs(x) > abs(y);
		});
		int neg = 0, lastn = -1, lastp = -1;
		loop(k) {
			if (a[i] < 0) neg++, lastn = i;
			else lastp = i;
		}
		if (neg & 1) {
			int ok = 0;
			vector<pair<ll, ll>> ts;
			for (int i = k;ok < 3 and i < n - z;i++) {
				if (lastp != -1 and a[i] < 0 and not (ok & 1)) ts.emplace_back(a[i], a[lastp]), ok |= 1;
				else if (a[i] > 0 and not (ok & 2)) ts.emplace_back(a[i], a[lastn]), ok |= 2;
			}
			if (ok) {
				if (abs(ts[0].first) * abs(ts[1].second) < abs(ts[1].first) * abs(ts[0].second)) {
					swap(ts[0], ts[1]);
				}
				a[(ts[0].second > 0 ? lastp : lastn)] = ts[0].first;
			}
			else {
				if (z) a[0] = 0;
				else {
					sort(riter(a), [](ll x, ll y) {
						return abs(x) == abs(y) ? x > y : abs(x) > abs(y);
					});
				}
			}
		}
		ll ans = 1;
		loop(k) {
			if (a[i] < 0) a[i] += mod;
			ans *= a[i];
			ans %= mod;
		}
		if (ans < 0) ans += mod;
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 5300
#include<cstdio>
unsigned answer[101] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 8, 8, 11, 11, 11, 11, 14, 14, 32, 32, 35, 35, 35, 35, 42, 42, 42, 42, 49, 49, 49, 49, 49, 49, 75, 75, 86, 86, 86, 86, 86, 86, 123, 123, 131, 131, 131, 131, 148, 148, 153, 153, 170, 170, 170, 170, 170, 170, 227, 227, 227, 227, 227, 227, 250, 250, 323, 323, 324, 324, 324, 324, 354, 354, 354, 354, 384, 384, 384, 384, 384, 391, 491, 491, 529, 529, 529, 529, 529, 529, 543};

int main(){
    unsigned N;
    scanf("%u", &N);
    printf("%u\n", answer[N]);
    return 0;
}

Measured memory_bytes: 1732
//https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};
int N;
string s;
int ms[1123456];
int main(){
    cin>>N;
    cin>>s;
    for(int i:range(N)){
        if(s[i]=='M')ms[i+1]++;
        ms[i+1]+=ms[i];
    }
    int Q;
    cin>>Q;
    while(Q--){
        int k;
        cin>>k;
        LL ret = 0;
        LL tot = 0;
        LL ds = 0;
        for(int i:range(N)){
            if(s[i]=='D'){
                ds++;
            }
            if(s[i]=='M'){
                tot+=ds;
            }
            if(s[i]=='C'){
                ret+=tot;
            }
            if(i-(k-1)>=0&&s[i-(k-1)]=='D'){
                ds--;
                tot-=ms[i+1]-ms[i-(k-1)];
            }
        }
        cout<<ret<<endl;
    }
    return 0;
}

Measured memory_bytes: 5404
#include <bits/stdc++.h>
using namespace std;
int N,T;
long long t[200010];
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>T;
    for(int i=0;i<N;++i)
    {
        cin>>t[i];
    }
    long long ans=0;
    int start=t[0];
    for(int i=1;i<N;++i)
    {
        if(start+T<t[i])
        {
            ans+=T;
            start=t[i];
        }
        else
        {
            ans+=(t[i]-start);
            start=t[i];
        }
    }
    ans+=T;
    cout <<ans<<endl;
    return 0;
}


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

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(obj) obj.begin(), obj.end()

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

const int iINF = 1e9;
const long long llINF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

int main() { 
    int N, M;
    cin >> N >> M;
    cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;
    return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define ote(x) cout<<(x)<<endl
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,e)
#define MOD 998244353

int main(){
	int N; cin>>N;
	vl D(N);
	rpz(i, N){
		cin>>D[i];
		if((i==0 && D[i]!=0) || (i>0 && D[i]<=0)){
			ote(0);
			return 0;
		}
	}

	map<ll,ll> M;//<depth,count>
	rpz(i, N) M[D[i]]++;

	// for(auto m:M){printf("%d %d\n",m.first,m.second);}puts("\n--");//

	ll ans = 1;
	rp(d, 1, M.size())
		rpz(i, M[d]) ans  = ans * M[d-1] % MOD;
	ote(ans);
}


Measured memory_bytes: 7296
#include <stdio.h>
#include <math.h>

typedef struct{
  double x;
  double y;
}Point;

void func(int, Point, Point);

int main(){

  int n;
  Point p1, p2;

  p1.x=0;
  p1.y=0;
  p2.x=100;
  p2.y=0;

  scanf("%d", &n);
  printf("%.8lf %.8lf\n", p1.x, p1.y);

  func(n, p1, p2);

  printf("%.8lf %.8lf\n", p2.x, p2.y);

  return 0;

}

void func(int n, Point p1, Point p2){

  Point a, b, c;

  if(n==0){
    return;
  }
  else{

    a.x=p1.x + (p2.x - p1.x)/3.0;
    a.y=p1.y + (p2.y - p1.y)/3.0;

    b.x=p1.x + 2.0*(p2.x - p1.x)/3.0;
    b.y=p1.y + 2.0*(p2.y - p1.y)/3.0;

    c.x= a.x + (b.x - a.x)*cos(60.0*M_PI/180.0) - (b.y - a.y)*sin(60.0*M_PI/180.0);
    c.y= a.y + (b.x - a.x)*sin(60.0*M_PI/180.0) + (b.y - a.y)*cos(60.0*M_PI/180.0);

    func(n-1, p1, a);
    printf("%.8lf %.8lf\n", a.x, a.y);
    func(n-1, a, c);
    printf("%.8lf %.8lf\n", c.x, c.y);
    func(n-1, c, b);
    printf("%.8lf %.8lf\n", b.x, b.y);
    func(n-1, b, p2);
  }
}
     



Measured memory_bytes: 2144
(let* ((n (read-line)))
  (defun f (a b) (if a b (not b)))
  (if (and (f (find #\N n :test #'char=) (find #\S n :test #'char=)) (f (find #\E n :test #'char=) (find #\W n :test #'char=)))
      (princ "Yes")
      (princ "No")))

Measured memory_bytes: 3680
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define ee endl
#define pii pair<int,int>
#define infinity 10000000000000000
#define mod 1000000007
int fx[]={0,0,+1,-1};
int fy[]={+1,-1,0,0};

using namespace std;
///check n=1;
///check corner case;
const int maX=1e5+1;
vector<ll>Graph[maX],cost[maX];
ll visit[maX];
ll x[10];
ll y[10];

int main()
{
    ll n,m,i,j,mx=-1;
    cin>>n;
    double sum=0.0;
    for(i=0;i<n;i++){
        cin>>j;
        sum+=j;
        mx=max(mx,j);
    }
    sum-=mx;
    sum+=(mx*1.0)/2.0;
    cout<<sum<<endl;
return 0;
}


Measured memory_bytes: 4992
use std::cmp::max;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let a: Vec<u64> = (0..n).map(|_| read()).collect();

    let v1: Vec<u64> = a
        .iter()
        .scan(a[0], |state, x| {
            let tmp = gcd(*state, *x);
            *state = tmp;
            Some(tmp)
        })
        .collect();
    let mut v2: Vec<u64> = a
        .iter()
        .rev()
        .scan(a[n - 1], |state, x| {
            let tmp = gcd(*state, *x);
            *state = tmp;
            Some(tmp)
        })
        .collect();

    v2.reverse();

    let mut max_i = *[v1[n - 1], v1[n - 2], v2[0], v2[1]].iter().max().unwrap();
    for i in 0..n - 2 {
        max_i = max(gcd(v1[i], v2[i + 2]), max_i);
    }

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

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn gcd(n: u64, m: u64) -> u64 {
    if n % m == 0 {
        m
    } else {
        gcd(m, n % m)
    }
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N, x;
int A[200100];

bool can(){
    if(N == 2){
        if(x != 2){
            return false;
        }

        std::iota(A, A + (2 * N - 1), 1);
        return true;
    }

    if(x == 1 || x == 2 * N - 1){
        return false;
    }

    std::iota(A, A + (2 * N - 1), 1);

    int y = x <= N ? x : 2 * N - x;

    std::swap(A[N-1], A[y-1]);
    std::swap(A[N-2], A[0]);
    std::swap(A[N-3], A[2*N-2]);
    std::swap(A[N], A[2*N-3]);

    if(y != x){
        for(int i=0;i<2*N-1;++i){
            A[i] = 2 * N - A[i];
        }
    }

    return true;
}

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

    std::cin >> N >> x;

    if(can()){
        std::cout << "Yes" << std::endl;

        for(int i=0;i<2*N-1;++i){
            std::cout << A[i] << std::endl;
        }
    }else{
        std::cout << "No" << std::endl;
    }
}


Measured memory_bytes: 2304
n,k=gets.split;a=[*0..9]-gets.split.map(&:to_i)
i1=(0...n.size).find{|i|!a.find{|e|e==n[i].to_i}}
(puts n;exit)if !i1
i2=i1.downto(0).find{|i|a.find{|e|e>n[i].to_i}}||-1
puts"#{i2<0?a[0]>0?a[0]:a[1]:n[0...i2]+a.find{|e|e>n[i2].to_i}.to_s}"+a[0].to_s*(n.size-i2-1)

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define BITBOOL(x,a) (((x)>>(a))&1)
int main(void){
  ll N, A, B, ans;
  cin >> N >> A >> B;
  ans = (N / (A+B))*A + min(N-(N / (A+B))*(A+B) ,A);
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} 

#include <boost/multiprecision/integer.hpp>

#define MAX 200001
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
int64_t COM(i64 n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    if (n >= MAX) { // O(k)
        i64 com = finv[k];
        rep(i, 0, k) (com *= (n - i)) %= MOD;
        return com;
    }
    else return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

i64 n, a, b; cin >> n >> a >> b;

COMinit();

i64 ans = boost::multiprecision::powm((i64)2, n, MOD);
(ans -= 1) %= MOD;

(ans -= COM(n, a) + COM(n, b)) %= MOD;

cout << (ans + MOD) % MOD << "\n";
return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 5120
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n, a[101][101], s, t, u;
	
	while(cin >> n){
		fill(&a[0][0], &a[n][n], 99999);
		
		for(int i = 0; i <= n; i++){
			a[i][i] = 1;
		}
		for(int i = 0; i < n; i++){
			cin >> s >> t;
			while(t--){
				cin >> u;
				a[s][u] = 1;
			}
		}
		
		for(int k = 1; k <= n; k++){
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					a[i][j] = (a[i][j] > a[i][k]+a[k][j])? a[i][k]+a[k][j] : a[i][j];
				}
			}
		}
		
		cin >> n;
		while(n--){
			cin >> s >> t >> u;
			if(a[s][t]+1 <= u){
				cout << a[s][t]+1 << endl;
			} else {
				cout << "NA" << endl;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
/*
 * Author       : YangDavid
 * Created Time : 2019年07月22日 星期一 11时13分09秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 555;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, a[maxn][maxn];
ll dp[maxn][maxn], pre1[maxn][maxn], pre2[maxn][maxn];
void upd(ll &x, ll y) { if(x > y) x = y; }

int main() {
    scanf("%d", &n);
    rep(i, n) rep(j, n) if(i != j) scanf("%d", &a[i][j]);
    rep(i, n) rep(j, n) {
        pre1[i][j] = pre1[i - 1][j] + pre1[i][j - 1] - pre1[i - 1][j - 1] + a[i][j];
        pre2[i][j] = pre2[i - 1][j] + pre2[i][j - 1] - pre2[i - 1][j - 1] + (i<j ? a[i][j] : 0);
    }

    memset(dp, 0x3f, sizeof dp);

    dp[0][0] = 0;
    for(int i = 0; i < n; ++i) {
        for(int last = 0; last <= i; ++last) {
            for(int j = i + 1; j <= n; ++j) {
                upd(dp[j][i], dp[i][last] + pre1[j][last] - pre1[i][last] + pre2[j][j] - pre2[i][j] - pre2[j][i] + pre2[i][i]); 
            }
        }
    }
    ll ans = INF;
    for(int last = 0; last < n; ++last)
        upd(ans, dp[n][last]);
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 8576
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
	while(1)
	{
		int n; cin >> n ;
		if(!n) break;
		map<int,long long> a;
		vector<int> ans;
		queue<int> q;
		for(int i=0;i<n;i++)
		{
			long b,c; int num;
			cin >> num >> b	>> c ;
			a[num]+=(long long) b*c;
			bool flag=true;
			for(int j=0;j<q.size();j++)
			{
				int tmp=q.front();
				if(tmp==num) flag=false;
				q.push(tmp); q.pop();
			}
			if(flag==true) q.push(num);
		}
		map<int,long long>::iterator p;
		bool flag=false;
		for(p=a.begin(); p!=a.end();p++)
			if(p->second >= 1000000) {ans.push_back(p->first); flag=true;}
		if(flag==false) cout << "NA" << endl;
		else
		{
			while(!q.empty() && !ans.empty())
			{
				vector<int>::iterator p;
				int tmp=q.front(); q.pop();
				p=find(ans.begin(),ans.end(),tmp);
				if(p!=ans.end()) cout << *p << endl;
			}
		}
	}
}

Measured memory_bytes: 1296
N = gets.chomp.to_i
An = gets.chomp.split(' ').map(&:to_i)
Bn = gets.chomp.split(' ').map(&:to_i)

total_killed = 0
(N - 1).downto(0) do |i|
  killed = An[i+1] > Bn[i] ? Bn[i] : An[i+1]
  total_killed += killed
  An[i+1] -= killed
  Bn[i] -= killed
  
  killed = An[i] > Bn[i] ? Bn[i] : An[i]
  total_killed += killed
  An[i] -= killed
  Bn[i] -= killed
end

puts total_killed


Measured memory_bytes: 17572
INF = 10**9+7

xy = list(map(int,input().split()))
ans =''

for i in range(xy[3]-xy[1]):
	ans += 'U'
for i in range(xy[2]-xy[0]):
	ans += 'R'
for i in range(xy[3]-xy[1]):
	ans += 'D'
for i in range(xy[2]-xy[0]+1):
	ans += 'L'
for i in range(xy[3]-xy[1]+1):
	ans += 'U'
for i in range(xy[2]-xy[0]+1):
	ans += 'R'
ans += 'DR'
for i in range(xy[3]-xy[1]+1):
	ans += 'D'
for i in range(xy[2]-xy[0]+1):
	ans += 'L'
ans+= 'U'
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=15000007;
const ll MAX=9187201950435737471;
const int N=100005;
const ll INF=1e17;
const long double PI=acos(-1);

ll a[N];
ll dp[N];

ll f(int idx){
    if(idx<=0){
        return 0;
    }
    ll &ret=dp[idx];
    if(ret!=-1)return ret;
    return ret=(idx>1)?min(f(idx-1)+abs(a[idx]-a[idx-1]),f(idx-2)+abs(a[idx]-a[idx-2])):f(idx-1)+abs(a[idx]-a[idx-1]);
}

void solve(int T){
    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cout<<f(n-1);
}

int main() {
    fastio
    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}




Measured memory_bytes: 8340
#include<cstdio>
#define mod (1000000007)
long long f[110000];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(n>m) {int t=n;n=m;m=t;}
	if(m-n>1) {printf("0\n");return 0;}
	f[0]=1;
	for(int i=1;i<=m;i++) f[i]=f[i-1]*i%mod;
	int x=n==m?2:1;
	printf("%lld\n",f[n]*f[m]*x%mod);
	return 0;
}

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

using namespace std;

int main(){
  int counter = 0;//カウンター
  int N;
  bool finish = false;
  cin >> N;
  
  vector<int> p(N);
  
  for (int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  
  while(true){
	  for (int i = 0; i < N; i++){
    	if(p[i]%2){
          finish = true;
          break;
    	}
    	int counter = 0;
    	p[i] /= 2;
      }
    if(finish){
      break;
    }
    counter++;
  }
  
  cout << counter << endl;
}

Measured memory_bytes: 256
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int main(){
	fastio;
	int n;
	
	
	cin>>n;
	if(n<3){
		cout<<"No";
		return 0;
	}
	int tmp=n;
	while(tmp%2==0){
		tmp>>=1;
	} 
	if(tmp==1){
		cout<<"No";
		return 0;
	}
	cout<<"Yes"<<endl;
	int N=n;
	if(n%2==0) N--;
	cout<<1<<" "<<2<<endl;
	cout<<2<<" "<<3<<endl;
	cout<<3<<" "<<n+1<<endl;
	
	cout<<n+1<<" "<<n+2<<endl;
	
	cout<<n+3<<" "<<n+2<<endl;
	for(int number=5;number<=N;number+=2){
		cout<<number<<" "<<1<<endl;
		cout<<number-1<<" "<<1<<endl;
		cout<<number-1+n<<" "<<number<<endl;
		cout<<number-1<<" "<<number+n<<endl;
	}
	if(n%2==0){
		int one,base=n^1;
		for(int i=2;i<n;i++){
			if((i^base)<n&&(i^base)>1){
				one=i;
				break;
			}
		}
		cout<<n<<" "<<one<<endl;
		cout<<(one^base)<<" "<<n+n<<endl;
	}
	return 0;
}


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

A=[1,3,5,7,8,10,12]
B=[4,6,9,11]
C=[2]

if A.count(x)==1:
  flagX=1
elif B.count(x)==1:
  flagX=2
else:
  flagX=3

if A.count(y)==1:
  flagY=1
elif B.count(y)==1:
  flagY=2
else:
  flagY=3

if flagX==flagY:
  print('Yes')
else:
  print('No')

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

/*
int n, m, dp[100000];
vector<int> g[100000];
queue<pair<int, int>> q;

int main() {
	cin >> n >> m;
	inc(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		g[x].PB(y);
		dp[y] = -1;
	}
	
	inc(i, n) { if(dp[i] == 0) { q.emplace(i, dp[i]); } }
	while(! q.empty()) {
		auto p = q.front(); q.pop();
		if(dp[p.FI] != p.SE) { continue; }
		for(auto && e: g[p.FI]) {
			if(setmax(dp[e], p.SE + 1)) { q.emplace(e, dp[e]); }
		}
	}
	
	int ans = 0;
	inc(i, n) { setmax(ans, dp[i]); }
	
	cout << ans << endl;
	
	return 0;
}
*/

const int M = 100000;
int n, m, dp[M];
vector<int> g[M];

int f(int v) {
	if(dp[v] != 0) { return dp[v]; }
	
	int ma = 0;
	for(auto && e: g[v]) { setmax(ma, f(e)); }
	
	return (dp[v] = ma + 1);
}

int main() {
	cin >> n >> m;
	inc(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		g[y].PB(x);
	}
	
	int ans = 0;
	inc(i, n) { setmax(ans, f(i) - 1); }
	
	cout << ans << endl;
	
	return 0;
}


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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , "; logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */


int main(){
    int k; string s; cin>>k>>s;
    if(s.size()<=k) out(s);
    else{
        string t = s.substr(0,k)+"...";
        out(t);
    }
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
N = int(input())
array = list(map(int, input().split()))
ans = 0
max = 0
first = array[N-1]
for i in range(1,N):
	if array[N-1-i] >= first:
		ans += 1
		first = array[N-1-i]
	else:
		first = array[N-1-i]
		if max < ans:
			max = ans
		ans = 0

if max < ans:
	max = ans

print(max)


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

int main(){
  int N, K;
  int kotae = 1;
  int add, multi;
  cin >> N >> K;

  if ( N == 1 ){
    multi = kotae * 2;
    add = kotae + K;
    if ( add <= multi ){
      kotae =add;
    }
    else {
      kotae = multi;
    }
  }
  if ( N >= 2 ){
    for ( int i=0; i < N; i++){
      multi = kotae * 2;
      add = kotae + K;
      if ( add <= multi ){
        kotae = add;
      }
      else {
        kotae = multi;
      }
     }
   }
   cout << kotae << endl;
}

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

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

       int t=1;
       //cin>>t;
       while(t--)
       {
            string s;
            cin>>s;
            int l,r;
            string t;
            if(s.size()<2)
            {
                 cout<<"-1 -1";
                 return 0;
            }
            if(s.size()==2)
            {
                 if(s[0]==s[1])
                 {
                      cout<<"1 2";
                      return 0;
                 }
                 else
                 {
                      cout<<"-1 -1";
                      return 0;
                 }
            }
            for(int i=0;i<s.size()-2;++i)
            {
                 t = s.substr(i,3);
                 sort(t.begin(),t.end());
                 if(t[0]==t[1] || t[1]==t[2])
                 {
                      cout<<i+1<<" "<<i+3;
                      return 0;
                 }
                 //cout<<t<<"\n";
            }
            cout<<"-1 -1";
       }
}


Measured memory_bytes: 3708
#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 FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;
  cin >> n >> m;
  priority_queue<int> que;
  REP(i,n){
    int a; cin >> a;
    que.push(a);
  }
  REP(i,m){
    int tp = que.top();
    que.pop();
    que.push(tp/2);
  }
  ll ans = 0;
  while(!que.empty()){
    int tp = que.top();
    que.pop();
    ans += tp;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3900
///AJoy Sarker ,CSE JAHANGIRNAGAR UNIVERSITY 48 Batch
#include<bits/stdc++.h>
using namespace std;
#define SORT(c) sort((c).begin(),(c).end());
#define pb push_back
#define MP make_pair
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define pi 3.141592653589793
#define ll long long
#define ull unsigned long long
#define w(x) int x;cin>>x;while(x--)
#define fast ios_base::sync_with_stdio(0)
#define sz size()
typedef unsigned long long UL;
template<typename T>inline T  S(T a)
{
    return a*a;
}
template<class T>inline string tostring(T a)
{
    ostringstream os("");
    os << a;
    return os.str();
}
template<typename T>inline ll tolong(T a)
{
    ll res;
    istringstream os(a);
    os>>res;
    return res;
}
template<typename T>inline T gcd(T a, T b)
{
    if (b == 0)return a;
    else return gcd(b, a % b);
}
template<typename T>inline T bigmod(T a, T b, T m)
{
    if (b == 0)return 1;
    else if (b % 2 == 0)return S(bigmod(a, b / 2, m)) % m;
    else return (a % m*bigmod(a, b - 1, m)) % m;
}
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll modd = (ll)1e9 + 7;
const int mod = 10000007;
/*#define N 20000009
bool prime[N];
vector<ll> prm;
void seive ()
{

    memset(prime, true, sizeof(prime));

    for( ll i=2; i*i<=N; i++)
    {
        if (prime[i] == true)
        {
            prm.pb(i);
            for (ll j=i*i; j<=N; j += i)
                prime[j] = false;
        }
    }
}*/
void pr (int f)
{
    if(f==1)
        cout<<"YES\n";
    else
        cout<<"NO\n";
}
map<int,int>mp;
set<string> st;
queue <int> q ;
int vis [1000];
int main()
{
    fast;
    int a,b,k;
    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)
        {
            cout<<"OK\n";
            return 0;
        }
    }
    cout<<"NG\n";
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,e)

int main(){
	int a,b; cin>>a>>b;
	ote(max({a+b,a-b,a*b}));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n,ret = 0;
  cin >> n;
  vector<ll> a(n+1),b(n+1),ans;
  for(ll i = 1; i <= n; ++i) cin >> a[i];
  for(ll i = n; i >= 1; --i){
    b[i] = a[i];
    for(ll j = 2*i; j <= n; j += i) b[i] += b[j];
    b[i] %= 2;
    if(b[i]){
      ++ret;
      ans.push_back(i);
    }
  }
  cout << ret << '\n';
  sort(ans.begin(),ans.end());
  for(ll i : ans) cout << i << ' ';
  return 0;
}

Measured memory_bytes: 5108
#include<bits//stdc++.h>
using namespace std;
int main(){
	string a;
	cin>>a;
	int x=a.size();
	for(int i=0;i<x;i++){
		cout<<"2018/"<<a[5]<<a[6]<<a[7]<<a[8]<<a[9]<<endl;
		return 0;
	}
}


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

using namespace std;

const int maxn = 2*(int)1e5+100;
//const double eps =
int n, k, a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int l = 1, r = 1000000000, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            cnt += (a[i] - 1) / mid;
        }
        if (cnt <= k) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 4344
N = int(input())
h = [int(i) for i in input().split()]
dp = [0] * N
dp[1] = abs(h[1] - h[0])

for i in range(N-2):
    dp[i + 2] = min(abs(h[i+1] - h[i + 2]) + dp[i+1], abs(h[i] - h[i + 2]) + dp[i])

print(dp[N-1])

Measured memory_bytes: 13928
#[allow(unused_imports)]
use proconio::{input, marker::*};

#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[allow(unused_imports)]
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*).unwrap();
    }
}

fn main() {
    input! {
        rl: usize,
        cl: usize,
        k: usize,
        rcv: [(usize, usize, usize); k],
    }

    let mx = rcv.iter().map(|e| e.2).max().unwrap();
    let mut costs = vec![vec![mx; cl + 1]; rl + 1];
    for &(r, c, v) in &rcv {
        costs[r][c] = mx - v;
    }

    use std::cmp::min;
    const INF: usize = 1_000_000_000_000_000;
    let mut dp = vec![vec![vec![INF; 4]; cl + 1]; rl + 1];
    dp[0][1][0] = 0;
    for i in 0..rl + 1 {
        for j in 0..cl + 1 {
            for k in 0..3 {
                dp[i][j][k + 1] = min(dp[i][j][k + 1], dp[i][j][k] + costs[i][j]);
                if j < cl {
                    dp[i][j + 1][k + 1] = min(dp[i][j + 1][k + 1], dp[i][j][k] + costs[i][j + 1]);
                }
            }
            for k in 0..4 {
                if j < cl {
                    dp[i][j + 1][k] = min(dp[i][j + 1][k], dp[i][j][k] + mx);
                }
                if i < rl {
                    dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][k] + mx);
                    dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][k] + costs[i + 1][j]);
                }
            }
        }
    }
    let mn = dp[rl][cl].iter().min().unwrap();
    println!("{}", (rl + cl - 1) * mx - mn);
}


Measured memory_bytes: 713536
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, a[10010];
    int INF=100000010;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int num1=INF, num2=INF, num3=INF;
    sort(a, a+n);
    string s;
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            if(i==j) continue;
            s=to_string(a[i])+to_string(a[j]);
            int k=stoi(s);
            if(num1>k) {
				num3=num2;
				num2=num1;
				num1=k;
			}else if(num2>k) {
				num3=num2;
				num2=k;
			}else if(num3>k){
				num3=k;
			}
        }
    }
    cout << num3 << "\n";
    
    
    return 0;
}


Measured memory_bytes: 3292
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def yn(f) return (f)? "Yes": "No" end
def ynb(f) return (f)? "YES": "NO" end
def ap(a) a.each{|u| p u} end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
a,b,k = inp
c = 0
(1..100).reverse_each do |d|
  if(a%d == 0 and b%d == 0)
    c += 1
    if(c == k)
      puts d
    end
  end
end

Measured memory_bytes: 1788
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            new Main().solve(sc);
        }
    }

    void solve(Scanner sc) {
        int n = sc.nextInt();
        Point[] ps = new Point[n];

        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long h = sc.nextLong();
            if (h == 100) {
                System.out.printf("%d %d %d%n", x, y, h);
                return;
            }
            ps[i] = new Point(x, y, h);
        }

        Arrays.sort(ps, (x, y) -> {
            if (y.h == x.h) {
                return 0;
            } else if (y.h > x.h) {
                return 1;
            }

            return -1;
        });

        for (int x = 0; x <= 100; x++) {
            for (int y = 0; y <= 100; y++) {
                long h = ps[0].h + Math.abs(ps[0].x - x) + Math.abs(ps[0].y - y);
                for (int k = 0; k < n; k++) {
                    long h1 = Math.max(h - Math.abs(ps[k].x - x) - Math.abs(ps[k].y - y), 0);

                    if (ps[k].h != h1) {
                        break;
                    } else if (k == n - 1) {
                        System.out.printf("%d %d %d%n", x, y, h);
                    }
                }
            }
        }
    }
}

class Point {
    long x;
    long y;
    long h;

    Point(long x, long y, long h) {
        this.x = x;
        this.y = y;
        this.h = h;
    }
}

Measured memory_bytes: 28372
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);

	int N=in();
	string S=in<string>();
	deque<char> T(N);
	REP(i,N) T[i]=S[i];

	int L=0;
	REP(i,N){
		if(S[i]==')'){
			if(L>0) L--;
			else T.push_front('(');
		}
		else{
			L++;
		}
	}
	REP(i,L){
		T.push_back(')');
	}

	for(auto& x:T) cout<<x;
	out();
	return 0;
}


Measured memory_bytes: 256