akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define PII pair<LL,LL>
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))
#define FOR(i,a,b) for (LL i=(a);i<=(b);++i)
#define ROF(i,b,a) for (LL i=(b);i>=(a);--i)
typedef long long LL;
inline LL read(){
	LL x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}

const LL MAXN=300005,Mo=998244353;
struct list{
	LL l,lt[MAXN],nt[MAXN*2],x[MAXN*2],y[MAXN*2];
	void clear(){ l=0; memset(lt,0,sizeof(lt)); }
	void addedge(LL a,LL b){ l++; nt[l]=lt[a]; lt[a]=l; x[l]=b; }
}E;
struct P{
	LL x,y;
	P(LL xx=0,LL yy=0):x(xx),y(yy){}
	P operator +(const P &E)const{ return P(x+E.x,y+E.y); }
	P operator -(const P &E)const{ return P(x-E.x,y-E.y); }
	LL operator *(const P &E)const{ return x*E.y-E.x*y; }
	LL operator ^(const P &E)const{ return x*E.x+y*E.y; }
}A[MAXN],B[MAXN];
LL n,m,a[MAXN],b[MAXN];
LL power(LL a,LL b){
	LL c=1; a%=Mo;
	while (b) {
		if (b&1) c=c*a%Mo;
		a=a*a%Mo; b>>=1;
	}
	return c;
}
LL cmp(P i,P j){ return i*j>0; }
int main(){
	n=read();
	FOR(i,1,n) a[i]=power(i,Mo-2);
	FOR(i,1,n) { A[i].x=read(); A[i].y=read(); }
	LL tmp,ans=power(2,n)+Mo-n-1;
	if (ans>=Mo) ans-=Mo;
	//cout<<ans<<endl;
	FOR(i,1,n) {
		FOR(j,1,i-1) B[j]=A[j]-A[i];
		FOR(j,i+1,n) B[j-1]=A[j]-A[i];
		FOR(j,1,n-1) if (B[j].x<0||B[j].x==0&&B[j].y<0) B[j].x=-B[j].x,B[j].y=-B[j].y;
		sort(B+1,B+n,cmp);
		for (LL j=1,k,tot;j<n;j=k+1) {
			for (k=j;k<n-1&&B[k+1]*B[j]==0;++k);
			tot=k-j+2;
			tmp=(power(2,tot)+Mo-tot-1)*a[tot]%Mo;
			//cout<<i<<':'<<tmp*tot%Mo<<endl;
			ans+=Mo-tmp; if (ans>=Mo) ans-=Mo;
		}
	}
	cout<<(ans%Mo+Mo)%Mo<<endl;
	return 0;
}

/*
4
0 0
0 1
1 0
1 1

*/


Measured memory_bytes: 12544
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

const int MAX_N = 10000;

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

    string s;

    cin >> s;

    int l = -1;
    int r = -1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == s[i + 1]) {
            l = i + 1;
            r = i + 2;
            break;
        }
        if (s[i] == s[i + 2]) {
            l = i + 1;
            r = i + 3;
            break;
        }
    }

    cout << l << " " << r << "\n";

    return 0;
}

Measured memory_bytes: 3724
N = int(input())
Flists = [list(map(int, input().split())) for _ in range(N)]
Plists = [list(map(int, input().split())) for _ in range(N)]

ans = -10**9
for i in range(1, 2**10):
    open = []
    for j in range(10):
        if ((i>>j) & 1):
            open.append(1)
        else:
            open.append(0)
    money = 0
    for num in range(N):
        Flist = Flists[num]
        same = sum([int(open[_] and Flist[_]) for _ in range(10)])
        money += Plists[num][same]
    ans = max(ans, money)

print(ans)


Measured memory_bytes: 3064
N,K=map(int,input().split())
d=list(map(int,input().split()))

flag=0

for i in range(100000):
    S=N+i
    flag=0
    for j in range(len(str(S))):
        if int(str(S)[j]) not in d:
            flag+=1
            if flag==len(str(S)):
                print(S)
                break
    else:
        continue
    break

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

using namespace std;

const int MN = 100010;
int n, m;
int dp[MN];
bool used[MN];
vector<int> g[MN];

