akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long 
using namespace std;
using Graph = vector<vector<int>>;


signed main() {
  int N, M;
  cin >> N >> M;
  
  vector<pair<int, int>> hen(M);
  Graph G(N);
  int A, B;
  for( int i = 0; i < M; i++ ){
    cin >> A >> B;
    A--;
    B--;
    hen.at(i) = make_pair(A, B);
    G.at(A).push_back(B);
    G.at(B).push_back(A);
  }
  
  int ans = 0;
  for( int i = 0; i < M; i++ ){ //取り除く辺
    vector<int> dist(N, -1); //まだ見てない頂点を-1とする
    queue<int> que;
    dist.at(0) = 0;
    que.push(0);
    
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nextv : G.at(v) ){
        if( (v == hen.at(i).first && nextv == hen.at(i).second) || (v == hen.at(i).second && nextv == hen.at(i).first) ){
          continue;
        }
        if( dist.at(nextv) != -1 ) continue;
        dist.at(nextv) = dist.at(v)+1;
        que.push(nextv);
      }
    }
    
    
    for( int j = 0; j < N; j++ ){
      if( dist.at(j) == -1 ){
        ans++;
        break;
      }
    }
  }
  cout << ans << endl;
  
  
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		char[] input = sc.next().toCharArray();

		int n = input.length + 1;
		int a[] = new int[n];

		for(int i = 1; i < n; i++){
			if(input[i - 1] == '<'){
				a[i] = a[i - 1] + 1;
			}
			else {
				a[i] = 0;
			}
		}

		for(int i = n - 2; i >= 0; i--){
			if(input[i] == '>'){
				a[i] = Math.max(a[i], a[i + 1] + 1);
			}
		}

		long sum = 0;
		for(int i = 0; i < n; i++){
//			System.out.println(a[i]);
			sum += a[i];
		}

		System.out.println(sum);
	}

}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

std::vector<std::vector<long long>> comb(int n, int r)
{
    std::vector<std::vector<long long>> v(n + 1, std::vector<long long>(n + 1, 0));
    for (int i = 0; i < v.size(); i++)
    {
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for (int j = 1; j < v.size(); j++)
    {
        for (int k = 1; k < j; k++)
        {
            v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
        }
    }
    return v;
}

int main()
{
    lint n;cin >> n;
    vector<lint> a(n);
    REP(i, n) { cin >> a[i]; }
    lint ans=0;
    vector<lint> s(n+1);

    REP(i,n){
        s[i + 1] = s[i] + a[i];
    }
    sort(ALL(s));

    lint pre = 0, count = 0;
    //int ans = 0;
    //vector<std::vector<lint>> v(n + 1, vector<lint>(n + 1, 0));
    //v = comb(n + 1, n + 1);

    REP(i, n+1)
    {
        lint c=s[i];
        if (i == 0)
        {
            pre = c;
        }
        if (pre == c)
        {
            count += 1;
        }
        else
        {
            if (count != 1)
            {
                //cout << count << " ";
                //ans += v[count][2];
                ans += count * (count - 1) / 2;
            }
            count = 1;
        }
      // cout << count << " ";
        pre = c;
    }
    //count += 1;
    if (count != 1)
    {
        //ans += v[count][2];
        ans += count * (count - 1) / 2;
    }

    cout << ans <<"\n";

    return 0;
}

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

using namespace std;
#define rep(i, l, r) for (int i = l; i<r;i++)
#define dec(i, l, r) for (int i = l; i>=r;i--)
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define pb(c) push_back(c)
#define vii vector<pair<int,int>>
#define ii pair<int,int>
#define max(a, b) (((a)<(b))?b:a)
#define min(a, b) ((a>b)?b:a)
#define mp(i, j) make_pair(i,j)
#define ull unsigned long long int
#define ll  long long int
#define pi 3.141592653589793238
#define inf ((ll)1e18)
#define eps 1e-14
#define mod ((int)1e9+7)
#define maxlg 18
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define maxn 400006
vi x ,y;
bool dp[8001][8001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
 #endif
    string s;
    cin>>s;
    int t[2]={0};
    char type=0;
    int st=0;

    rep (i,0,s.length()) {
        if (s[i]=='F') {
             st++;
        } else {
            t[type]+=st;
            if (type==0  )x.push_back(st);
            else if (type==1  )y.push_back(st);
            st=0;
            type = type^1;

        }
    }
    if (type==0  )x.push_back(st);
    else if (type==1  )y.push_back(st);
    t[type]+=st;
    int X,Y;
    cin>>X>>Y;
    int xx=X,yy=Y;
    X = X-x[0];
    t[0]-=x[0];
    x[0]=0;

    X =abs(X),Y=abs(Y);

    if (abs(t[0]-X)%2==1 || abs(t[1]-Y)%2==1) {
        cout<<"No";
        return 0;
    }
    int needx = X+abs(t[0]-X)/2;
    int needY = Y+abs(t[1]-Y)/2;
    if (needx>8000 || needY>8000 || needx<0 || needY<0) {
        cout<<"No";
        return 0;
    }
    dp[x.size()][0]=true;

    for (int i=x.size()-1;i>=0;i--)
        rep (j,0,needx+1) {
            //miss
            dp[i][j] |= dp[i+1][j];
            if (j-x[i]>=0)
                dp[i][j] |= dp[i+1][j-x[i]];

        }

    bool ans = dp[0][needx];
    fill(&dp[0][0],&dp[0][0]+8001*8001,false);
    dp[y.size()][0]=true;
    for (int i=y.size()-1;i>=0;i--)
        rep (j,0,needY+1) {
            //miss
            dp[i][j] |= dp[i+1][j];
            if (j-y[i]>=0)
                dp[i][j] |= dp[i+1][j-y[i]];

        }
      ans = ans&dp[0][needY];
    if (ans)cout<<"Yes";
    else cout<<"No";

    return 0;
}








Measured memory_bytes: 62976
#include<stdio.h>
int main() {
    int a,b,d;
    scanf("%d%d",&a,&b);
    d=a%500;
    if(d<=b){
        printf("Yes\n");
    }
    else if(a<500&&a<=b){
        printf("Yes\n");
    } else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
using System;

class Rectangle {
    
    static void Main(){
        
        string[] str = Console.ReadLine().Split(' '); 
        // ''?????§?????????????????????????????°???????????£??????????????????str?????????????´??????????
        var a = int.Parse(str[0]);
        var b = int.Parse(str[1]);

        int area = a * b;
        int circuit = (2 * a) + (2 * b) ;
        Console.WriteLine(area + " " + circuit);
    }
    
}

Measured memory_bytes: 9212
import collections
n = int(raw_input())
ais = map(int, raw_input().split(' '))
cco = collections.Counter([ais[i] for i in range(len(ais)) if i % 2])
cce = collections.Counter([ais[i] for i in range(len(ais)) if i % 2 == 0])
cce = [(cce[k],k) for k in cce]
cce.sort(key = lambda x:-x[0])

t = n/2
if cce:
	m = t + t- cce[0][0]
else:
	m = 2*t
for colori in cco:
	for v,colorj in cce:
		if colorj != colori:
			m = min(m,t - cco[colori] + t - v)
			break

print m

Measured memory_bytes: 105352
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	long long k, i = 0;
	cin >> s >> k;
	i -= k;
	for (char c : s)
		if (!++i || c - '1')
			return cout << c << endl, 0;
}

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

int main(){
  long long int n;
  cin>>n;
  vector <long long int> a(n);
  for(int i=0;i<n;i++)
    cin>>a[i];
  sort(a.begin(),a.end());
  long long num=0;
  for(int i=1;i<n;i++){
    for(int j=i-1;j>=1;j--){
      int y=a[i]-a[j]+1;
      int index=lower_bound(a.begin(),a.end(),y)-a.begin();
      if(index<j)
         num=num+j-index;
    }
  }
  cout<<num;
}
              
    


Measured memory_bytes: 256
#include <bits/stdc++.h>
/* Karen {{{
  ___  ____
 |_  ||_  _|
   | |_/ /    ,--.   _ .--.  .---.  _ .--.
   |  __'.   `'_\ : [ `/'`\]/ /__\\[ `.-. |
  _| |  \ \_ // | |, | |    | \__., | | | |
 |____||____|\'-;__/[___]    '.__.'[___||__]
}}} */
/* cpp template {{{*/
using namespace std;

#define endl '\n'

#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
#define RREP(i, n) for (int i = 1; i <= (n); i++)
#define X real()
#define Y imag()
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ALL(v) v.begin(), v.end()

typedef double D;
typedef long long ll;
typedef long double lb;
typedef complex<D> P;
typedef vector<P> VP;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<string, int> psi;

inline bool inside(int y,int x,int H,int W){return(y>=0&&x>=0&&y<H&&x<W);}
inline int in() {int x; std::cin >> x; return x;}

template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << endl;
}
template <typename T>
void print(T x) {
  std::cout << x << '\n';
}
/* }}} */
/* 定数 {{{*/
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 9;
const D EPS  = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
/* }}} */

