akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
#define int long long
typedef pair<int,int>P;
typedef pair<int,P>P2;
typedef pair<string,P>PP;
#define F first
#define S second
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

signed main(){
  int n,k;
  cin>>n>>k;
  int a[n];
  r(i,n)cin>>a[i];
  int ans=0;

  for(int i=0;i<=k;i++){

    if( n<i )continue;

    for(int l=0;l<=i;l++){
      
      priority_queue<int,vector<int>,greater<int> >q;
      r(K,l)q.push(a[K]);
      r(K,i-l)q.push(a[n-1-K]);

      int sum=0;
      //r(k,n-i)sum+=a[l+k];

      int x=k-i,t=1e9;

      while(x && !q.empty() && q.top()<0LL){
        t=q.top();
        q.pop();x--;
      }


      while(!q.empty())sum+=q.top(),q.pop();

      //cout<<i<<' '<<l<<' '<<sum<<endl;

      ans=max(ans,sum);

    }

  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    s=SI()
    ans=0
    for i in range(6):
        if s[i]=="1":
            ans+=1
    print(ans)        
    

        
        
        
        
    
if __name__=="__main__":
    main()



Measured memory_bytes: 65644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    int A[9][9];
    int a;
    cin >> a;
    int f= 0;
    REP(i,9){
        REP(j,9){
            if((i+1)*(j+1)==a) f= 1;
        }
    }
    cout << ((f)?"Yes":"No") << endl;
}

Measured memory_bytes: 256
import sys

import string


characters = string.ascii_lowercase


def base_cvt(value, n=2):
    try:
        tmp = int(value)
    except BaseException:
        raise ValueError('Invalid value:', value)

    if n < 2 or n > len(characters):
        raise ValueError('Invalid n:', value)

    result = ''
    tmp = int(value)
    while tmp >= n:
        idx = tmp % n
        result = characters[idx] + result
        tmp = int(tmp / n)
    idx = tmp % n
    result = characters[idx] + result
    return result


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    k = 1  # 桁数
    while True:
        if n <= 26**k:
            break
        n -= 26**k
        k += 1
    ans = base_cvt(n - 1, 26)
    if len(ans) < k:
        ans = 'a' * (k - len(ans)) + ans
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10032
#include<bits/stdc++.h>
using namespace std;
long long n,ans=1,a[1000];
void check(long long x){
	for(int i=2;i<=x;i++)
		while(x%i==0){
			a[i]++;
			x/=i;
		}
}
int main(){
	cin >> n;
	for(int i=2;i<=n;i++)
		check(i);
	for(int i=0;i<1000;i++){
		ans*=a[i]+1;
		ans%=1000000007;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = []
aa = 0
bb = 0
b = []
flag = 0
for i in range(N):
    aa += A[i]
    a.append(aa)
for i in range(M):
    bb += B[i]
    b.append(bb)
MAX = 0
for i in range(N):
    t = a[i]
    if t > K:
        break
    else:
        tt = K-t
        index = bisect_left(b,tt)
        if index == M:
            MAX = max(MAX,i+1+M)
        elif b[index] == tt:
            MAX = max(MAX,i+1+1+index)
        else:
            MAX = max(MAX,i+1+index)
for i in range(M):
    t = b[i]
    if t > K:
        break
    else:
        tt = K-t
        index = bisect_left(a,tt)
        if index == N:
            MAX = max(MAX,i+1+N)
        elif a[index] == tt:
            MAX = max(MAX,i+1+1+index)
        else:
            MAX = max(MAX,i+1+index)


        
print(MAX)

Measured memory_bytes: 50780
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define mp make_pair
ll check (ll n,ll m,ll i,ll j)
{
	if(i>=0 && i<n && j<m && j>=0)
	   return 1;
	else
	 return 0;   
}
int main()
{
	ll t;
	t = 1;
	while(t--)
	{
		ll k,i,j,n,m;
		cin>>n>>m>>k;
		ll arr[n][m];
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++){
			
			char d;
			cin>>d;
			if(d=='.')
			   arr[i][j] = 0;
			else
			   arr[i][j] = 1;   	
		
		}} 
		ll ans = 0;
		for(i=0;i<(1<<n);i++)
		{
			for(j=0;j<(1<<m);j++)
			{
				ll p,q,c=0;
				ll fake[n][m];
				for(p=0;p<n;p++)
				   for(q=0;q<m;q++)
				     fake[p][q] = arr[p][q];
				for(p=0;p<n;p++)
				{
					for(q=0;q<m;q++)
					{
						if((i&(1<<p))==(1<<p))
						  fake[p][q] = 0;
						if((j&(1<<q))==(1<<q))
						  fake[p][q] = 0;  
					}
				}
				for(p=0;p<n;p++)
				   for(q=0;q<m;q++)
				     c+=fake[p][q];
//				cout<<c<<endl;     
				if(c==k)
				   ans++;
			}
		}
		cout<<ans;
	}
	return 0;
} 

Measured memory_bytes: 3592
#include<stdio.h>
#define ll long long 
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
int main(){
  ll a,b;
  scanf("%lld%lld",&a,&b);
  ll c=0,i;
  a=gcd(a,b);
  for(i=2;i*i<=a;i++){
    if(a%i)continue;
    c++;
    while(a%i==0)a/=i;}
  if(a-1)
    c++;
  printf("%lld\n",c+1);
  return 0;}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solve(void)
{
  int N;
  cin>>N;
  int res = 0;
  for (int i = 0; i < N; i++)
  {
    int A,B;
    cin>>A>>B;
    res += B - A + 1;
  }
  cout<<res<<endl;
  
 
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <math.h>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <deque>
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
const int inf=0x3f3f3f3f;
int n,k;
char s[10000];
int a[1000];
int main()
{
    //freopen("/Users/zilongzhang/Desktop//l.txt","r",stdin);
    while(scanf("%d",&n)!=-1)
    {
        double t;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        t=a[1];
        for(int i=2;i<=n;i++)
            t=(t+a[i])/2.0;
        printf("%.5lf\n",t);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,x;cin>>N>>x;
  vector<long long>a(N);
  for(int i=0;i<N;i++)cin>>a[i];
  long long ans=0;
  for(int i=0;i<N-1;i++){
    if(a[i]+a[i+1]<=x)continue;
    ans+=a[i]+a[i+1]-x;
    if(a[i]>=x)a[i+1]=0;
    else a[i+1]-=a[i]+a[i+1]-x;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4024
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();
		
		long ans = 0;
		if (N >= 3 && M >= 3) {
			ans = (long) (N - 2) * (long) (M - 2);
		} else if (N == 1 && M == 1) {
			ans = 1;
		} else if ((N == 1 && M == 2) || (N == 2 && M == 1) || (N == 2) && (M == 2)) {
			ans = 0;
		} else if (N == 1) {
			ans = M - 2;
		} else if (M == 1) {
			ans = N - 2;
		} else if (N == 2) {
			ans = 0;
		} else if (M == 2) {
			ans = 0;
		}
		
		System.out.println(ans);
	}
}

Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		try {

			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			boolean result = false;

			if (a + b == c) {
				result = true;
			}
			else if (b + c == a) {
				result = true;
			}
			else if (c + a == b) {
				result = true;
			}

			if (result) {
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
		}
		finally {
			sc.close();
		}
	}

}


Measured memory_bytes: 9044
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
int main()
{
    ll L, R, d;
    cin >> L >> R >> d;
    ll ans = 0;
    rep(i, R-L+1){
        if((L+i)%d == 0){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3616
#include <iostream>
using namespace std;
int h, n, x;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> h >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		h -= x;
		if (h <= 0)
		{
			cout << "Yes\n";
			return 0;
		}
	}
	cout << "No\n";
	return 0;
}

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

int main() {
  int n,m;
  cin >> n;
  vector<string> s(n);
  for(int i=0; i<n; i++) cin >> s.at(i);
  cin >> m;
  vector<string> t(m);
  for(int i=0; i<m; i++) cin >> t.at(i);

  string a;
  int ans=0;
  int ANS=0;
  for(int i=0; i<n; i++){
    a=s.at(i);
    for(int i=0; i<n; i++){
      if(a==s.at(i)) ans++;
    }
    for(int i=0; i<m; i++){
      if(a==t.at(i)) ans--;
    }
    if(ANS<ans) ANS=ans;
    ans=0;
  }
  cout <<ANS<<endl;
}

Measured memory_bytes: 256
#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;
  ll a[100000], ans, zero;
  ans = 1, zero = 0;

  rep(i, n) {
    cin>>a[i];
    if (a[i] == 0) {
      zero++;
    }
  }
  if (zero > 0){
    ans = 0;
    cout<<ans<<endl;
    return 0;
  }

  rep(i, n){
    if (a[i] <= 1000000000000000000 / ans) {
      ans *= a[i];
    }
    else {
      ans = -1;
      break;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4400
w,h,n=map(int,input().split())
x1,y1,x2,y2=0,0,w,h
for i in range(n):
    x,y,a=map(int,input().split())
    if a==1:
        x1=max(x1,x)
    elif a==2:
        x2=min(x2,x)
    elif a==3:
        y1=max(y1,y)
    else:
        y2=min(y2,y)
print(max(x2-x1,0)*max(y2-y1,0))

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
typedef long long ll;

string s,t;
int main(){
  cin >> s >> t;
  cout << t + s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
typedef unsigned long long ull;
using namespace std;

ull max(ull a, ull b) {
    if (a > b)
        return a;
    return b;
}

int main() {
    int N = 0, W = 0;
    cin >> N >> W;
    ull wi[N][2];
    for (int i = 0; i < N; ++i)
        cin >> wi[i][0] >> wi[i][1];
    ull dp[N+1][W+1];
    for (int i = 0; i < N+1; ++i)
        for (int j = 0; j < W+1; ++j)
            dp[i][j] = 0;
    for (int i = 1; i < N+1; ++i) {
        for (int j = 1; j < W+1; ++j) {
            int nI = j-wi[i-1][0];
            dp[i][j] = max(dp[i-1][j], nI < 0 ? 0 : (dp[i-1][nI]+wi[i-1][1]));
        }
    }
    cout << dp[N][W];
}


Measured memory_bytes: 82548
#include<stdio.h>
int main(void)
{
	int n,k,a,g;
	int cnt=0;
	int list[101]={0};
	scanf("%d %d",&n,&k);
	for(int i=0;i<k;i++) {
		scanf("%d",&a); 
		for(int j=0;j<a;j++) {
			scanf("%d",&g);
			list[g]++;
		}
	}
	for(int i=1;i<=n;i++) {
		if(list[i]==0)
			cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}
			

Measured memory_bytes: 1728
#include <bits/stdc++.h>
//#pragma GCC optimize ("O2,unroll-loops")

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int MAXN=200010, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN], dsu[MAXN];
pll A[MAXN];
int seg[MAXN<<1];
/*
struct CMP{
	bool operator ()(int x, int y){
		return pll(A[x].second*A[y].first, x)<pll(A[y].second*A[x].first, y);
	}
};
set<int, CMP> st;

FUCK C++ 9
FUCK C++ 11
FUCK atcoder
FUCK set
*/
int fuck(int x, int y){
	if (!x || !y) return x^y;
	if (A[x].second*A[y].first<A[y].second*A[x].first) return x;
	return y;
}
void Set(int pos, int val){
	seg[pos+=n]=val;
	for (; pos>1; pos>>=1) seg[pos>>1]=fuck(seg[pos], seg[pos^1]);
}

int getpar(int x){
	if (dsu[x]==x) return x;
	return dsu[x]=getpar(dsu[x]);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	iota(dsu, dsu+MAXN, 0);
	cin>>n;
	for (int i=2; i<=n; i++) cin>>par[i];
	for (int i=1; i<=n; i++){
		cin>>x;
		A[i]={x==0, x==1};
	}
	for (int i=2; i<=n; i++) Set(i, i);
	for (int i=1; i<n; i++){
		int v=seg[1], u=getpar(par[v]);
		assert(v);
		Set(u, 0);
		Set(v, 0);
		ans+=A[u].second*A[v].first;
		A[u].first+=A[v].first;
		A[u].second+=A[v].second;
		if (u>1) Set(u, u);
		dsu[v]=u;
	}
	cout<<ans<<"\n";
	
	return 0;
}


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

int main() {
    int n,x,basyo=0,count = 1;
    cin >> n >> x;
    vector<int> data(n);
    for (int i = 0; i < n; i++){
        cin >> data.at(i);
        basyo += data.at(i);
        if(basyo <= x)count ++;
    }
    cout << count << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
       
using namespace std;
       
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
 
// #define MAX 100010
 
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES
 
// long long binpow(long long a,long long b)
// {
//     if (b == 1) return a;
//     long long res = binpow(a, b/2)%MOD;
//     if (b % 2) return (res*((res*a)%MOD))%MOD;
//     else return (res * res)%MOD;
// }
 
// long long int fact(long long int a)
// {
//     if(a==0||a==1)
//         return 1;
//     long long int ans = 1;
//     for(int i=a;i>=1;i--)
//         ans = (ans * i);
//     return ans;
// }
 
// long long int ivmod(long long int a)
// {
//     return binpow(a,MOD-2);
// }
 
// long long int ncr(long long int a,long long int b)
// {
//     long long int pans=1;
//     for(int i =a;i>max(b,a-b);i--)
//         pans=pans*i;
//     long long int div = fact(min(b,a-b));
//     // cout<<ans<<"            "<<div<<endl;
//     pans = pans/div;
//     return pans;
// }


int dist[101010];
int color[101010];
vector< vector<int> > g(1000000);

void dfs(int vert,int di , int co)
{
    if(di<=dist[vert])
        return;
    dist[vert] = di;
    if(color[vert] == 0)
        color[vert] = co;
    for(int i=0;i<g[vert].size();i++)
    {
        int temp = g[vert][i];
        dfs(temp,di-1,co);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // #ifndef ONLINE_JUDGE
        // freopen("input.txt","r",stdin);
        // freopen("output.txt","w",stdout);
    // #endif
    int n;
    cin>>n; 
    int m;
    cin>>m; 
    for(int i=0;i<n;i++)
    {
        dist[i] = -1;
    }   
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);  
    }
    int q;
    cin>>q;
    int v[q],d[q],c[q];
    for(int i=0;i<q;i++)
    {
        cin>>v[i]>>d[i]>>c[i];
        v[i]--;
    }
    for(int i=q-1;i>=0;i--)
    {
        dfs(v[i],d[i],c[i]);
    }
    for(int i=0;i<n;i++)
        cout<<color[i]<<endl;
    return 0;
}

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

int main(){
    char x;
    set<char> s;
    while(cin >> x) s.insert(x);

    if(s.size() == 4){
        cout << "Yes" << endl;
    }else if(s.size()%2 == 1){
        cout << "No" << endl;
    }else{
        if(s.count('S') && s.count('N'))    cout << "Yes" << endl;
        else if(s.count('W') && s.count('E'))    cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

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

map<long, long> pf(long n) {
  map<long, long> ma;
  for (long i = 2; i * i <= n; i++) {
    while (n % i == 0) ma[i]++, n /= i;
  }
  if (n != 1) ma[n]++;
  return ma;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long N;
  cin >> N;
  vector<long> A(N);
  for (long i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  bool diff1 = 0;
  for (long i = 1; i < N; i++) {
    if (A.at(i) - A.at(i - 1) == 1) diff1 = 1;
  }

  bool B = 1;
  vector<long> cnt(1e6+1);
  for (auto a : A) {
    for (auto [b, c] : pf(a)) {
      if (cnt.at(b)) B = 0;
      cnt.at(b) += c;
    }
  }
  if (B) return cout << "pairwise coprime" << "\n", 0;

  long G = 0;
  for (long i = 0; i < N; i++) {
    G = gcd(G, A.at(i));
  }

  if (G == 1) return cout << "setwise coprime" << "\n", 0;

  cout << "not coprime" << "\n";
}


Measured memory_bytes: 18756
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  string s;
  cin >> s;
  int n=s.size();
  
  if(n==1){
  cout << 1 << endl;
  return 0;
  }
  
  vector<int> ans(n);
  ans[0]=1;
  if(s[0]!=s[1])ans[1]=2;
  else ans[1]=1;
  
  if(n==2){
  cout << ans[1] << endl;
  return 0;
  }
  
  if(s[0]==s[1]||s[1]==s[2])ans[2]=2;
  else ans[2]=3;
  if(n==3){
  cout << ans[2] << endl;
  return 0;
  }
  
  for(int i=3;i<n;i++){
    if(s[i]!=s[i-1]) {
    ans[i]=ans[i-1]+1;
    }
    if(s[i-1]==s[i]) {
    ans[i]=ans[i-3]+2;
    }
  }
      
  cout << ans[n-1] << endl;
  
}


Measured memory_bytes: 1412
#include <stdio.h>

int main() {
  int a[3][10] = {0}, b[3][10] = {0}, c[3][10] = {0}, d[3][10] = {0};
  int bu, f, r, v;
  int n;
  int i, j, k;

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d %d %d %d", &bu, &f, &r, &v);

    switch (bu) {
      case 1 : a[f - 1][r - 1] += v;
               break;
      case 2 : b[f - 1][r - 1] += v;
               break;
      case 3 : c[f - 1][r - 1] += v;
               break;
      case 4 : d[f - 1][r - 1] += v;
               break;
    }
  }

  for (i = 0; i < 4; i++) {
    switch (i) {
      case 0 : for (j = 0; j < 3; j++) {
                for (k = 0; k < 10; k++) {
                  printf(" %d", a[j][k]);
                }
                putchar('\n');
               }
               break;
      case 1 : for (j = 0; j < 3; j++) {
                for (k = 0; k < 10; k++) {
                  printf(" %d", b[j][k]);
                }
                putchar('\n');
               }
               break;
      case 2 : for (j = 0; j < 3; j++) {
                for (k = 0; k < 10; k++) {
                  printf(" %d", c[j][k]);
                }
                putchar('\n');
               }
               break;
      case 3 : for (j = 0; j < 3; j++) {
                for (k = 0; k < 10; k++) {
                  printf(" %d", d[j][k]);
                }
                putchar('\n');
               }
               break;
    }
    if (i != 3)
      printf("####################\n");
  }

  return 0;
}



Measured memory_bytes: 2080
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

    	/*Scanner = テキスト入力を扱うためのクラス
		 *キーボードからの入力を受けつける場合は
		 *System.inを使って下記のように記述
		 */
		Scanner scan = new Scanner(System.in);

		//forループ文用に変数準備
		int i;
		int j;

		/*while文で無限ループ設定
		 * if文でbreakをかける
		 * 求められている通りになったがコードが無駄に多いように思える
		 * 後程修正を行えるか試す
		 */

		while(true){
			int H = scan.nextInt();
			int W = scan.nextInt();
			if(H == 0 && W == 0)break;
			for(j = 0; j < H; j++){
				for(i = 0; i < W; i++){
					System.out.print("#");
				}
			System.out.println();
			}
			System.out.println();
		}
    }
}

Measured memory_bytes: 26820
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<iostream>
#include<cmath>
#include<math.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
const double PI=M_PI;
signed main(){
    ll k;cin>>k;
    string s;cin>>s;
    if(s.size()>k){
        string t=s.substr(0,k)+"...";
        s=t;
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3632
N = int(input())
s = [1]
a = 6
b = 9
while a <= N:
    s.append(a)
    a *= 6

while b<= N:
    s.append(b)
    b *= 9
s.sort()


dp = [-1]*(N+1)
dp[0] = 0


for i in range(1,N+1):
    temp = []
    for j in s:
        if (i-j >= 0):
            if (dp[i-j] != -1):
                temp.append(dp[i-j]+1)
        else:
            break
    dp[i] = min(temp)

print(dp[N])
    

Measured memory_bytes: 3828
#include<stdio.h>
int main()
{
	int h, w, i, j;
	while (1)
	{
		scanf("%d %d", &h, &w);
		if ((h == 0) && (w == 0))
			break;
		for (i = 0; i < h; i++)
		{
			if (i % 2 == 0){
				for (j = 0; j < w; j++)
				{
					if (j % 2 == 0)
						printf("#");
					else
						printf(".");
				}
				printf("\n");
			}
			else{
				if (i % 2 == 1){
					for (j = 0; j < w; j++)
					{
						if (j % 2 == 0)
							printf(".");
						else
							printf("#");
					}
					printf("\n");
				}
			}
		}
		printf("\n");

	}

	return(0);

}

Measured memory_bytes: 572
#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, M;
  cin >> N >> M;

  int ans = 0;

  ans += N * (N-1) / 2;
  ans += M * (M-1) / 2;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int N;
	int asumikana;
	if (scanf("%d", &N) != 1) return 1;
	asumikana = 0;
	while ((1 << (asumikana + 1)) <= N) asumikana++;
	printf("%d\n", 1 << asumikana);
	return 0;
}



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

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

int main()
{
    /*
    int n;
    cin>>n;
    while(n)
    {
        if(n%10==7)
        {
            cout<<"Yes"<<endl;
            return 0;
        }
        n=n/10;
    }
    cout<<"No"<<endl;
    */
    /*
    int n;
    cin>>n;
    ll total = 0;

    for(int i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
            total+=i;
        }
    }
    cout<<total<<endl;
    */
    int k;
    cin>>k;
    ll total = 0;
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=k;j++)
        {
            for(int l=1;l<=k;l++)
            {
                total+=gcd(gcd(i,j),l);
            }
        }
    }
    cout<<total<<endl;
    return 0;
}

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

#define For(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

typedef long long LL;

const int N = 20;

LL Pow[N], ans;

void DFS(int x, LL rem, LL ret, bool first){
	if(x <= 1){
		if(x == 1) ret *= 10 - first;
		if(!rem) ans += ret;
		return;
	}

	LL del = Pow[x - 1] - 1;
	
	int l = first ? 0 : -9, r = 9;

	For(i, l, r){
		LL nxt = rem - del * i;
		if(nxt % 10 || abs(nxt) > Pow[x]) continue;
		DFS(x - 2, nxt / 10, ret * (10 - abs(i) - first), false);
	}
	
}

int main(){
	LL d;
	scanf("%lld", &d);
	
	Pow[0] = 1;
	For(i, 1, 18) Pow[i] = Pow[i - 1] * 10;
	For(i, 1, 18) DFS(i, d, 1, 1);

	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;

int main(){
    double L; cin >> L;
    cout << setprecision(16) << (L/3)*(L/3)*(L/3) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<bool>>;

vector<bool> seen;
void dfs(const Graph& G, long v) {
	seen[v] = true;

	for (long v2 = 0; v2 < G[v].size(); v2++) {
		if (!G[v][v2]) continue;
		if (seen[v2]) continue;
		dfs(G, v2);
	}
}

int main() {
	long n, m; cin >> n >> m;
	vector<long> a(m), b(m);
	Graph G(n, vector<bool>(n, false));
	for (long i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		G[a[i]][b[i]] = G[b[i]][a[i]] = true;
	}

	long ans = 0;

	for (long i = 0; i < m; i++) {
		G[a[i]][b[i]] = G[b[i]][a[i]] = false;
		seen.assign(n, false);
		dfs(G, 0);
		bool bridge = false;
		for (auto item: seen) if (!item) bridge = true;
		if (bridge) ans++;
		G[a[i]][b[i]] = G[b[i]][a[i]] = true;
	}

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


Measured memory_bytes: 3160
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
ll a[100005];
ll x[100005] = {};
ll sum[100005];
int main() {
	int n;
	cin >> n;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ans += a[i];
		x[a[i]]++;
	}
	pair<ll, ll>p;
	int m;
	cin >> m;
	ll count = 0;
	for (int i = 0; i < m; i++) {
		cin >> p.first >> p.second;
		ans -= x[p.second] * p.second;
		x[p.second] += x[p.first];
		ans = ans + (x[p.second] * p.second - x[p.first] * p.first);
		sum[count] = ans;
		x[p.first] = 0;
		count++;
	}
	for (int i = 0; i < m; i++) {
		cout << sum[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 5952
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
ll MOD = 1000000007;
ll INF =1<<30;


int main(){
   string s;
   cin >> s;
   int cnt = 0;
   rep(i,s.size()){
       if(s[i]=='2') cnt++;
   }
   cout << cnt <<endl;
}

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

int main()
{
  ios::sync_with_stdio(0);
  int n, x, cnt[100100] = {0};
  cin >> n;
  while (n--)
  {
    cin >> x;
    cnt[x]++;
  }

  int ans = 0;
  for (int i = 1; i < 100000; i++)
    ans = max(ans, cnt[i - 1] + cnt[i] + cnt[i + 1]);
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
   long long int n,k,a;
    vector<int> health;
    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        cin>>a;
        health.push_back(a);
    }
    sort(health.begin(),health.end());

   long long int sum=0;
    for(int i=0; i<n-k; i++)
    {
        sum+=health[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int K,N;
  cin >> K >> N;
  vector<int> A(N);
  rep(i,N)
  {
    cin >> A[i];
  }
  int M = 0;
  rep(i,N)
  {
    if(i!=N-1)
    {
      M = max(M,A[i+1]-A[i]);
    }
    else
    {
      M = max(M,A[0]+K-A[N-1]);
    }
    
  }
  cout << K-M << endl;
  return 0;
}


Measured memory_bytes: 1152
#include<iostream>
using namespace std;
long long int a[100];
int main()
{
	
	int n;
	cin>>n;
	a[0]=2;
	a[1]=1;
	for(int i=2;i<=n;i++)
	{
		a[i]=a[i-1]+a[i-2];
	}
	cout<<a[n]<<endl; 
} 

Measured memory_bytes: 256
n=int(input())
p=list(map(int,input().split()))
counter=0
for i in range(1,n-1):
  p_ = list((p[i-1],p[i],p[i+1]))
  p_.sort()
  if (p_[1] == p[i]) and (p_[0]<p_[1]):
    counter +=1
print(counter)

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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(X,i) ((X>>i)&1)
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define ina(x,n) rep(x_i,n) cin>>x[x_i]
#define outa(x,n) rep(x_i,n) cerr<<x[x_i]<<" \n"[x_i==n-1]

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;

const int mod = 1e9+7;
const int inf = (1<<28);
const ll infl = (1LL<<60);

int main() {
  int n; cin >> n;
  cout << (n+1)/2 << endl;
  return 0;
}


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

signed main() {
#ifdef LOCAL
  assert(freopen("a.in", "r", stdin));
#endif
  string s;
  cin >> s;
  for (int i = 0; i < int(s.size()) - 1; ++i) {
    if (s.substr(i, 2) == "AC") {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
}

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

using namespace std;

int main() {
    long long int H;
    long long int result = 0;
    cin >> H;
    long long int m = 0;
    while (!(pow(2, m) <= H && H < pow(2, m + 1))){
        m++;
    }
    result = pow(2,m+1) -1;
    cout << result << endl;
}

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

n, p = [int(x) for x in input().split()]
s = input().rstrip()[::-1]
ans = 0
if p == 2:
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += (n - i)
    print(ans)
    sys.exit()
if p == 5:
    for i in range(n):
        if int(s[i]) == 0 or int(s[i]) == 5:
            ans += (n - i)
    print(ans)
    sys.exit()
t = [0, int(s[0]) % p]
mul = 10
for i in range(1, n):
    t.append((t[-1] + int(s[i])*mul) % p)
    mul *= 10
    mul %= p
from collections import Counter
c = Counter(t)
for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2
print(ans)



Measured memory_bytes: 48428
import fractions
import sys
from functools import reduce
import collections
import time
input = sys.stdin.readline


def main():
    n, k = input_list()
    total = 0
    a_map = {}
    for _ in range(n):
        num, count = input_list()
        if num in a_map:
            a_map[num] += count
        else:
            a_map[num] = count
    sa_map = sorted(a_map.items(), key=lambda x: x[0])

    for num, count in sa_map:
        total += count
        if k <= total:
            print(num)
            break
    # 2 3 3 3 4 4 4

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


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

int n;
int t[200];
int u[200];
int dp[(1<<16)];

int calc(int l,int r){
  l=(1<<l)-1;
  r=(1<<r)-1;
  return r-l;
}

void init(){
  for(int i=0;i<200;i++)t[i]=u[i]=0;
  for(int i=0;i<(1<<16);i++)dp[i]=0;
}

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    init();
    
    for(int i=0;i<n;i++){
      int m,l,r;
      cin>>m>>u[i];
      for(int j=0;j<m;j++){
	cin>>l>>r;
	l-=6;r-=6;
	t[i]|=calc(l,r);
      }
    }
    
    for(int i=0;i<n;i++){
      for(int S=0;S<(1<<16);S++){
	if(S&t[i])continue;
	int nS=S|t[i];
	dp[nS]=max(dp[nS],dp[S]+u[i]);
      }
    }
    
    int ans=0;
    for(int i=0;i<(1<<16);i++)
      ans=max(ans,dp[i]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1416
// https://atcoder.jp/contests/abc177/tasks/abc177_e
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)
const int SZ = 1e6;

// エラトステネスの篩
template <int N> struct Prime {
    bitset<N + 1> b;
    Prime() : b() {
        // trueで初期化
        b.flip();
        b[0] = b[1] = false;
        for (int i = 2; i <= N; ++i) {
            if (b[i]) {
                for (int j = i * i; j <= N; j += i) {
                    b[j] = false;
                }
            }
        }
    }
};
// SZ = 1e6 だと10ms
Prime<SZ> prime;

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), D(SZ + 1);
    for (auto &x : A) {
        cin >> x;
        // 同じ数が重複するケースを考慮
        D[x]++;
    }
    // trueなら "pairwise coprime"
    bool pc = true;
    // trueなら "setwise coprime"
    bool sc = true;

    REP(i, SZ) {
        // 素数の場合
        if (prime.b[i]) {
            int cnt = 0;
            for (int now = i; now <= SZ; now += i) {
                cnt += D[now];
            }
            // 任意の2つの整数のgcdがi
            if (cnt >= 2) {
                pc = false;
            }
            // 全ての整数のgcdがi
            if (cnt == N) {
                sc = false;
                break;
            }
        }
    }
    if (pc) {
        cout << "pairwise coprime" << endl;
    } else if (sc) {
        cout << "setwise coprime" << endl;
    } else {
        cout << "not coprime" << endl;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 19008
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
using namespace std;
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

int main(){
    int N; cin >> N;
    vector<int> a(N),b(N);
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < N; i++) cin >> b[i];
    long long ans = 0;
    for(int k = 0; k < 30; k++){
        long long t = 1 << k;
        long long cnt = 0;
        vector<int> c(N),d(N);
        for(int i = 0; i < N; i++){
            c[i] = a[i] % (2*t);
            d[i] = b[i] % (2*t);
        }
        sort(begin(d),end(d));
        for(int i = 0; i < N; i++){
            cnt += lower_bound(begin(d),end(d),2*t - c[i]) - lower_bound(begin(d),end(d),t - c[i]);
            cnt += lower_bound(begin(d),end(d),4*t - c[i]) - lower_bound(begin(d),end(d),3*t - c[i]);
        }
        if (cnt % 2 == 1) ans += t;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3432
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>

#define fst first
#define snd second

using namespace std;

typedef struct {
    int dis;
    int lim;
} edge;
typedef pair<int,int> pp;
typedef pair<int, pp> node; // v, (x,y)
typedef pair<double, node> que; // sum, (v, (x,y))

edge input[50][50];
double G[50][50][50]; // x, y, v

int main(void) {
    while(1) {
        int n,m,s,g;
        scanf("%d%d",&n,&m);
        if(!n) break;
        scanf("%d%d",&s,&g);
        s--, g--;

        memset(input, 0, sizeof(input));
        memset(G, 0, sizeof(G));

        for(int i=0; i<m; i++) {
            int x,y,d,c;
            scanf("%d%d%d%d",&x,&y,&d,&c);
            x--, y--;
            input[x][y] = input[y][x] = {d,c};
        }

        map<node,double> tbl;
        priority_queue<que> q;
        for(int i=0; i<n; i++)
            if(input[s][i].dis)
                q.push(que(-0.0, node(1, pp(s,i))));

        double res = 10000000.0;
        while(q.size()) {
            que t = q.top(); q.pop();

            int v = t.snd.fst;
            int x = t.snd.snd.fst, y = t.snd.snd.snd;

            double sum = -t.fst + 1.0* input[x][y].dis / v;

            if(tbl.find(t.snd) != tbl.end()) continue;
            tbl[t.snd] = sum;

            if(y == g && v == 1) {
                res = res < sum ? res : sum;
                continue;
            }

            for(int i=0; i<n; i++)
                if(i!=x && input[y][i].dis) {
                    int dv[] = {-1,0,1};
                    for(int iv=0; iv<3; iv++)
                        if(0<v+dv[iv] && v+dv[iv]<=input[y][i].lim && tbl.find(node(v+dv[iv], pp(y,i))) == tbl.end())
                            q.push(que(-sum, node(v+dv[iv], pp(y,i))));
                }
        }
        if(res>1000000.0)
            puts("unreachable");
        else
            printf("%f\n", res);


    }
    return 0;
}

Measured memory_bytes: 22836
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
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;}

long long gcd_o(long long y, long long x){
    return x ? gcd(x,y%x) : y;
}

int main(){
    int k;
    cin >> k;
    ll sum = 0;
    REP(i, k+1){
        REP(j, k+1){
            REP(m, k+1){
                sum += gcd_o(i, gcd_o(j, m));
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define Outc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
template <typename T> inline void Out(T x)
{
	if(!x){Outc('0'); return;} if(x < 0) Outc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; Outc(*--_Ot)); if(_O-_Ob >= BUF_SIZE-50) _END;
}
int a[55], n, mx, mn;
int main()
{
	n = read(); mx = mn = 1; for(rint i = 1; i <= n; a[i] = read(), a[i]>a[mx]?mx=i:0, a[i]<a[mn]?mn=i:0, i++);
	if(a[mn] >= 0 || a[mx] <= 0) printf("%d\n",n-1);
	else if(a[mx]+a[mn] >= 0){printf("%d\n",2*n-2); for(rint i = mx>1?1:2; i <= n; printf("%d %d\n",mx,i), a[i] += a[mx], i++, i += i==mx);}
	else {printf("%d\n",2*n-2); for(rint i = mn>1?1:2; i <= n; printf("%d %d\n",mn,i), a[i] += a[mn], i++, i += i==mn);}
	for(rint i = mn = 1; i <= n; a[i]<a[mn]?mn=i:0, i++); 
	if(a[mn] >= 0) for(rint i = 1; i < n; printf("%d %d\n",i,i+1), i++);
	else for(rint i = n; i > 1; printf("%d %d\n",i,i-1), i--); return 0;
}

Measured memory_bytes: 256
// AOJ 1244: Molecular Formula
// 2017.10.12 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int w[1024];

void insert(char *s, int n)
{
	int i;
	i = (s[0]-'A'+1);
	if (s[1]) i |= (s[1]-'a'+1) << 5;
	w[i] = n;
}

int lookup(char *s)
{
	int i;
	i = (s[0]-'A'+1);
	if (s[1]) i |= (s[1]-'a'+1) << 5;
	return w[i];
}

char *molecular();
char *atom(int *n, char *s)
{
	int k;
	char b[3];

	if (*s == '(') {
		s++; if ((s = molecular(n, s)) == NULL) return NULL;
		s++;
		if (isdigit(*s)) {
			k = 0; while (isdigit(*s)) k = 10*k + (*s++ - '0');
			*n *= k;
		}
	} else if (isalpha(*s)) {
		b[0] = *s++, b[1] = 0;
		if (islower(*s)) b[1] = *s++, b[2] = 0;
		if ((k = lookup(b)) == 0) return NULL;
		*n = k;
	}
	return s;
}

char *molecular(int *n, char *s)
{
	int k, m;

	*n = 0, m = 0;
	while (*s >= ' ') {
		if (*s == '(' || isalpha(*s)) {
			if ((s = atom(&m, s)) == NULL) return NULL;
			k = 1;
		} else if (*s == ')') break;
		if (isdigit(*s)) {
			k = 0; while (isdigit(*s)) k = 10*k + (*s++ - '0');
		}
		*n += m*k;
	}
	return s;
}

int main()
{
	int ans;
	char buf[202], *p, *q;

	while (fgets(buf, 200, stdin) && *(buf+2) != 'D') {
		p = buf;
		while (isspace(*p)) p++;
		q = p; while (isalpha(*p)) p++;
		*p++ = 0;
		insert(q, atoi(p));
	}

	while (fgets(buf, 200, stdin) && *buf != '0') {
		p = buf; while (isspace(*p)) p++;
		if (molecular(&ans, p) == NULL) puts("UNKNOWN");
		else printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
 
#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define pfis(a) printf("%d ",a);
#define pfls(a) printf("%lld ",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define f(i,a,b) for(int i=a;i<b;i++)
#define pb(a) push_back(a);
#define mp(a,b) make_pair(a,b)
#define ll long long   

const ll mod=1e9+7;

int main()
{
    ll n,y;
    sfl(n);
    sfl(y);
   // cout<<n<<y<<endl;
    ll p,q,r;
    ll i,j,k,flag=0,sum=0;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
                sum=i*10000 + j*5000;
                if((i+j)>=n)
                {
                    k=(i+j)-n;
                }
                if((i+j)<n)
                {
                    k=n-(i+j);
                }
                sum=sum+k*1000;
                 ll b=i+j+k;
                // cout<<b<<endl;
              //  cout<<sum<<endl;
                if(sum==y&&b==n)
                {
                    flag=1;
                    p=i;
                    q=j;
                    r=k;
                    goto down;
                }
                 sum=0;
           
        }
    }
    down:
    if(flag==1)
    {
        cout<<p<<" "<<q<<" "<<r<<endl;
    }
    else
    {
        cout<<"-1"<<" "<<"-1"<<" "<<"-1"<<endl;
    }
    
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define per(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define INF 2e9
#define LINF 1e18
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, k, q; cin >> n >> k >> q;
    vector<int> a(q);
    rep(i, q) {
        int x;
        cin >> x;
        x--;
        a[i] = x;
    }

    vector<int> ans(n);
    rep(i, q) ans[a[i]]++;

    int lim = q-k;
    vector<bool> which(n, false);
    rep(i, n) {
        if (ans[i] <= lim) {
            which[i] = false;
        }
        else {
            which[i] = true;
        }
    }

    rep(i, n) {
        if (which[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

}

Measured memory_bytes: 1408
w, h, n = map(int, input().split())
w0, h0 = 0, 0
for _ in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        w0 = max(x, w0)
    elif a == 2:
        w = min(x, w)
    elif a == 3:
        h0 = max(y, h0)
    elif a == 4:
        h = min(y, h)
if w <= w0:
    ans = 0
elif h <= h0:
    ans = 0
else:
    ans = abs(w-w0) * abs(h-h0)
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll K;
    cin >>K;

    if(K%2==0){
        cout<<(K*K)/4<<endl;
    }else{
        cout<<(K+1)*(K-1)/4<<endl;
    }
    

    return 0;
    

}

Measured memory_bytes: 3632