int dfs(int v) {
    if (used[v]) return dp[v];
    for (int i = 0; i < int(g[v].size()); i++) {
        int u = g[v][i];
        dp[v] = max(dp[v], dfs(u) + 1);
    }
    used[v] = true;
    return dp[v];
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        g[a].push_back(b);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dfs(i));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8320
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n; cin >> n;
  vector<int> s(n); REP(i, n) cin >> s[i];
  ll ans = 0;
  FOR(c, 1, n - 1) {
    int l = 0, r = n - 1;
    ll score = 0;
    for (; (n - 1) % c == 0 ? l < r : l + c < n - 1; l += c, r -= c) {
      score += s[l] + s[r];
      chmax(ans, score);
    }
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 3720
import numpy as np
N,Q = map(int,input().split())
S = np.array([b' '] + list(input()), dtype='S1')
A = (S == b'A')
C = (S == b'C')
AC = (A[:-1] & C[1:])
AC_cum = AC.cumsum()

for _ in range(Q):
  L,R = map(int,input().split())
  print(AC_cum[R-1] - AC_cum[L-1])


Measured memory_bytes: 16424
#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    #n=int(input())
    s,w= map(int, sys.stdin.readline().split(' '))
    if s>w:
        print("safe")
    else:
        print("unsafe")
    #a=list(map(int,sys.stdin.readline().split(' ')))
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=3005;
double dp[N][N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
	cin>>n;
	vector<double> p(n);
	for(auto& it:p) cin>>it;
	dp[1][1]=p[0];
	dp[1][0]=1-p[0];
	for(int i=2;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(j==0) dp[i][j]=dp[i-1][j]*(1-p[i-1]);
			else dp[i][j]=dp[i-1][j-1]*p[i-1]+dp[i-1][j]*(1-p[i-1]);
		}
	}
	double ans=0;
	for(int i=(n+1)/2;i<=n;i++) ans+=dp[n][i];
	cout<<fixed<<setprecision(10)<<ans;
    return 0;
}



Measured memory_bytes: 69120
function main(input: string) {
  const [A1,A2,A3] = input.split(" ").map(v => parseInt(v));
  console.log(A1+A2+A3 <= 21 ? "win" : "bust");
}

main(
  require("fs")
    .readFileSync("/dev/stdin", "utf8")
    .trim()
);


Measured memory_bytes: 7372
N, X, Y = map(int, input().split())
path = [0]*N
X -= 1
Y -= 1
# dis = Y - X - 1
# routeA = N - dis
# print(path)
for q in range(N):
    for i in range(q+1, N):
        # print("{}{}".format(q,i))
        cost = min(i-q, abs(q-X) + 1 + abs(i-Y)) 
        # cost = min(i-q, abs(q-X) + 1 + abs(i-Y), abs(q-Y) + 1 + abs(i - X)) 
        # print(cost)
        path[cost] += 1
        # path.append(list(cost)[0])
        # path[q][i] = min(i-q, abs(q-X) + 1 + abs(i-Y)
for i in range(1,N):
    print(path[i])        

Measured memory_bytes: 3444
/*
AizuOnline A0218
Title Dividing Students
*/
#include <stdio.h>
// Select Below
//#include <stdlib.h>
//#include <string.h>
//#include <float.h>
//#include <math.h>
//#include <limits.h>
//Global data section
int n;
int pe,pm,pj;
//
main()
{
        int i;
        int av,avme;

        while(EOF!=scanf("%d",&n) && n)
        {
                for(i=0;i<n;i++)
                {
                        scanf("%d %d %d",&pm,&pe,&pj);
                        av =(pe+pm+pj)/3;
                        avme=(pe+pm)/2;
                        if(pe==100 || pm==100 ||pj==100||av >= 80 ||avme >=90)
                                printf("A\n");
                        else if ((av>=70)||(av>=50 && (pe>=80||pm>=80)))
                                printf("B\n");
                        else
                                printf("C\n");
                }
        }
return(0);
}

Measured memory_bytes: 584
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int main(){
    for(int x = 1; x <= 9; x++){
        for(int y = 1; y <= 9; y++){
            printf("%dx%d=%d\n", x, y, x * y);
        }
    }
    return 0;
}

Measured memory_bytes: 1096
import math
N,D=list(map(int,input().split()))
Z=[ list(map(int,input().split(" "))) for i in range(N)]
D=float(D)
c=0
for i in range(N):
    t=math.sqrt((Z[i][0])**2+(Z[i][1])**2)
    if D>=t:
        c+=1
print(c)

Measured memory_bytes: 102624
import collections

def solve(k, r):
    count = {}
    ans = 0
    for i, n in enumerate(r):
        target = i-n
        ans += count.get(target, 0)
        count[i+n] = count.get(i+n, 0)+1
    return ans
k = int(input())
r = list(map(int, input().split()))
print(solve(k, r))

Measured memory_bytes: 40568
import sys
input = sys.stdin.readline

def main():
    s = input().strip()[::-1]

    while True:
        ok = False
        if len(s) >= 7:
            if s[:7] == "remaerd":
                s = s[7:]
                ok = True
        if len(s) >= 6:
            if s[:6] == "resare":
                s = s[6:]
                ok = True
        if len(s) >= 5:
            if s[:5] == "esare" or s[:5] == "maerd":
                s = s[5:]
                ok = True
        if not ok:
            break
    
    # print(s)
    if len(s) > 0:
        print("NO")
    else:
        print("YES")