#define int long long

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

  int W = in(), H = in();
  vector<pair<int, bool> > cost;

  REP(i, W) {
    int p = in();
    cost.pb(mp(p, true));
  }
  REP(i, H) {
    int q = in();
    cost.pb(mp(q, false));
  }

  W++; H++;
  sort(ALL(cost));

  ll ans = 0;
  vector<pair<int, bool> >::iterator it = cost.begin();

  for (; it != cost.end(); it++) {
    if ((*it).se){
      ans += ((*it).fi * H);
      W--;
    } else {
      ans += ((*it).fi * W);
      H--;
    }
  }

  cout << ans << endl;

}



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

 
int main() {
    int n;
    cin >> n;
    int cnt = 0;
    int a;
    rep(i,n){
        cin >> a;
        if((i+1)%2 == 1 && a%2 == 1) cnt++;
        }
    cout << cnt << endl;
}


Measured memory_bytes: 3560
n=int(input())
x=[]
for _ in range(n):
    a,b=map(int,input().split())
    x.append([a,b,b-a])

x.sort(key=lambda x:(x[1],x[0]))
t=0
ans='Yes'
for i in range(n):
    if t+x[i][0]<=x[i][1]:
        t+=x[i][0]
    else:
        ans='No'
        break
print(ans)

Measured memory_bytes: 57020
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
xyh.sort(key=lambda x:x[2],reverse=True)
for X in range(0,101):
    for Y in range(0,101):
        f=True
        H=xyh[0][2]+abs(xyh[0][0]-X)+abs(xyh[0][1]-Y)
        for i in range(1,n):
            x,y,h=xyh[i]
            if h==0:
                if H-abs(x-X)-abs(y-Y)>0:
                    f=False
                    break
            else:
                if H-abs(x-X)-abs(y-Y)!=h:
                    f=False
                    break
        if f:
            print(X,Y,H)
            break

Measured memory_bytes: 3064
use std::io;
use std::io::prelude::*;
use std::str::FromStr;