if __name__ == "__main__":
    main()

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

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
lld b[1000000];
lld a[1000000];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin>>n;
  
  rep(i,0,n-1)cin>>b[i];
  
  rep(i,0,n){
    a[i]=1000000000000;
    
  }
  rep(i,0,n-1)a[i]=min(a[i],b[i]);
  rep(i,0,n-1)a[i+1]=min(a[i+1],b[i]);
  lld ans=0;
  rep(i,0,n){
    
    ans+=a[i];
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2304
using System;
using System.Linq;///
public class A{
    public static void Main(){
        string s = Console.ReadLine();
        var s_ = s.GroupBy(x=>x);///?
        //Console.WriteLine(s_.GetType() );
        //  System.Linq.GroupedEnumerable`3[System.Char,System.Char,System.Char]
        bool f = s_. All(x=>x.Count()==2);///?
        if (f){
            Console.WriteLine("Yes");
        }
        else{
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 13280
#include <bits/stdc++.h>
#define max(a,b,c) max(max(a,b),c)
using namespace std;
using ll = long long;

const ll p = 1000000007;

ll fac[100010], facm[100010];

ll qpow(ll a, ll n)
{
	ll x = a;
	ll ans = 1;
	while(n)
	{	
		if(n & 1)
		{
			ans *= x;
			ans %= p;
		}
		n >>= 1;
		x *= x;
		x %= p;
	}
	return ans;
}

ll C(ll n,ll k)
{
	if(k > n) return 0ll;
	ll ans = fac[k] * fac[n - k] % p;
	ans = (fac[n] * qpow(ans, p - 2ll)) % p;
	return ans;
}

int a[100010];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fac[0] = 1;
	for(int i = 1; i < 100010; i++)
	{
		fac[i] = (fac[i - 1] * i) % p;
	}
	ll n, x, d;
	cin >> n;
	for (int i = 1; i <= n + 1; ++i)
	{
		cin >> x;
		if (!a[x])
		{
			a[x] = i;
		}
		else
		{
			d = n + 1 - (i - a[x] + 1);
			break;
		}
	}
	for (int i = 1; i <= n + 1; ++i)
	{
		cout << (C(n + 1, i) -  C(d, i - 1) + p) % p << endl;
	}
	return 0;
}

Measured memory_bytes: 2432
H,W=map(int,input().split())
a=[0]*H
result=[]
for i in range(H):
  a[i] = list(map(int,input().split()))
  for j in range(W-1):
    if(a[i][j]%2):
      result.append("{} {} {} {}".format(i+1,j+1,i+1,j+2))
      a[i][j+1] += 1
for i in range(H-1):
  if(a[i][-1]%2):
    result.append("{} {} {} {}".format(i+1,W,i+2,W))
    a[i+1][-1] += 1

print(len(result))
for i in range(len(result)):
  print(result[i])

Measured memory_bytes: 16372
#include <stdio.h>

int main(void)
{
	int a;
	int b;
	int c;

	scanf("%d%d%d", &a, &b, &c);

	if (a <= b && b <= c)
	{
		printf("%d %d %d\n", a, b, c);
	}

	else if (a <= c && c <= b)
	{
		printf("%d %d %d\n", a, c, b);
	}


	else if (b <= a && a <= c)
	{
		printf("%d %d %d\n", b, a, c);
	}

	else if (b <= c && c <= a)
	{
		printf("%d %d %d\n", b, c, a);
	}

	else if (c <= a && a <= b)
	{
		printf("%d %d %d\n", c, a, b);
	}

	else if (c <= b && b <= a)
	{
		printf("%d %d %d\n", c, b, a);
	}

	getchar();
	return 0;
}

Measured memory_bytes: 1032
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int x, h;
        cin >> x >> h;
        if(x == 0)
            return 0;

        double y = sqrt(h*h + x*x/4.0);
        double s = x * x + (x * y) * 2;
        printf("%.10f\n", s);
    }
}

Measured memory_bytes: 0
// Problem : A - Placing Marbles
// Contest : AtCoder - AtCoder Beginner Contest 081
// URL : https://atcoder.jp/contests/abc081/tasks/abc081_a
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
	string s;cin>>s;
	int cnt=0;
	for(char c:s)
	cnt+=(c=='1');
	cout<<cnt;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3652
#include <iostream>
//#include <vector>
#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL a;
    LL b;
    string s;
    bool is_ok=true;
    cin >> a >> b;
    cin >> s;
    if(a+b+1!=s.size()){
        is_ok=false;
    }else if(s[a]!='-'){
        is_ok=false;
    }else{
        for(LL i=0; i<a; i++){
            LL tmp=s[i]-'0';
            if(tmp<0 || tmp>9){
                is_ok=false;
            }
        }
        for(LL i=a+1; i<a+b+1; i++){
            LL tmp=s[i]-'0';
            if(tmp<0 || tmp>9){
                is_ok=false;
            }
        }
    }

    if(is_ok==true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second
//#define int   long long
#define ll   long long
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

ll h, w;
string s[22]; 
vector <pair <ll, ll> > ad[22][22];

ll bfs(ll i, ll j)
{
//	trace2(i, j);
	ll p, q1;
	ll vis[22][22];
	fr(p,0,22)
		fr(q1,0,22)	
			vis[p][q1] = 0;
	ll mx = 0;
	queue <pair <pair <ll, ll>, ll> > q;
	q.push(mp(mp(i, j), 0));
	vis[i][j] = 1;
	while(!q.empty())
	{
		pair <pair <ll, ll>, ll> pr = q.front();
		q.pop();
		fr(p,0,ad[pr.ff.ff][pr.ff.ss].size())
		{
			if(vis[ad[pr.ff.ff][pr.ff.ss][p].ff][ad[pr.ff.ff][pr.ff.ss][p].ss])
				continue;
			vis[ad[pr.ff.ff][pr.ff.ss][p].ff][ad[pr.ff.ff][pr.ff.ss][p].ss] = 1;
			mx = max(mx, pr.ss + 1);
			q.push(mp(ad[pr.ff.ff][pr.ff.ss][p], pr.ss + 1));
		}
	}
	return mx;
}

int main()
{
	FAST;
	ll i, j, k;
	cin >> h >> w;
	fr(i,0,h)
		cin >> s[i];
	fr(i,0,h)
		fr(j,0,w)
		{
			if(s[i][j] == '#')
				continue;
			if((i + 1 < h)&&(s[i+1][j] == '.'))
				ad[i][j].pb(mp(i+1,j));
			if((i - 1 >= 0)&&(s[i-1][j] == '.'))
				ad[i][j].pb(mp(i-1,j));
			if((j + 1 < w)&&(s[i][j+1] == '.'))
				ad[i][j].pb(mp(i,j+1));
			if((j - 1 >= 0)&&(s[i][j-1] == '.'))
				ad[i][j].pb(mp(i,j-1));
		}
	ll mx = 0;
	fr(i,0,h)
		fr(j,0,w)
			mx = max(mx, bfs(i, j));
	cout << mx;
}


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

using namespace std;
typedef long long i64;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef unordered_set<int> si;
typedef pair<int, int> ii;

#define mp make_pair
#define all(n) (n).begin(), (n).end()

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename T>
void printV(vector<T> A) {
    if (A.empty()) cerr << "EMTPY\n";
    else { 
        cerr << "\n[";
        for (int i = 0; i < A.size() -1 ; ++i) {
            cerr << A[i] << ", ";
        }
        if (A.size()) cerr << A.back() << "]\n";
    }
}


template <typename T>
void printVV(vector<vector<T>> A) {
    cerr << "\n[";
    for (auto v : A) {
        printV<T>(v);
    }
    cerr << "]\n";
}

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cerr << name << ": " << arg1 << endl;
}

template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&& ...args) {
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << " |";
    __f(comma + 1, args...);
}

int main(int argc, char **argv) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
    return 0;
}


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

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];
  int tmp = 1;
  for (int t : A)
    if (t % 2 == 0)
      tmp *= 2;
  cout << pow(3, N) - tmp << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>

using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<pair<ll,ll>> dep;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
const int mod=1e9+7;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい

string s,t;


int main(){
	cin>>s>>t;
	int i=s.size()-t.size();
	bool f=false;
	while(i>=0){
		for(int j=0;j<t.size();j++){
			if(s[i+j]==t[j] || s[i+j]=='?'){
				if(j==t.size()-1){f=true;}
			}
			else break;
		}
		if(f){
			for(int j=0;j<t.size();j++){
				s[i+j]=t[j];
			}
			for(int j=0;j<s.size();j++){
				if(s[j]=='?')s[j]='a';
			}
			break;
		}
		i--;
	}
	if(f){
		cout<<s<<endl;
	}
	else cout<<"UNRESTORABLE"<<endl;
	
	return 0;
}



Measured memory_bytes: 256
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <pair <ll,ll> ,ll> &a,const pair <pair <ll,ll> ,ll> &b){
    if(a.first.first==b.first.first && a.first.second==b.first.second) return a.second>b.second;
    else if(a.first.second==b.first.second) return a.first.first>b.first.first;
    return a.first.second<b.first.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}


int main(){
    IOS;
    make(ll,n);
    makevec(double,vec,n);
    vector <vector <double> >dp(n+1,vector <double>(n+1));
    for(ll i=0;i<=n;i++){
        for(ll j=0;j<=n;j++){
            if(i==0 && j==0) dp[i][j]=1;
            else if(j>i || i==0) dp[i][j]=0;
            else dp[i][j]=dp[i-1][j]*(1-vec[i-1])+dp[i-1][j-1]*vec[i-1];
        }
    }
    double ans=0;
    for(ll i=n;i>n/2;i--) ans+=dp[n][i];
    cout<<setprecision(10)<<ans<<endl;


}