fn main() {
    let stdin = io::stdin();
    let mut data = stdin.lock().lines();
    let (h, w) = {
        let line = data.next().unwrap().unwrap();
        let mut line_split = line.split(' ');
        (i32::from_str(line_split.next().unwrap()).unwrap(),
         i32::from_str(line_split.next().unwrap()).unwrap())
    };
    let mut min_table = [[9999i32; 1000]; 1000];
    for i in 0..h as usize {
        let line = data.next().unwrap().unwrap();
        let mut j = 0usize;
        for wd in line.chars() {
            if wd == '#' {
                min_table[i][j] = 0;
            }
            j += 1;
        }
    }
    // left <-> right
    for i in 0..h as usize {
        for j in 0..(w-1) {
            let cur = j as usize;
            let adj = (j + 1) as usize;
            if min_table[i][adj] > min_table[i][cur] + 1 {
                min_table[i][adj] = min_table[i][cur] + 1;
            }
        }
        for j in 0..(w-1) {
            let cur = (w - 1 - j) as usize;
            let adj = (w - 2 - j) as usize;
            if min_table[i][adj] > min_table[i][cur] + 1 {
                min_table[i][adj] = min_table[i][cur] + 1;
            }
        }
    }
    // up <-> down
    for j in 0..w as usize {
        for i in 0..(h-1) {
            let cur = i as usize;
            let adj = (i + 1) as usize;
            if min_table[adj][j] > min_table[cur][j] + 1 {
                min_table[adj][j] = min_table[cur][j] + 1;
            }
        }
        for i in 0..(h-1) {
            let cur = (h - 1 - i) as usize;
            let adj = (h - 2 - i) as usize;
            if min_table[adj][j] > min_table[cur][j] + 1 {
                min_table[adj][j] = min_table[cur][j] + 1;
            }
        }
    }
    let mut maxv = 0;
    for i in 0..h as usize {
        for j in 0..w as usize {
            if min_table[i][j] > maxv {
                 maxv = min_table[i][j];
            }
        }
    }
    println!("{}", maxv);
}

Measured memory_bytes: 8188
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<map>
#include<cmath>
#define ll long long
#define inf 0x7fffffff;
#define maxn 1005
using namespace std;
int s,w; 
int read()
{
    int l=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        w=-1;
        else
        ch=getchar();
    }
    while(ch<='9'&&ch>='0')
    {
        l*=10;
        l+=ch-'0';
        ch=getchar();
    }
    return l*w;
} 

int main()
{
	s=read();
	w=read();
	if(w>=s)
	printf("unsafe");
	else
	printf("safe");
	return 0;
} 

Measured memory_bytes: 3772
#include<iostream>
#define ll long long
using namespace std;
int main(){
    ll N,W;
    cin>>N>>W;
    ll a[N],w[N],dp[N+1][W+1]={0};
    for (int i = 0; i < N; ++i)
    {
        cin>>a[i]>>w[i];
    }
    for (ll i = 0; i < N+1; ++i)
    {
        for (ll j = 0; j < W+1; ++j)
        {
            if(j==0 || i==0)
                dp[i][j]=0;
            else if(a[i-1]<=j)
                dp[i][j]=max(dp[i-1][j],w[i-1]+dp[i-1][j-a[i-1]]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[N][W]<<endl;




    return 0 ;
}

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

int main(){
  int n;
  //vector<int> p;
  int res = 0;
  cin >> n;
  int p[n];
  for(int i=0;i<n;i++){
    cin >> p[i];
  }

  for(int i = 0;i<n-2;i++){
    if(p[i] < p[i+2]){
      if(p[i] < p[i+1] && p[i+1] < p[i+2]) res++;
    }
    if(p[i] > p[i+2]){
      if(p[i] > p[i+1] && p[i+1] > p[i+2]) res++;
    }
  }
  cout << res << endl;
  return 0;
}


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

const ll MAX = 2e5 + 1;
ll MOD = 1e9 + 7;
ll INV[MAX] = {}, FACTORIAL[MAX] = {}, FACTORIAL_INV[MAX] = {};

void calc_init() {
  INV[1] = 1;
  FACTORIAL[0] = FACTORIAL[1] = 1;
  FACTORIAL_INV[0] = FACTORIAL_INV[1] = 1;

  for (int i = 2; i <= MAX; i++) {
    ll q = MOD / i, r = MOD % i;
    INV[i] = (-INV[r] * q) % MOD;
    INV[i] = (INV[i] + MOD) % MOD;
    FACTORIAL[i] = (i * FACTORIAL[i - 1]) % MOD;
    FACTORIAL_INV[i] = (INV[i] * FACTORIAL_INV[i - 1]) % MOD;
  }
}

ll nCk(ll n, ll k) {
  ll ans = FACTORIAL[n];
  ans = (ans * FACTORIAL_INV[k]) % MOD;
  ans = (ans * FACTORIAL_INV[n - k]) % MOD;
  return ans;
}

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

  calc_init();

  ll N; cin >> N;
  ll K; cin >> K;
  vector<ll> A(N, 0);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A.begin(), A.end());

  ll ans = 0;
  ll all = nCk(N, K);
  for (int i = 0; i < N - 1; i++) {
    ll c = all + 2 * MOD;
    if (i + 1 >= K) c -= (nCk(i + 1, K));
    if (N - i - 1 >= K) c -= (nCk(N - i - 1, K));
    c %= MOD;

    ans += c * (A[i + 1] - A[i]);
    ans %= MOD;
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1e11

int n,m;
map <int,vector <int> > mp;
ll dp[100005];
ll rec(int i)
{
    if(mp[i].size()==0)
        return 0;
    if(dp[i]+1)
        return dp[i];
    ll res=-1;
    for(int j=0;j<mp[i].size();j++)
    {
        res = max(res,1+rec(mp[i][j]));
    }
    return dp[i] = res;
}

int main()
{
    memset(dp,-1,sizeof dp);
    int x,y;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        cin >> x >> y;
        mp[x].push_back(y);
    }
    ll ans=-1;
    for(int i=1;i<=n;i++)
    {
        ans = max(ans,rec(i));
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 15360
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
            if (w == 0 && h == 0) {
                break;
            }
            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    if ((x + y) % 2 == 0) {
                        System.out.print("#");
                    } else {
                        System.out.print(".");
                    }
                }
                System.out.println("");
            }
            System.out.println("");
        }
    }
}