Measured memory_bytes: 73728
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int a,b,c,d,e;
int main()
{
	cin>>e;
	d=e%10;
	c=e/10%10;
	b=e/100%10;
	a=e/1000%10;
	if(a+b+c+d==7) cout<<a<<'+'<<b<<'+'<<c<<'+'<<d<<'='<<7; else
		if(a+b+c-d==7) cout<<a<<'+'<<b<<'+'<<c<<'-'<<d<<'='<<7; else
			if(a+b-c+d==7) cout<<a<<'+'<<b<<'-'<<c<<'+'<<d<<'='<<7; else
				if(a-b+c+d==7) cout<<a<<'-'<<b<<'+'<<c<<'+'<<d<<'='<<7; else
					if(a+b-c-d==7) cout<<a<<'+'<<b<<'-'<<c<<'-'<<d<<'='<<7; else
						if(a-b+c-d==7) cout<<a<<'-'<<b<<'+'<<c<<'-'<<d<<'='<<7; else
							if(a-b-c+d==7) cout<<a<<'-'<<b<<'-'<<c<<'+'<<d<<'='<<7; else
								if(a-b-c-d==7) cout<<a<<'-'<<b<<'+'<<c<<'+'<<d<<'='<<7; 
	cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, greater<>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//998244353;
const int base = 2187;
const double eps = 1e-8;
const int N = 200'000;
const int LOGN = 19;

int n, m, k;

void solve(int test)
{
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n - 1; ++i) {
    cin >> b[i];
  }
  a[0] = b[0];
  b[n - 1] = b[n - 2];
  for (int i = 1; i < n; ++i) {
    a[i] = min(b[i - 1], b[i]);
  }
  cout << accumulate(begin(a), end(a), 0ll) << '\n';
}

void precalc()
{
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i)
    solve(i);
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
//#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll quick_power_mod(ll a,ll b,int m)//pow(a,b)%m
{
    a%=m;
	ll result = 1;
	while(b>0)
	{
		if(b&1)
		result=(result*a)%m;
		a=(a*a)%m;
		b>>=1;
	}
	return result;
}
//计算组合数取模
ll comp(ll a,ll b,int p)//composite num C(a,b)%p
{
	if(a<b)return 0;
	if(a==b)return 1;
	if(b>a-b)b=a-b;
	ll ans=1,ca=1,cb=1;
	for(ll i=0;i<b;i++)
	{
		ca=(ca*(a-i))%p;
		cb=(cb*(b-i))%p;
	}
	ans=(ca*quick_power_mod(cb,p-2,p))%p;
	return ans;
}
ll lucas(ll n,ll m,ll p)
{
	ll ans=1;
	while(n&&m&&ans)
	{
		ans=(ans*comp(n%p,m%p,p))%p;//also can be recusive
		n/=p;
		m/=p;
	}
	return ans;
}
int main()
{
	ll m,n,a,b;
	while(cin>>n>>a>>b){
        ll ans=(quick_power_mod(2,n,mod)-1-lucas(n,a,mod)-lucas(n,b,mod)+(ll)3*mod)%mod;
        cout<<ans;
    }
		
	return 0;
}

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    
    int cnt[256] = {};
    for (auto c: s) {
        cnt[c]++;
    }
    
    if (n != 26) {
        char c = 'a';
        while (cnt[c]) c++;
        cout << s << c << endl;
    } else {
        int i = n-2;
        cnt[s.back()]--;
        while (i >= 0 && s[i] > s[i+1]) {
            cnt[s[i]]--;
            i--;
        }
        if (i == -1) {
            cout << -1 << endl;
            return 0;
        }
        char c = s[i];
        while (cnt[c]) c++;
        cout << s.substr(0, i) << c << endl;
    }
    
    return 0;
}

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

int main(){
    int n;cin >> n;
    ll ans = 1;

    int i = 1;

    for(int i = 1; i <= n; i++) {
        ans = (long long)ans*i % 1000000007;
    }

    cout << ans << endl;
	return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

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

    int yui = 0;
    rep(i, n) {
        yui ^= data[i];
    }

    rep(i, n) {
        cout << (yui ^ data[i]) << endl;
    }
    

    return 0;
}


Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "mydebug.h"
#else
#define debug(...)
#endif
typedef long long ll;typedef unsigned long long ul; typedef vector<ll> vl;

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

  vl A;
  for(int i=0;i<K;i++) {
    ll x;
    cin >> x;
    A.push_back(x);
  }

  ll lg=2;
  ll sm=2;

  for(int i=K;i-->0;) {
    ll f=A[i];

    sm=f*(sm/f + ((sm%f)?1:0));

    lg=f*(lg/f) + f-1;

  }

  if(sm>lg)
    cout << -1 << endl;
  else
    cout << sm << " " << lg << endl;

}

Measured memory_bytes: 1400
n, q = map(int, input().split())
arr = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    arr[a-1].append(b)
    
ans = [0 for _ in range(n)] 

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    
for i, c in enumerate(ans):
    for j in arr[i]:
        ans[j-1] += c
            
print(*ans)

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

using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;

  {
    int needToAdd = 0;
    int leftCount = 0;
    for (int i = 0; i < N; i++) {
      if (S[i] == '(') {
        leftCount++;
      } else if (S[i] == ')') {
        if (leftCount == 0) {
          needToAdd++;
        } else {
          leftCount--;
        }
      }
    }
    for (int i = 0; i < needToAdd; i++) S = '(' + S;
    N = S.length();
  }

  {
    int needToAdd = 0;
    int rightCount = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (S[i] == ')') {
        rightCount++;
      } else if (S[i] == '(') {
        if (rightCount == 0) {
          needToAdd++;
        } else {
          rightCount--;
        }
      }
    }
    for (int i = 0; i < needToAdd; i++) S = S + ')';
  }

  cout << S << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, b) for(int i(a); i <= (b); ++i)

template <class T> inline bool smin(T&x, const T&y) { return y < x ? x = y, 1 : 0; }
template <class T> inline bool smax(T&x, const T&y) { return x < y ? x = y, 1 : 0; }

typedef long long ll;

int n;
double f[6005];
#define id(x) (x + n + 1)
int main() {
	scanf("%d", &n);
	f[0] = 1;
	REP(i, 1, n) {
		double x; scanf("%lf", &x);
		for(int j = i; j; --j) f[j] = f[j] * (1 - x) + f[j - 1] * x;
		f[0] *= 1 - x;
	}
	double r = 0;
	REP(i, n / 2 + 1, n) r += f[i];
	printf("%.10f", r);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define pb push_back
//#define ivorysi
#define MAXN 300005
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
    	if(c == '-') f = -1;
    	c = getchar();
    }
    while(c >= '0' && c <= '9') {
    	res = res * 10 + c - '0';
    	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
    	out(x / 10);
    }
    putchar('0' + x % 10);
}
const int MOD = 1000000007;
int dp[MAXN][3][2][2],sum[MAXN],ans,N;
char s[MAXN];
int inc(int a,int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
    return 1LL * a * b % MOD;
}
void update(int &x,int y) {
    x = inc(x,y);
}
int fpow(int x,int c) {
    int res = 1,t = x;
    while(c) {
        if(c & 1) res = mul(res,t);
        t = mul(t,t);
        c >>= 1;
    }
    return res;
}
void Solve() {
    scanf("%s",s + 1);
    N = strlen(s + 1);
    for(int i = N ; i >= 1 ; --i) {
        sum[i] = sum[i + 1] + (s[i] == '?');
    }
    dp[0][0][0][0] = 1;
    for(int i = 1 ; i <= N ; ++i) {
        int t = 0;

        for(int j = 0 ; j <= 2 ; ++j) {
            for(int h = 0 ; h <= 1 ; ++h) {
                for(int k = 0 ; k <= 1 ; ++k) {
                    if(!dp[i - 1][j][h][k]) continue;
                    if(s[i] == '0' || s[i] == '?') {
                        if(k) update(dp[i][1][h][0],dp[i - 1][j][h][k]);
                        else {
                            if(j == 1) update(dp[i][2][h][0],dp[i - 1][j][h][k]);
                            else update(dp[i][1][h][0],dp[i - 1][j][h][k]);
                        }
                    }
                    if(s[i] == '1' || s[i] == '?') {
                        if(k) {
                            if(h) update(t,dp[i - 1][j][h][k]);
                            else update(dp[i][0][h + 1][0],dp[i - 1][j][h][k]);
                        }
                        else {
                            if(j == 1) update(dp[i][0][h][1],dp[i - 1][j][h][k]);
                            if(j == 2) update(dp[i][1][h][0],dp[i - 1][j][h][k]);
                            if(j == 0) {
                                if(h) update(t,dp[i - 1][j][h][k]);
                                else update(dp[i][0][h + 1][0],dp[i - 1][j][h][k]);
                            }
                        }
                    }
                }
            }
        }
        update(ans,mul(t,fpow(2,sum[i + 1])));
    }
    update(ans,inc(dp[N][0][1][1],dp[N][0][1][0]));
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 15744
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,temp;
	while(1){
		cin >> n >> m;
		int a[n+1],sum=0;
		if(n==m && n==0) break;
		for(int i=1;i<=n;i++){
			cin >> a[i];
		}
		for(int i=1;i<n;i++){
			for(int j=i+1;j<n+1;j++){
				if(a[i]<a[j]){
					temp=a[i];
					a[i]=a[j];
					a[j]=temp;
				}
			}
		}
		for(int i=1;i<n+1;i++){
			if(i%m!=0){
				sum+=a[i];
			}
		}
		cout << sum << endl;
	}
}