Measured memory_bytes: 36572
#include<cstdio>
using namespace std;
#define N 305
int n,m,p,dp[N][N],su[N][N],c[N][N];
int main()
{
	scanf("%d%d%d",&n,&m,&p);n++;m++;
	for(int i=1;i<=m;i++)dp[1][i]=1,su[1][i]=i;
	for(int i=0;i<=n;i++)c[i][i]=c[i][0]=1;
	for(int i=2;i<=n;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
	for(int i=2;i<=n;i++)
	{
		for(int k=1;k<=m;k++)
		for(int j=1;j<i;j++)
		dp[i][k]=(dp[i][k]+1ll*dp[i-j][k]*su[j][k-1]%p*c[i-2][j-1])%p;
		for(int k=1;k<=m;k++)su[i][k]=(su[i][k-1]+dp[i][k])%p;
	}
	printf("%d\n",dp[n][m]);
}//

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


int main(){
  int N;
  long long int T;
  long long int tmp;
  long long int time=0;
  long long int res=0;
  long long int prev=0;
  cin>>N>>T;
  cin>>tmp;
  for(int i=1;i<N;i++){
    cin>>tmp;
    if((tmp-prev)<=T){time+=tmp-prev;res=T-(tmp-prev);prev=tmp;}
    else {time+=T;res=0;prev=tmp;}
  }
  time+=T;
  
  cout<<time;
  return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int LL;
typedef long double dd;
//#define i_7 (ll)(1E9+7)
#define i_7 998244353
#define i_5 i_7-2

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
//template<class T>void max(T a,T b){if(a<b)return b;else return a;}
//template<class T>void min(T a,T b){if(a>b)return b;else return a;}
//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}
//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}

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

ll gcd(ll a,ll b){
    if(a>=b)swap(a,b);
    if(a==0)return b;
    return gcd(b%a,a);
}

int main(){fastio
    
    ll k;cin>>k;
    ll ans=0;
    rep(i,1,k){
        rep(j,1,k){
            ll g=gcd(i,j);
            rep(p,1,k){
                ans+=gcd(g,p);
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 3648
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
bef=-9999
for i in range(n):
    ans+=b[a[i]-1]
    if bef+1==a[i]-1:
        ans+=c[bef]
    bef=a[i]-1
print(ans)


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

#define sf scanf
#define pf printf
#define pfn printf("\n");
#define ll long long
#define sfd(n) scanf("%d",&n);
#define sfld(n) scanf("%lld",&n);
#define sflf(n) scanf("%lf",&n);
#define sfc(n) scanf("%c",&n);
#define sfs(n) scanf("%s",&n);
#define pfd(n) printf("%d",n);
#define pfld(n) printf("%lld",n);
#define pflf(n) printf("%lf",n);
#define pfc(n) printf("%c",n);
#define pfs(n) printf("%s",n);

#define csh(a,n) memset(a,n,sizeof(a));
int main(){
	char arr[100001];
	cin>>arr;
	int n=strlen(arr);
	char p=arr[0];
	int mi=n;
	for(int i=1;i<n;i++)
	{
		if(arr[i]!=p)
		{
			if(p=='0')
			{
				p='1';
			}
			else{
				p='0';
			}
			mi=min(mi,max(i,n-i));
		}
	}
	cout<<mi<<endl;
}

Measured memory_bytes: 384
N=int(input())
n1=0
n2=0
a=[]
for i in range(N):
    A=int(input())
    a.append(A)
    n2=max(n2,min(n1,A))
    n1=max(n1,A)
for i in range(N):
    if a[i]==n1:
        print(n2)
    else:
        print(n1)


Measured memory_bytes: 12532
#include<bits/stdc++.h>
using namespace std;
const int m=1e9+7;
#define int long long int 
int cal(int x,int y)
{
    int res=1;
    while(y>0)
    {
        if(y&1)
        res=(res*x)%m;
        x=(x*x)%m;
        y=y>>1;
    }
    return res%m;
}
int32_t main(){

    int n;
    cin>>n;
    set<int> s;
    if(n&1)
    {
        int i=0;
        while(i<n)
        {
            s.insert(i);
            i+=2;
        }
    }
    else
    {
        int i=1;
        while(i<n)
        {
            s.insert(i);
            i+=2;
        }
    }

   map<int,int> m;
   for(int i=0;i<n;i++)
   {
       int x;
       cin>>x;
       m[x]++;
   }

    int f=0;
    int power=0;
   for(auto i:m)
   {
       if((m[i.first]!=2||s.find(i.first)==s.end())  && i.first!=0)
       {
           f=1;
           break;
       }
       if(i.first!=0)
       power++;

   }
   if(f)
   cout<<0<<endl;  
   else
    cout<<cal(2,power)<<endl;

   

}

Measured memory_bytes: 9752
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int n,x,total=0;
		int i,j,k;
		Scanner scan = new Scanner(System.in);
		while(true)
		{	
		n=scan.nextInt();
		x=scan.nextInt();
		if(n==0&&x==0)
			break;
		for(i=1;i<=n-2;i++) {
			for(j=i+1;j<=n-1;j++) {
				for(k=j+1;k<=n;k++) {
					if(i+j+k==x)
						total++;
				}
			}
		}
		System.out.println(total);
		total=0;
		}
	}
}



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

const string YES = "Yes";
const string NO = "No";

void solve(std::string S){
    vector<string> v = {"hi", "hihi", "hihihi", "hihihihi", "hihihihihi"};
    bool f = false;
    for(auto a : v){
        if(S == a)f = true;
    }
    if(f)cout<<YES<<endl;
    else cout<<NO<<endl;
}

int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

int main(){
  ll A,B,C;
  cin>>A>>B>>C;
  if (C-B>=0){
    if (C-A>=0){
      cout << B + min(C,((A+B)+1)) << endl;
    }else{
      cout << B+C << endl;
    }
  }else{
    cout << B+C << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <stack>
#include <bitset>
#include <utility>
#include<iomanip>
// #include <numeric>
using namespace std;



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector<vector<ll>> vvint;
typedef vector<string> vstring;
typedef vector<vector<string>> vvstring;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<long double> vdouble;
typedef vector<vector<long double>> vvdouble;
typedef vector<vector<vector<long double>>> vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define INT_MAX 2147483647
#define LLONG_MAX 9223372036854775807
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define DIVIDER 1000000007


//
// struct Node{
//   vint children;
//   ll index;
//   ll prop;
// };
// struct edge{ll to; ll cost;};



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

// ll X,Y,Z,K;
// ll pmax = 30000000000;
// vint A,B,C;




// struct UnionFind {
//     vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
//
//     UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
//         for(int i = 0; i < N; i++) par[i] = i;
//     }
//
//     int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
//         if (par[x] == x) return x;
//         return par[x] = root(par[x]);
//     }
//
//     void unite(int x, int y) { // xとyの木を併合
//         int rx = root(x); //xの根をrx
//         int ry = root(y); //yの根をry
//         if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
//         par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
//     }
//
//     bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
//         int rx = root(x);
//         int ry = root(y);
//         return rx == ry;
//     }
// };
//
// vint divisor(ll n){ // nの約数
//   vint ret;
//   for(ll i=1;i*i<=n;i++){
//     if(n%i == 0){
//       ret.pb(i);
//       if(i*i!=n) ret.pb(n/i);
//     }
//   }
//   vsort(ret);
//   return ret;
// }
//
// ll get_digits_num(ll n){
//   ll ret=0;
//   while(n){
//     n/=10;
//     ret++;
//   }
//   return ret;
// }


ll f(ll n){
  ll rtn;
  ll m = n%8;

  rtn = 0;
  for(ll i=n-m;i<=n;i++){
    rtn = rtn^i;
  }

  return rtn;
}


int main() {
  cout<<fixed<<setprecision(10);

  ll A,B;cin>>A>>B;

  ll rtn;
  if(A==0) rtn=f(B);
  else rtn=(f(A-1)^f(B));

  cout << rtn << endl;;







}




//


Measured memory_bytes: 256
#include <iostream>
#include <map>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<string, int> cnt;
    while (n--) {
        string res;
        cin >> res;
        cnt[res]++;
    }
    cout << "AC x " << cnt["AC"] << endl;
    cout << "WA x " << cnt["WA"] << endl;
    cout << "TLE x " << cnt["TLE"] << endl;
    cout << "RE x " << cnt["RE"] << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300005,M=100005;
int n,m;
struct Node
{
    int l,r,len;
}a[N];
bool cmp(Node x,Node y)
{
    return x.len<y.len;
}
struct Binary_Indexed_Tree
{
    int tree[M];
    Binary_Indexed_Tree()
    {
        memset(tree,0,sizeof(tree));
        return;
    }
    int lowbit(int x)
    {
        return x&-x;
    }
    void add(int x,int y)
    {
        if(x==0) return;
        for(int i=x;i<=m;i+=lowbit(i))
            tree[i]+=y;
        return;
    }
    void add(int a,int b,int val)
    {
        if(a>b) return;
        add(a,val);
        add(b+1,-val);
        return;
    }
    int getsum(int x)
    {
        int res=0;
        for(int i=x;i>0;i-=lowbit(i))
            res+=tree[i];
        return res;
    }
}T;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,l,r;i<=n;++i)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].len=a[i].r-a[i].l+1;
    }
    sort(a+1,a+n+1,cmp);
    int j=1;
    for(int i=1;i<=m;i++)
    {
        while(j<=n&&a[j].len<i)
        {
            T.add(a[j].l,a[j].r,1);
            j++;
        }
        int ans=n-j+1;
        for(int k=i;k<=m;k+=i)
            ans+=T.getsum(k);
        printf("%d\n",ans);
    }
    return 0;
}


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

#define ll long long

int main()
{
    ll n,sum=0;
    cin>>n;
    ll a[n+5];
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    cout<<(sum-n)<<endl;
}


Measured memory_bytes: 256
N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y


ans = T[0]
for i in range(1, N):
    ans *= T[i] // gcd(ans, T[i])

print(ans)


Measured memory_bytes: 3060
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=1e5+10;
const int maxm=1e2+10;
const int mod=1e9+7;
int n,m;
int c[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            c[a]++;
            c[b]++;
        }
        int flag=1;
        for(int i=1;i<=n;i++)
        {
            if(c[i]%2==1)
                flag=0;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#define lli long long int
#define N 4
#define pb push_back
#define p 1000000007
using namespace std;


int main()
{
    string str;
    int ct = 0;
    cin>>str;
    int n = (int)str.length();
    for(int i=0;i<n/2;i++)
    {
        if(str[i]== str[n-i-1])
            continue;
        ct = ct +  1;
    }
    cout<<ct<<endl;
}


Measured memory_bytes: 3632
/**
** author: Haunted_Cpp
**/
/***************** [LIBRARY PROTOCOL] ****************/
#include<bits/stdc++.h>
using namespace std;
/********************* [CONSTANTS] *******************/
#define INF 1e9
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MOD 1000000007
typedef long ld;
typedef long long lld;
typedef pair<int,int>ii;
vector<int>dr={+1,-1,+0,+0,+1,-1,-1,+1};
vector<int>dc={+0,+0,+1,-1,+1,-1,+1,-1};
/******************** [FUNCTIONS] ********************/
/*********************** [MAIN] **********************/
int main(){
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int r,c;cin>>r>>c;
  vector<string>grid(r);for(int i=0;i<r;i++)cin>>grid[i];
  vector<vector<int>>dp(r,vector<int>(c));
  for(int i=0;i<r;i++){
    if(grid[i][0]=='#')break;
    dp[i][0]=1;
  }
  for(int i=0;i<c;i++){
    if(grid[0][i]=='#')break;
    dp[0][i]=1;
  }
  for(int i=1;i<r;i++){
    for(int j=1;j<c;j++){
      if(grid[i][j]=='#')continue;
      dp[i][j]=((dp[i-1][j]%MOD)+(dp[i][j-1]%MOD))%MOD;
    }
  }
  cout<<dp[r-1][c-1]%MOD<<'\n';
  return 0;
}

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

int main() {
	long long n,a;cin>>n>>a;
	vector<long long> x(n);
	for(int i=0;i<n;i++){
		cin>>x[i];
		x[i]-=a;
	}
	vector<long long> v(50*51,0);
	vector<long long> v2(50*51,0);
	int def=50*26;
	v2[def]++;
	v2[def+x[0]]++;
	v=v2;

	for(int i=1;i<n;i++){
		for(int j=0;j<50*51;j++){
			v2[j+x[i]]+=v[j];
		}
		v=v2;
	}
	cout<<v[def]-1<<endl;
//	for(int i=def-30;i<def+30;i++){
//		cout<<v[i]<<endl;
//	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll h,w; cin >> h >> w;
    ll a,b; cin >> a >> b;
    string res[h];
    string ones(a, '1'), zeros(w-a, '0');
    // debug(ones);
    rep(i,b)res[i] = ones + zeros;
    string ones_2(w-a, '1'), zeros_2(a, '0');
    for(int i = b; i < h; i++)res[i] = zeros_2 + ones_2;
    rep(i,h)cout << res[i] << "\n";
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 201000
#define LL long long

int n, m;
LL ans;
LL s[AC], k[AC], d[AC];

inline int read()
{
	int x = 0;char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

inline int cal(int l, int r)
{	
	if(l == r) return 0;
	if(l < r) return r - l;
	else return r + m - l;
}

inline void pre()
{
	n = read(), m = read();
	for(R i = 1; i <= n; i ++) 
	{
		s[i] = read();
		if(i > 1) ans += cal(s[i - 1], s[i]);//先计算出没有特殊按钮的代价
	}
}

inline void add(int l, int r)
{
	//printf("%d %d\n", l, r);
	if(l > r) return ;
	++ k[l], -- k[r + 1], d[r + 1] -= r - l + 1;//是要在后面减掉前面累积的
}

inline void upmax(LL &a, LL b)
{
	if(b > a) a = b;
}

void work()
{
	for(R i = 1; i < n; i ++)
	{
		if(s[i] == s[i + 1]) continue;
		if(s[i] < s[i + 1]) add(s[i] + 2, s[i + 1]);
		else add(s[i] + 2, s[i + 1] + m);
	}
	int b = 2 * m; LL maxn = 0;
	for(R i = 1; i <= b; i ++) k[i] += k[i - 1];
	for(R i = 1; i <= b; i ++) k[i] += k[i - 1] + d[i];
	for(R i = 1; i <= m; i ++) k[i] += k[i + m], upmax(maxn, k[i]);
	printf("%lld\n", ans - maxn);
}

int main()
{
	//freopen("in.in", "r", stdin);
	pre();
	work();
	//fclose(stdin);
	return 0;
}

Measured memory_bytes: 3584
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); //入出力高速化
	while (true) {
	int H,W; cin >> W >> H;
	if (H == 0 && W == 0) break;
	vector<vector<int>> wallh(H, vector<int>(W-1)), wallw(H-1, vector<int>(W));
	rep(i,2*H-1) {
		if (i % 2 == 0) {
			rep(j,W-1) cin >> wallh[i/2][j];
		} else {
			rep(j,W) cin >> wallw[i/2][j];
		}
	}

	vector<vector<int>> d(H, vector<int>(W,INF));
	d[0][0] = 1;
	queue<pair<int, int>> que;
	que.emplace(make_pair(0,0));
    while (!que.empty()) {
        int y,x;
	    tie(y,x) = que.front(); que.pop();
	    if (x < W-1) {  
	        if (wallh[y][x] == 0 && d[y][x+1] == INF) {
			    que.emplace(make_pair(y,x+1));
			    d[y][x+1] = d[y][x] + 1;
		    } 
	    }
		if (x > 0) {  
	        if (wallh[y][x-1] == 0 && d[y][x-1] == INF) {
			    que.emplace(make_pair(y,x-1));
			    d[y][x-1] = d[y][x] + 1;
		    } 
	    }
		if (y < H-1) {  
	        if (wallw[y][x] == 0 && d[y+1][x] == INF) {
			    que.emplace(make_pair(y+1,x));
			    d[y+1][x] = d[y][x] + 1;
		    } 
	    }
		if (y > 0) {  
	        if (wallw[y-1][x] == 0 && d[y-1][x] == INF) {
			    que.emplace(make_pair(y-1,x));
			    d[y-1][x] = d[y][x] + 1;
		    } 
	    }
	}

	if (d[H-1][W-1] == INF) cout << 0 << endl;
	else cout << d[H-1][W-1] << endl;
	}
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define int long long




signed main(){
    int n;
    cin>>n;
    int h[n],maxh=0,ans=0;
    for(int i=0;i<n;i++){
        cin>>h[i];
        if(maxh<=h[i])ans++;
        maxh=max(maxh,h[i]);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int N;
int K;
int L;

vector<long> count;
vector<vector<int> > road;
vector<vector<int> > rail;

vector<int> idList;
int id = 0;

vector<bool> usedRoad;
vector<bool> usedRail;

map<int, int> tmap;
vector<int> list;

void findRoad(int p) {
  usedRoad[p] = true;
  idList[p] = id;
  vector<int> list2 = road[p];
  for (int i = 0; i < list2.size(); ++i) {
    int q = list2[i];
    if (!usedRoad[q]) {
      findRoad(q);
    }
  }
}
void findRail(int r) {
  usedRail[r] = true;
  list.push_back(r);
  int key = idList[r];
  ++tmap[key];
  vector<int> list2 = rail[r];
  for (int i = 0; i < list2.size(); ++i) {
    int s = list2[i];
    if (!usedRail[s]) {
      findRail(s);
    }
  }
}
void solve() {
  cin >> N >> K >> L;

  usedRoad.resize(N);
  usedRail.resize(N);
  idList.resize(N);
  road.resize(N);
  rail.resize(N);

  for (int i = 0; i < K; ++i) {
    int p;
    int q;
    cin >> p >> q;

    road[p - 1].push_back(q - 1);
    road[q - 1].push_back(p - 1);
  }

  for (int i = 0; i < L; ++i) {
    int r;
    int s;

    cin >> r >> s;

    rail[r - 1].push_back(s - 1);
    rail[s - 1].push_back(r - 1);
  }

  for (int i = 0; i < N; ++i) {
    if (!usedRoad[i]) {
      findRoad(i);
      ++id;
    }
  }

  count.resize(N);

  for (int i = 0; i < N; ++i) {
    if (!usedRail[i]) {
      tmap.clear();
      list.clear();
      findRail(i);
      for (int j = 0; j < list.size(); ++j) {
        int k = list[j];
        count[k] += tmap.at(idList[k]);
      }
    }
  }

  cout << count[0];
  for (int i = 1; i < N; ++i) {
    cout << ' ' << count[i];
  }
  cout << endl;
}
int main(int argc, char* argv[]) {
  solve();
  return 0;
}

Measured memory_bytes: 20600
N=int(input())
H=list(map(int,input().split()))
H.insert(0,0)
H.append(0)
#print(H)
count=1
total=0
rem=N
for i in range(1000):
    for j in range(1,N+1):
        if H[j]==i:
            rem -= 1
            H[j]=0
            if H[j-1]!=0 and H[j+1]!=0:
                count+=1
            if H[j-1]==0 and H[j+1]==0:
                count -=1
    if rem==0:
        break
    total += count
    #print("rem:"+str(rem))
    #print("count"+str(count))
    #print(total)


print(total)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    char agct[4] = {'A', 'C', 'G', 'T'};
    string S;
    cin >> S;
    int ans = 0;
    int tmp_ans = 0;
    for (int i = 0; i < S.size(); i++)
    {
        if ([&]() {
                for (int j = 0; j < 4; j++)
                {
                    if (S[i] == agct[j])
                        return true;
                }
                return false;
            }())
        {
            tmp_ans++;
        }
        else
        {
            ans = max(ans, tmp_ans);
            tmp_ans = 0;
        }
    }
    ans = max(ans, tmp_ans);
    printf("%d\n", ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int m = 1046527;

char M[m][15];

int h1(int key) { return key % m; }
int h2(int key) { return 1 + key % (m - 1); }
int h(int key, int i) { return (h1(key) + i * h2(key)) % m; }

long long getKey(char s1[])
{
	long long key = 0;
	int p = 1;
	for(int i = 0; i < strlen(s1); i++){
		if(s1[i] == 'A') key += 1 * p;
		else if(s1[i] == 'C') key += 2 * p;
		else if(s1[i] == 'G') key += 3 * p;
		else if(s1[i] == 'T') key += 4 * p;
		p *= 5;
	}
	return key;
}

void insert(char s1[]){
	int i = 0;
	while(true){
		if(!strlen(M[h(getKey(s1), i)])){
			strcpy(M[h(getKey(s1), i)], s1);
			break;
		}
		i++;
	}
}

void find(char s1[]){
	int i = 0, flag = 0;
	while(i < m && strlen(M[h(getKey(s1), i)])){
		if(!strcmp(M[h(getKey(s1), i)], s1)){
			flag = 1;
			break;
		}
		i++;
	}
	if(flag)
		printf("yes\n");
	else
		printf("no\n");
}

int main(){
	int n;
	char s1[10], s2[15];
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s1 >> s2;
		if(s1[0] == 'i')
			insert(s2);
		else
			find(s2);
	}
	return 0;
}

Measured memory_bytes: 18316
#include <stdio.h>

int main(void) {

	int w, n;
	int a[30], b[30],c[30];
	int i=0,j;
	int nextSearch;

	do {
		scanf("%d",&w);
	} while (w > 30);

	do {
		scanf("%d", &n);
	} while (n > 30);

	while (i < n) {
		scanf("%d,%d",&a[i],&b[i]);
		if ((1 <= a[i]) && (a[i] <= w) && (1 <= b[i]) && (b[i] <= w)) {
			i++;
		}
	}

	for (i = 0; i < w; i++) {
		nextSearch = i + 1;
		for (j = 0; j < n; j++) {
			if (a[j] == nextSearch){
				nextSearch = b[j];
			}
			else if (b[j] == nextSearch) {
				nextSearch = a[j];
			}
		}
		c[nextSearch - 1] = i + 1;
	}

	for (i = 0; i < w; i++) {
		printf("%d\n",c[i]);
	}

	return 0;
}

Measured memory_bytes: 596
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		double Dp1 = 0;
		double Dp2 = 0;
		double Dp3 = 0;
		double Dp2u = 0;
		double Dp3u = 0;
		double Dpmax = 0;
		for(int i=0; i<n; i++){
			x[i] = sc.nextInt();
		}
		for(int i=0; i<n; i++){
			y[i] = sc.nextInt();
		}
		for(int i=0; i<n; i++){
			Dp1 += Math.abs(x[i]-y[i]);
			Dp2u += Math.pow(x[i]-y[i], 2);
			Dp3u += Math.pow(Math.abs(x[i]-y[i]), 3);
			Dpmax = Math.max(Dpmax, Math.abs(x[i]-y[i]));
		}
		Dp2 = Math.sqrt(Dp2u);
		Dp3 = Math.pow(Dp3u, 1.0/3.0);
		
		System.out.println(Dp1);
		System.out.println(Dp2);
		System.out.println(Dp3);
		System.out.println(Dpmax);
	}
}

Measured memory_bytes: 26480
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

const ld pi = 3.141592653589793;

ll n, e, w, l, r, m = 300005;
string s;

int main() {
  cin >> n;
  cin >> s;

  for (int i = 0; i < n; i++) {
    if (s[i] == 'E') {
      e++;
    } else {
      w++;
    }
  }

  l = 0;
  r = w;

  if (s[0] == 'W') {
    r--;
  }
  m = min(m, (n - 1 - r));

  for (int i = 1; i < n; i++) {
    if (s[i - 1] == 'E') {
      l++;
    }
    if (s[i] == 'W') {
      r--;
    }
    m = min(m, (n - 1 - l - r));
  }

  cout << m << endl;
}

Measured memory_bytes: 3844
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}

	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑


int main() {
	long long n, ans = 100000;
	cin >> n;
	while (n--) { ans = (ans + ans / 20 + 999) / 1000 * 1000; }
	cout << ans << endl;
}


Measured memory_bytes: 3060
#include <stdio.h>
#include <vector>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
using vi = vector<int>;

string str;
string stra;
int id = 0;

void pt(vector<int> v){
  for(int r=0;r<v.size();r++){
    cout << v[r];
  }
  cout << endl;
}

vi number(){
  vi res;
  for (;'0'<=stra[id]&&stra[id]<='9'; id++) {
    res.push_back(stra[id] - '0');
  }
  reverse(res.begin(),res.end());
  return res;
}
int solve(){
  stra = str;
  for (int i = 9; i >= 0; i--) {
    id = 0;
    for (int j = 0; j <(int)str.size(); j++) {
      if (str[j] == 'X') {
        stra[j] = i + '0';
      }
    }
    vi a = number();
    if (stra[id] == '+' ) {
      id++;
    }
    vi b = number();

    a.resize(max(b.size() + 1,a.size()+1),0);

    for (int j = 0; j < (int)b.size(); j++) {
      a[j] += b[j];
      if (a[j]>=10) {
        a[j] -= 10;
        a[j+1]++;
      }
    }
    for (int j = b.size(); j < (int)(a.size()-1); j++) {
      if (a[j] >= 10) {
        a[j] -= 10;
        a[j+1]++;
      }
    }
    // for(int j=0;j<(int)a.size()-1;j++){
    //   if(a[j]>=10){
    //     a[j]-=10;
    //     a[j+1]++;
    //   }
    // }

    if(a[a.size()-1]==0){
      a.pop_back();
    }

    //pt(a);
    // int j;
    // int k=0;
    // int l=0;
    // vi ab;
    // for(j=0;j<int(a.size())&&j<int(b.size());j++){
    //   k=0;
    //   if(a[j]+b[j]+l>=10){
    //     k++;
    //     ab.push_back(a[j]+b[j]+l-10);
    //   }
    //   else{
    //     ab.push_back(a[j]+b[j]+l);
    //   }
    //   l=k;
    // }
    // for(;j<int(a.size());j++){
    //   k=0;
    //   if(a[j]+l>=10){
    //     k++;
    //     ab.push_back(a[j]+l-10);
    //   }
    //   else{
    //     ab.push_back(a[j]+l);
    //   }
    //   l=k;
    // }
    // for(;j<int(b.size());j++){
    //   k=0;
    //   if(b[j]+l>=10){
    //     k++;
    //     ab.push_back(b[j]+l-10);
    //   }
    //   else{
    //     ab.push_back(b[j]+l);
    //   }
    //   l=k;
    // }
    // if(l>0){
    //   ab.push_back(l);
    // }
    // a=ab;
    /////////
    if (stra[id] == '=') {
      id++;
    }

    vi c = number();
    if (a.size() != c.size()) {
      continue;
    }
    int flag = 0;
    for (int j = 0; j < (int)a.size(); j++) {
      if (a[j] == c[j]) {
        flag++;
      }
    }
    if (flag ==(int)a.size()) {
      return i;
    }

  }
  return -1;
}
int main(){
  cin >> str;
  while(str.size()){
  int ans = solve();
  if (ans >= 0) {
    cout << ans << endl;
  } else {
    cout << "NA" << endl;
  }
  str="";
  cin >> str;
}
  return 0;
}



Measured memory_bytes: 2992
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <vector>
#include <climits>
#include <queue>
#include <utility>
#include <iomanip>
#include <sstream> 
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
template<typename T1, typename T2>
inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
const ll MOD = 1000000006;
const ll INF = 1LL << 60;

vector<ll> a;

int main()
{
    ll n;
    cin >> n;
    ll buffer;
    rep(i, n) {
        cin >> buffer;
        a.push_back(buffer);
    }

    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());

    /*rep(i, n) {
        cout << a[i] << " ";
    }
    cout << endl;*/

    ll ans = a[0];
    for (ll i = 1; i < n-1; i++) {
        ans += a[((i-1)/2)+1];
        //cout << a[((i - 1) / 2) + 1] << " ";
    }

    cout << ans;


}

/*vector<ll> a;
vector<ll> b;
vector<pair<ll, ll>> c;

int main()
{
    ll n, k;
    cin >> n >> k;

    ll buffer;
    rep(i, n) {
        cin >> buffer;
        //a.push_back(buffer);
        //b.push_back(abs(buffer));
        c.push_back(make_pair(abs(buffer), buffer));
    }

    sort(c.begin(), c.end());
    reverse(c.begin(), c.end());

    ll ans = 1;
    bool sign = true;
    rep(i, k - 1) {
        ans *= c[i].second;
        ans = ans % MOD;
        if (ans < 0)
            ans += MOD;

        if (c[i].second < 0)
            sign = !sign;
    }

    bool ok = false;
    for (int i = k - 1; i < n; i++) {
        if ((sign && c[i].second >= 0) || (!sign && c.[i].second <= 0)) {
            ans *= c[i].second;
            ans = ans % MOD;
            if (ans < 0)
                ans += MOD;
            ok = true;
            break;

        }
    }
    
    if (!ok) {
        reverse(c.begin(), c.end());
        rep(i, k - 1) {
            ans *= c[i].second;
            ans = ans % MOD;
            if (ans < 0)
                ans += MOD;

            if (c[i].second < 0)
                sign = !sign;
        }
    }
    
}


*/

Measured memory_bytes: 5316