Measured memory_bytes: 2948
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind
{
public:
    UnionFind(int n) : parent(n), rank(n)
    {
        for(int i = 0; i < n; ++i) parent[i] = i;
    }
    
    int root(int x)
    {
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }
    
    bool same(int x, int y)
    {
        return root(x) == root(y);
    }
    
    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            parent[x] = y;
        } else {
            parent[y] = x;
            if(rank[x] == rank[y]){
                rank[x]++;
            }
        }
    }

private:
    vector<int> parent, rank;
};

struct Edge
{
    int u, v, cost;
    bool operator<(const Edge& rhs) const
    {
        return cost < rhs.cost;
    }
};

vector<Edge> E;

int main()
{
    int n, m, a, b, c;
    while(1){
        E.clear();
        scanf("%d", &n);
        if(n == 0) break;
        scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            scanf("%d,%d,%d", &a, &b, &c);
            Edge e = {a, b, c / 100 - 1};
            E.push_back(e);
        }
        
        sort(E.begin(), E.end());
        
        UnionFind uf(n);
        int ans = 0;
        for(int i = 0; i < E.size(); ++i){
            if(!uf.same(E[i].u, E[i].v)){
                ans += E[i].cost;
                uf.unite(E[i].u, E[i].v);
            }
        }
        printf("%d\n", ans);
    }
}

Measured memory_bytes: 1180
h,w,k=map(int,input().split())
r,s,t,u=map(lambda x:int(x)-1,input().split())
b=[input()for _ in range(h)]
l=[[-1]*w for _ in range(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(print(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      p,q=x+e*i,y+f*i
      if not((0<=p<h)&(0<=q<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
print(-1)

Measured memory_bytes: 93980
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	a := make([]int, 110000)
	b := make([]int, 110000)
	for i := 0; i < N; i++ {
		x := getInt()
		a[x]++
		b[x]++
	}

	for i := 0; i < 100001; i++ {
		b[i+1] += a[i]
	}
	for i := 1; i < 100001; i++ {
		b[i-1] += a[i]
	}
	m := 0
	for i := 0; i < 110000; i++ {
		m = max(m, b[i])
	}
	out(m)
}


Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
vector<int> G[100010];
int col[100010];
void dfs(int s,int c){
    col[s] = c;
    for(int v:G[s]){
        if(col[v]==-1) dfs(v,1 - c);
    }
}

bool bip_ch(int v){
    int i;
    for(i=0;i<v;i++){
        col[i] = -1;
    }
    for(i=0;i<v;i++){
        if(col[i]==-1) dfs(i,0);
    }
    for(i=0;i<v;i++){
        for(int ver:G[i]){
            if(col[i]==col[ver]) return false;
        }
    }
    return true;
}

int par[100010],sz[100010],wh[100010];
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i; sz[i] = 1; wh[i] = col[i];
	}
}

int find(int x){
	if(par[x]==x) return x;
	return par[x] = find(par[x]);
}

void unite(int x, int y){
	x = find(x); y = find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	par[x] = y;
	sz[y] += sz[x]; wh[y] += wh[x];
}

bitset<100010> dp1,dp2;
int main(){
    long long i,j,n,m;
    cin >> n >> m;
    for(i=0;i<m;i++){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b); G[b].push_back(a);
    }
    if(!bip_ch(n)){
        cout << -1 << endl;
        return 0;
    }
    init(n);
    for(i=0;i<n;i++){
        for(int v:G[i]){
            unite(v,i);
        }
    }
    dp1[0] = 1;
    for(i=0;i<n;i++){
        if(par[i]==i){
            dp2 = (dp1<<wh[i]);
            dp2 |= (dp1<<(sz[i] - wh[i]));
            dp1 = dp2;
        }
    }
    for(i=n/2;i>=0;i--){
        if(dp1[i]){
            cout << i*(n - i) - m << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 10820
l, r = map(int, input().split())
if r - l >= 2019:
    print(0)
    exit()
minn = 2*(10**9)*2
for i in range(l, r+1):
    for j in range(i+1, r+1):
        minn = min(minn, i * j % 2019)
print(minn)

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<list>
#include<deque>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
#include<numeric>

using namespace std;

using ll = int64_t;

/// <summary>
/// 単純なcoutの時に使う
/// </summary>
#define co(a) cout<<a<<"\n"


/// <summary>
/// [beg, end)の範囲を，添え字indexでループするfor文に置換します
/// </summary>
#define rep(i,a) for(ll i=0; i<a; ++i)
#define reps(i, a, b) for(ll i = a; i < b; ++i)

/// <summary>
/// 迷路等で使う方向のベクトル
/// </summary>
const vector<ll> dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };

/// <summary>
/// デバッグ時に使う
/// </summary>
#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

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

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

	ll N, D;
	cin >> N >> D;

	vector<vector<ll>> X (N, vector<ll> (D));

	rep (y, N) {
		rep (x, D) {
			cin >> X[y][x];
		}
	}

	ll ans = 0;

	double hoge = 0;
	rep (j, N - 1) {
		reps (i, j + 1, N) {
			hoge = 0;
			rep (a, D) {
				hoge += (X[i][a] - X[j][a]) * (X[i][a] - X[j][a]);
			}

			if (sqrt (hoge) == (int)(sqrt (hoge))) {
				++ans;
			}
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
n, m, q = map(int, input().split())
queries = [tuple(map(int, input().split())) for _ in range(q)]
arr = []

def f(p):
    if len(p) == n+1:
        arr.append(p[:-1])
        return
    while p[-1] <= m:
        f(p + [p[-1]])
        p[-1] += 1

f([1])

ans = 0
for p in arr:
    score = 0
    for a, b, c, d in queries:
        if p[b-1] - p[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)


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

using namespace std;

int main(void){
    string s1, s2;
    cin >> s1 >> s2;
    if(s1[0] == s2[2] && s1[1] == s2[1] && s1[2] == s2[0]){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
    int N,M;
    cin >> N >> M;
    cout << (1800*M+100*N)/(1/pow(2,M)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
#include <cmath>

using namespace std;

int arr[100010];
int cnt[2][100010];
int mx[2], mx2[2], a[2], b[2];

int main()
{
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int n, i;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    for(i = 0; i < n; i++)
        cnt[i % 2][arr[i]]++;

    for(int t = 0; t < 2; t++)
    {
        for(i = 1; i <= 100000; i++)
        {
            if(cnt[t][i] > mx[t])
            {
                mx2[t] = mx[t];
                b[t] = a[t];

                mx[t] = cnt[t][i];
                a[t] = i;
            }
            else if(cnt[t][i] > mx2[t])
            {
                mx2[t] = cnt[t][i];
                b[t] = i;
            }
        }
    }

    int r;
    if(a[0] != a[1])
        r = n - mx[0] - mx[1];
    else
        r = min(n - mx[0] - mx2[1], n - mx[1] - mx2[0]);
    
    printf("%d\n", r);
    return 0;
}

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

bool judge(int check)
{
    if(check % 2 == 0)
        return true;
    else
        return false;
}
// trueは偶数
// falseは奇数

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    int ans = 0;
    //一応while
    while(1)
    {
        if(judge(A) == judge(B) && judge(B) == judge(C)) break;

        if(judge(A) == judge(B))
        {
            ++A;
            ++B;
            ++ans;
        }
        else if(judge(A) == judge(C))
        {
            ++A;
            ++C;
            ++ans;
        }
        else if(judge(B) == judge(C))
        {
            ++B;
            ++C;
            ++ans;
        }
    }

    //cout << ans;
    ans += ( max(max(A,B), max(A,C)) - A ) / 2;
    //cout << ans;
    ans += ( max(max(A,B), max(A,C)) - B ) / 2;
    //cout << ans;
    ans += ( max(max(A,B), max(A,C)) - C ) / 2;
    //cout << ans;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define db double
const db pi=acos(-1);

int n, l, a[3030];
db anx, any;

int main(){
    cin>>n>>l;
    for (int i=1;i<=n;++i) cin>>a[i];
    sort(a+1,a+n+1);
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j){
            db p1=(a[i]+a[j])*pi/l, p2=p1+pi;
            int c1=n-(j-i+1), c2=j-i-1;;
            anx+=cos(p1)*c1+cos(p2)*c2;
            any+=sin(p1)*c1+sin(p2)*c2;
        }
    db fm=1./6*n*(n-1)*(n-2);
    printf("%.10lf %.10lf\n",anx/fm,any/fm);
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void){
    char sd[52] = "0000000000000000000000000000000000000000000000000000";
    char t[52] = "0000000000000000000000000000000000000000000000000000";
    scanf("%s",sd);
    scanf("%s",t);
    int i;
    int lent;
    for(i=0;i<52;i++){
        if(t[i]<'a' || t[i]>'z'){
            lent = i;
            break;
        }
    }
    int lensd;
    for(i=0;i<52;i++){
        if((sd[i]<'a' || sd[i]>'z') && (sd[i] != '?')){
            lensd = i;
            break;
        }
    }
    int j;
    int hairu = 0;
    for(i=lensd-lent;i>=0;i--){
        int muri = 0;
        for(j=i;j<i+lent;j++){
            if(sd[j] != '?'){
                if(sd[j] != t[j-i]){
                    muri++;
                }
            }
        }
        if(muri == 0){
            hairu = i;
            goto UNKO;
        }
    }
    printf("UNRESTORABLE");
    printf("\n");
    return 0;
UNKO:
    for(i = hairu; i<hairu+lent;i++){
        sd[i] = t[i-hairu];
    }
    for(i=0;i<52;i++){
        if(sd[i] == '?'){
            sd[i] = 'a';
        }
    }
    printf("%s",sd);
    printf("\n");
    return 0;
}

Measured memory_bytes: 128