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

vector<pair<long long, int>> primeFactorization(long long n) {
    long long k = n;
    vector<pair<long long, int>> ret;
    for (long long i = 2; i*i <= n; i++) {
        pair<long long, int> p = {i, 0};
        while(k % i == 0) {
            p.second += 1;
            k /= i;
        }
        if (p.second != 0) {
            ret.push_back(p);
        }
    }
    if (k > 1) ret.push_back({k, 1});
    return ret;
}

int main(void){
    long long N, P; cin >> N >> P;
    vector<pair<long long, int>> vp = primeFactorization(P);
    long long ans = 1;
    for (auto p : vp) {
        while (N <= p.second) {
            ans *= p.first;
            p.second -= N;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
dbflag=""

def debug(*args):
	if ""!=dbflag: print(*args)

if ""!=dbflag: _INDATA=open(dbflag)

def readline():
	if ""!=dbflag:return _INDATA.readline()
	else: return input()


result = 0


N, H = map(int, readline().split())



#２次元配列
import numpy as np
data=np.ndarray(shape=(N,2),dtype=int)


for i in range(0,N):
	data[i,:]=[int(x) for x in readline().split(' ')]

maxi=np.argmax(data[:,0])
amax=data[maxi,0]

B=data[:,1]
BoverA = sorted((B[B > amax])[:],reverse=True)
lenBoverA=len(BoverA)

curH =H
for i in range(0,lenBoverA):
	curH-=BoverA[i]
	result +=1
	if curH<=0: break


import math

if curH >0:
	result+=math.ceil(curH / amax)

print(result)



Measured memory_bytes: 21868
N = int(input())
S = input()

pos = [[] for i in range(10)]

for i, s in enumerate(S):
    pos[int(s)].append(i)

res = set()

for i in range(10):
    if len(pos[i]) == 0:
        continue
    p = pos[i][0]
    for j in range(10):
        tmp = list(filter(lambda x: x > p, pos[j]))
        if len(tmp) == 0:
            continue
        q = tmp[0]
        for k in range(10):
            tmp = list(filter(lambda x: x > q, pos[k]))
            if len(tmp) == 0:
                continue
            r = tmp[0]

            res.add(str(p) + str(q) + str(r))

print(len(res))


Measured memory_bytes: 4584
#include <stdio.h>
//#define MAX 1000;

//int liner(int,int);

int main(){
  int i=0,j=0;
  int s,t;
  int count=0,key;

  scanf("%d",&s);
  int S[s];
  for(i=0;i<s;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&t);
  int T[t];
  for(i=0;i<t;i++){
    scanf("%d",&T[i]);
  }

    for(i=0;i<t;i++){
      /*if(S[i] == S[i+1]) i++;*/
      key = T[i];
      for(j=0;j<s;j++){
	if(key == S[j]){
	  count++;
	  break;
	}
      }
    }
  
  /*else if( t > s){
    for(i=0;i<s;i++){
      if(T[i] == T[i+1]) i++;
      key = T[i];
      for(j=0;j<s;j++){
	if(S[j] == S[j+1]) j++;
	if(key == S[j]) {
	  count++;
	  break;
	}
      }
    }
  }*/
      printf("%d\n",count);
      return 0;
}


  
		 
  



Measured memory_bytes: 2108
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<n+1;i++)

using namespace std;
using std::swap;

//vector<long long int> p;
vector<long long int> x;
vector<long long int> y;



int main() {

	int n;
	float ave = 1.000000,ans = 0.000000;
	cin >> n;
	x.resize(n);
	y.resize(n);
	rep(i, n)cin >> x[i] >> y[i];
	for (int i = 1; i < n ; ++i)ave *= i;
	for (int i = 0; i < n-1; ++i) {
		for (int j = i + 1; j < n; ++j) {
			ans += sqrt(pow(x[j] - x[i], 2.000000) + pow(y[j] - y[i], 2.0000000))*(ave*2.00000);
			
		}
	}
	cout << fixed<<setprecision(10)<<ans/ave/n << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
int n, b, c;
set<int> s;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> b;
        s.insert(b);
    }
    int s_size=s.size();
    int ans = 0;
    if((n-s_size)%2==0){
        ans=-(n-s_size)/2*2+n;
    }
    else{
        ans=-(n-s_size+1)/2*2+n;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4992
#include<stdio.h>

int main(){
    int k,u,l,n,m,i,j;
    int a[1001][1001];
    int b[1001][1001];
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        scanf("%d", &u);
        a[i][1]=u;
        scanf(" %d", &k);
        a[i][2]=k;
        for(j=3; j<=k+2; j++){
            scanf(" %d", &a[i][j]);
            b[i][a[i][j]] = 1;
        }
    }

    for(l=1; l<=n; l++){
        for(m=1; m<=n; m++){
            printf("%d",b[l][m]);
            if(m != n) printf(" ");
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2504
def solve():
  N, M = map(int, input().split())
  l = [int(i) for i in input().split()]
  l.pop(0)
  s = set(l)
  for i in range(N - 1):
    l = [int(i) for i in input().split()]
    l.pop(0)
    s = s & set(l)
  return len(s)

print(solve())


Measured memory_bytes: 3060
import java.util.*;
import java.io.*;
import java.lang.*;
import static java.lang.System.*;
public class Main{
  public static void main(String[] args) throws Exception {

			  Scanner sc=new Scanner(in);

String a=sc.nextLine();
String b=sc.nextLine();
String ans="";
int n=a.length();
for(int i=0;i<n;i++)
{
	ans+=a.charAt(i);
	if(i!=b.length())
	ans+=b.charAt(i);

}
out.println(ans);

}
}

Measured memory_bytes: 20820
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    cout<<(m-1)*(n-1)<<endl;
    return 0;
}

Measured memory_bytes: 256
m = int(input())
dc = []
for i in range(m):
    dc.append(list(map(int, input().split())))
num = 0
for i in range(m):
    num += (dc[i][0] * dc[i][1])
keta = 0
for i in range(m):
    keta += dc[i][1]
count = 0
count += ((num - 1) // 9)
count += (keta - 1)
print(count)

Measured memory_bytes: 45356
#include<iostream>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll r;

int main(){
    cin>>r;
    cout<<r*r;
    return 0;
}

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

int main(){
    ll n; int m; cin >> n >> m;
    ll sum = 0;
    rep(i,m){
        ll x; cin >> x;
        sum += x;
    }
    if(n >= sum) cout << n-sum << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

double p = 3.141592653589793;

int main(){
  ll A, B, H, M;
  cin >> A >> B >> H >> M;

  double xA = A*cos(((double)H + (double)M / 60.0) / 6.0 * p);
  double yA = A*sin(((double)H + (double)M / 60.0) / 6.0 * p);
  double xB = B*cos((double)M / 30.0 * p);
  double yB = B*sin((double)M / 30.0 * p);

  double dist = sqrt((xA -xB)*(xA - xB) + (yA - yB)*(yA - yB));

  cout << setprecision(15) << fixed << dist << endl;
  
  return 0;
}


Measured memory_bytes: 4164
#include <bits/stdc++.h>
using namespace std ;
const int maxn = 205 ;
int n, m, a[maxn] ;
int main() {
	int i, rec = 0 ;
	scanf ( "%d", &n ) ;
	n <<= 1 ;	
	for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d", a+i ) ;
	sort(a+1, a+n+1) ;
	for ( i = 1 ; i <= n ; i += 2 ) rec += a[i] ;
	printf ( "%d\n", rec ) ;
	return 0 ;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#include<map>
#include<math.h>
#include<string>
#include <cctype>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl
#define INF 1ll<<60;

using namespace std;
using ll = long long;
typedef pair<int, int> P;

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

    int count=0;
    rep(i, s.size()/2){
        if(s[i]!=s[s.size()-i-1]) count++;
    }

    out(count);
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int x[101], n, k, sum;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i];
    }
    for(int i=1;i<=n;i++){
        if(x[i]<=k/2) sum+=x[i]*2;
        else sum+=(k-x[i])*2;
    }
    cout<<sum<<"\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll ans,last,a;
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
       cin>>a;
       ll take=min(last,a);
       ans+=take;
       a-=take;
       ans+=a/2;
       last=a%2;
     }
  cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;} 
int main(void)
{
  int a,b;
    scanf("%d %d",&a,&b);
  if(a>b)
    printf("safe");
  else
    printf("unsafe");
}

Measured memory_bytes: 1712
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())
z, _ = zip(*sorted(enumerate(A), key=itemgetter(1)))
z, _ = zip(*sorted(enumerate(z), key=itemgetter(1)))
cnt = 0
for i in range(N):
    if i % 2 != z[i] % 2:
        cnt += 1
print(cnt // 2)


Measured memory_bytes: 29976
#include<iostream>
#include<cstdio>
using namespace std;
long long n,a,b;
long long x[100010];
void read(long long &x)
{
	char ch;
	ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
}
int main()
{
	read(n);read(a);read(b);
	long long ans=0;
	read(x[1]);
	for(int i=2;i<=n;i++)
	{
		read(x[i]);
		if((x[i]-x[i-1])*a>b) ans+=b;
		else ans+=(x[i]-x[i-1])*a;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int W = sc.nextInt();
			
			int[] ws = new int[N];
			long[] vs = new long[N];
			
			for(int i = 0; i < N; i++) {
				ws[i] = sc.nextInt();
				vs[i] = sc.nextLong();
			}
			
			long[] DP = new long[W + 1];
			Arrays.fill(DP, -1);
			DP[0] = 0;
			
			for(int item = 0; item < N; item++) {
				
				for(int curr = W - ws[item]; curr >= 0; curr--) {
					if(DP[curr] < 0) { continue; }
					
					DP[curr + ws[item]] = Math.max(DP[curr + ws[item]], DP[curr] + vs[item]);
				}
			}
			
			System.out.println(Arrays.stream(DP).max().getAsLong());
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

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

using namespace std;

int main()
{
    map<string, int> mp;
    string w, word, mw;
    while (cin >> word) {
        mp[word]++;
        if (mp[word] > mp[mw]) mw = word;
        if (word.size() > w.size()) w = word;
    }
    cout << mw << " " << w << endl;
    return 0;
}

Measured memory_bytes: 3144
H ,W = [int(i) for i in input().split(' ')]
s = []
#print(s)
for i in range(H):
    line = input()
    lis = []
    for str in line:
        lis.append(str)
    s.append(lis)


def drawable(h,w):
    for i in [-1,1]:
        if 0 <= w+i < W:
#            print(h,w+i)
            if s[h][w+i] =='#':
                return True
    for i in [-1,1]:
        if 0 <= h+i < H:
            if s[h+i][w] =='#':
                return True

    return False

flag = True
for i in range(H):
    for j in range(W):
#        print(i,j)
        if s[i][j]=='#' and not(drawable(i,j)):
           flag = False 

if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ans = 0
for i in range(-(-N//2)+1):
	cnt = 0
	for j in range(1, 2*i):
		if (2*i-1) % j == 0:
			cnt += 1

	if cnt == 8:
		ans += 1

print(ans)

Measured memory_bytes: 5148
n = int(input())
s = 0
a = 0
for i in range(1, n+1):
  if i % 3 == 0:
    a = 0
  elif i % 5 == 0:
    a = 0
  elif i % 3 == 0 and i % 5 == 0:
    a = 0
  else:
    s += i
print(s)

Measured memory_bytes: 9168
#include <stdio.h>

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

int main(void) {
	int T[100000];
	int S[50000];
	int R[500];
	int i,j,k,n,q,t;

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

	scanf("%d\n", &q);
	for(i=0;i<q;i++) {
		scanf("%d", &S[i]);
	}
	
	qsort((void*)T, n, sizeof(T[0]), int_sort);
	qsort((void*)S, q, sizeof(S[0]), int_sort);
	
	i=j=k=0;
	while(i<n&&j<q) {
		if(T[i] == S[j]) {
			R[k] = T[i];
			i++;j++;k++;
		} else if(T[i] > S[j]) {
			j++;
		} else if(T[i] < S[j]) {
			i++;
		}
	}
	printf("%d\n", k);
/*	
	for(i=0;i<k;i++) {
		printf("%d", R[i]);
		if(i<k-1) {
			printf(" ");
		} else {
			printf("\n");
		}
	}
*/	
	return 0;
}

Measured memory_bytes: 1424
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#define REP(i,n)for (int i=0;i<(n);i++)
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ll long long
using namespace std;
typedef pair<int,int> P;
bool inc(string a,string b){
	if(a.size()<b.size())swap(a,b);
	return a.substr(0,b.size())==b;
}

int cnt[26];

int main(){
	int k;
	string s;
	set<string> f;
	cin>>s;
	cin>>k;
	REP(i,s.size())cnt[s[i]-'a']++;
	int p=0;
	REP(i,26){
		if(cnt[i]>0){
			vector<string>vv;
			REP(j,s.size()){
				if(s[j]-'a'==i){
					vv.PB(s.substr(j));
				}
			}
			sort(ALL(vv));
			REP(j,vv.size()){
				REP(l,vv[j].size()){
					string ss=vv[j].substr(0,l+1);
					if(f.count(ss))continue;
					p++;
					if(p==k){
						cout<<ss<<endl;
						return 0;
					}
					f.insert(ss);
				}
			}
		}
	}
}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0;i < (int)(n);i++)
#define RREP(i,n) for(int i = (int)n-1;i >= 0;i--)
#define FOR(i,s,n) for(int i = s;i < (int)n;i++)
#define RFOR(i,s,n) for(int i = (int)n-1;i >= s;i--)
#define ALL(a) a.begin(),a.end()
#define IN(a, x, b) (a<=x && x<b)
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;}
template<class T>istream&operator >>(istream&is,vector<T>&vec){for(T&x:vec)is>>x;return is;}
template<class T>inline void OUT(T t){cout<<t<<"\n";}
template<class T,class... Ts>inline void OUT(T t,Ts... ts){cout<<t<<" ";OUT(ts...);}
template<typename T=int>vector<T>mv(size_t a){return vector<T>(a);}
template<typename T=int,typename... Ts>auto mv(size_t a,Ts... ts){return vector<decltype(mv<T>(ts...))>(a,mv<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type FILL(T&t,const V&v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type FILL(T&t,const V&v){for(auto &e:t)FILL(e,v);}
constexpr long long INF = 1e18;

template <typename T>
struct SegmentTree{
	using F = function<T(T,T)>;
	int n;
	F f;
	T ti;
	vector<T> dat;
	SegmentTree(){};
	SegmentTree(F f,T ti):f(f),ti(ti){}
	void init(int n_){
		n=1;
		while(n<n_) n<<=1;
		dat.assign(n<<1,ti);
	}
	void build(const vector<T> &v){
		int n_=v.size();
		init(n_);
		for(int i=0;i<n_;i++) dat[n+i]=v[i];
		for(int i=n-1;i;i--)
			dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
	}
	void set_val(int k,T x){
		dat[k+=n]=x;
		while(k>>=1)
			dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
	}
	T query(int a,int b){
		T vl=ti,vr=ti;
		for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
			if(l&1) vl=f(vl,dat[l++]);
			if(r&1) vr=f(dat[--r],vr);
		}
		return f(vl,vr);
	}
};

signed main(){
	int N;
	cin>>N;
	auto a = mv(N);
	cin>>a;
	auto f =[&](int x)->bool{
		auto b = mv(N);
		auto s = mv(N+1);
		REP(i,N)b[i] = a[i] >= x ? 1 : -1;
		REP(i,N)s[i+1] = s[i] + b[i];
		auto p = mv<pair<int,int>>(N+1);
		REP(i,N+1)p[i] = {s[i],i};
		sort(ALL(p));
		auto seg = SegmentTree<int>([](int a,int b){return a+b;},0);
		seg.build(vector<int>(N+1,0));
		int ret = 0;
		REP(i,N+1){
			ret += seg.query(0,p[i].second);
			seg.set_val(p[i].second,1);
		}
		return ret >= (N*(N+1)/2+1)/2;
	};
	int l = -1, r = 1e18 + 1;
	while(r - l > 1){
		int c = (l + r) / 2;
		if(f(c)) l = c;
		else r = c;
	}
	cout << l << endl;
}

Measured memory_bytes: 7072
#include <iostream>
#include <vector>

int main() {
  int n;

  constexpr int check[] = {5, 7, 5, 7, 7};

LOOP:
  while (std::cin >> n, n != 0) {
    std::vector<std::string> v(n);

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


    for (int i = 0; i < n; ++i) {
      int cnt = 0, idx = 0;
      for (int j = i; j < n; ++j) {
        cnt += v[j].size();
        if (cnt == check[idx]) {
          cnt = 0;
          idx++;
        }
        if (idx == 5) {
          std::cout << i + 1 << std::endl;
          goto LOOP;
        }
      }
    }
  }
}



Measured memory_bytes: 3244
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader is = new InputStreamReader(System.in);
		char[] buf = new char[21];
		while (is.read(buf) != -1) {
		}
		for (int i = buf.length - 1; i >= 0; i--) {
			if (buf[i] > '\u002F')
				System.out.print(buf[i]);
		}
		System.out.print("\n");
	}
}

Measured memory_bytes: 16848
#include<stdio.h>
#include<stdlib.h>
int min(int a,int b)
{
  if(a<b)
    return a;
  else
    return b;
}
int main()
{
int n;
  scanf("%d",&n);
  int a[n],i;
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  int sum=0,temp=0;
  int count[n];
  count[0]=0;
  count[1]=abs(a[0]-a[1]);
  for(i=2;i<n;i++)
  {
    count[i]=min(abs(a[i]-a[i-1])+count[i-1],abs(a[i]-a[i-2])+count[i-2]);
  }
  printf("%d",count[n-1]);
}

       


Measured memory_bytes: 896
import bisect
import sys

a, b, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
sss = list(map(int, lines[:a]))
ttt = list(map(int, lines[a:a + b]))
xxx = list(map(int, lines[a + b:]))

nearest_temples = [0] * a
nearest_shrines = [0] * b
for i, s in enumerate(sss):
    ti = bisect.bisect(ttt, s)
    nt = 10 ** 11
    if ti > 0:
        nt = min(nt, abs(s - ttt[ti - 1]))
    if ti < b:
        nt = min(nt, abs(s - ttt[ti]))
    nearest_temples[i] = nt
for i, t in enumerate(ttt):
    si = bisect.bisect(sss, t)
    ns = 10 ** 11
    if si > 0:
        ns = min(ns, abs(t - sss[si - 1]))
    if si < a:
        ns = min(ns, abs(t - sss[si]))
    nearest_shrines[i] = ns

buf = []
for x in xxx:
    si = bisect.bisect(sss, x)
    ti = bisect.bisect(ttt, x)
    ans = 10 ** 11
    if si > 0:
        ans = min(ans, x - sss[si - 1] + nearest_temples[si - 1])
    if si < a:
        ans = min(ans, sss[si] - x + nearest_temples[si])
    if ti > 0:
        ans = min(ans, x - ttt[ti - 1] + nearest_shrines[ti - 1])
    if ti < b:
        ans = min(ans, ttt[ti] - x + nearest_shrines[ti])
    buf.append(ans)
print('\n'.join(map(str, buf)))


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

long gcd(long n, long m) {
	if (n == 0)return m;
	if (n < m)swap(n, m);
	return gcd(n % m, m);
}

int main() {
	int a, b; cin >> a >> b;
	cout << (a - 1) * (b - 1);
}

Measured memory_bytes: 256
fn main() {
    let (mut n, m): (usize, usize) = (read::<usize>(), read::<usize>());
    for _ in 0..m {
        match n.checked_sub(read()) {
            Some(v) => n = v,
            None => {
                println!("{}", -1);
                exit(0);
            }
        }
    }
    println!("{}", n);
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 2168
import sys

# sys.stdin = open('f1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    X = read_int()
    K = read_int()
    r = read_int_list()
    Q = read_int()
    j = 0
    sign = -1
    s = 0
    e = X
    y = 0
    origin = 0
    out = [0] * Q
    for i in range(Q):
        t, a = read_int_list()
        while j < K and r[j] < t:
            d = r[j] - origin
            y += d * sign
            if y < 0:
                s += abs(y)
                if s > e:
                    s = e
                y = 0
            if y + e - s > X:
                diff = (y + e - s) - X
                e -= diff
                if e < s:
                    e = s
            if y > X:
                y = X
            origin = r[j]
            j += 1
            sign *= -1
        d = t - origin
        if a <= s:
            res = y
        elif a <= e:
            res = y + a - s
        else:
            res = y + e - s
        res += d * sign
        if res < 0:
            res = 0
        if res > X:
            res = X
        out[i] = res
    return out


def main():
    res = solve()
    print(*res, sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 14588
#include<stdio.h>

int main() {
    int a, b;
    scanf("%d%d", &a, &b);

    if(a < 10 && a >= 0 && b >= 0 && b <10) {
        printf("%d\n", a * b);
    } else {
        printf("-1\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
char p[1002][1002], cop[1002][1002];
int main() {
	int n;
	cin >> n;
	if (n == 0)cout << 1 << endl;
	else cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[3],ans=0;
	cin>>a[0]>>a[1]>>a[2];
	if(a[0]==a[1]&&a[1]==a[2]){
	    cout<<0<<endl;
	    return 0;
	}
	while(1){
	    sort(a,a+3);
	    a[2]=a[2]-a[0];
	    a[1]=a[1]-a[0];
	    a[0]=0;
	    if((a[0]==0&&a[1]==2&&a[2]==2)||(a[0]==0&&a[1]==0&&a[2]==1)){
	        cout<<ans+1<<endl;
	        return 0;
	    }
	    a[0]+=2;
        ans++;
	}
	return 0;
}

Measured memory_bytes: 256
a,b,ab,x,y = map(int,input().split())
price =0
if(a+b>2*ab):
    price = 2*ab*min(x,y)
    min = min(x,y)
    x -= min
    y -= min
    if(x>=y and a<2*ab):
        price += a*x
    elif(y>x and b<2*ab):
        price += b*y
    else:
        price += 2*ab*max(x,y)
else:
    price += a*x+b*y
print(price)


Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
#include<iomanip>
#include<set>
using namespace std;
#define ll long long
int main(){
int n;
ll ans=0;
cin>>n;

for(int i=1;i<=n;i++){
    if(i%3==0 || i%5==0)
        continue;
    ans+=i;
}
cout<<ans;

}

Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  long long A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  if(A[0]!=0){
    cout<<-1<<endl;
    return 0;
  }
  long long cnt=0;
  for(int i=1;i<N;i++){
    if(A[i]-A[i-1]>1){
      cout<<-1<<endl;
      return 0;
    }
    if(A[i]-A[i-1]==1){
      cnt++;
    }
    else{
      cnt+=A[i];
    }
  }
  cout<<cnt<<endl;

  return 0;
}

  

Measured memory_bytes: 5204
package main

import "fmt"

func main() {
	var h1, m1, h2, m2, k int
	fmt.Scan(&h1, &m1, &h2, &m2, &k)
	ans := (h2*60 + m2) - (h1*60 + m1) - k
	fmt.Println(ans)
}


Measured memory_bytes: 1756
import itertools

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

lst = []
for i in itertools.permutations(range(1, n+1)):
    num = int(''.join(map(str, list(i))))
    lst.append(num)

num_p = int(''.join(map(str, p)))
num_q = int(''.join(map(str, q)))

for i in range(len(lst)):
    if lst[i] == num_p:
        arg_p = i
    if lst[i] == num_q:
        arg_q = i

print(abs(arg_q-arg_p))

Measured memory_bytes: 4728
# 人を頂点と見なしたグラフを作る。有向で、逆向きの場合は正負を反転させて辺を張る
# 頂点からの距離を記録し、一致しない箇所があればNG。
# 全ての辺を通るまで続ける。
# 辺の情報を[{0から行ける頂点},{1から行ける頂点},...]で管理する
# 親には進まないようにしてDFSする

N,M = map(int,input().split())
E = [[] for i in range(N)]
for i in range(M):
  L,R,D = map(int,input().split())
  E[L-1].append([R-1,D])
  E[R-1].append([L-1,-D])
from collections import deque
# 頂点、親、距離
INF = 10 ** 10
dist = [INF] * N
for i in range(N):
  if dist[i] != INF:
    continue
  dist[i] = 0
  q = deque()
  # 頂点、親
  q.append([i,-1])
  while q:
    v,parent = q.popleft()
    for child in E[v]:
      if child[0] == parent:
        continue
      if dist[child[0]] == INF:
        dist[child[0]] = dist[v] + child[1]
        q.append([child[0],v])
      else:
        if dist[child[0]] != dist[v] + child[1]:
          print("No")
          exit(0)
else:
  print("Yes")


Measured memory_bytes: 108192
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


template <typename T>
T amarinasi(T a,T b){
    if(a%b==0)
{
    return a/b;
}
else if(a%b>0)
{
    return a/b+1;
}
else
{
    return a/b-1;
}
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------

int main(){
ll n;
cin>>n;
pair<pair<string,ll>,ll>data[n];
string s;
ll p;
for(ll i=0;i<n;i++){
    cin>>s>>p;
    p*=-1;
    data[i]=make_pair(make_pair(s,p),i+1);
}
sort(data,data+n);
for(ll i=0;i<n;i++){
    cout<<data[i].second<<endl;
}
return 0;
}










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

using namespace std;

int main()
{
  int n;
  cin>>n;
  vector<int>v;
  int answer=0;
  for(int i = 0 ; i< 2*n ;i++){
    int k;
    cin>>k;
    v.push_back(k);
  }
  sort(v.begin(),v.end());
  for(int i = 0 ; i < 2*n ; i+=2){
    answer+=min(v.at(i),v.at(i+1));
  }
  cout<<answer<<endl;
return 0;
}


Measured memory_bytes: 504
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    s = input()

    c = collections.Counter(s)

    ans = 1
    for v in c.values():
        ans *= v + 1
        ans %= MOD
    ans = (ans - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
  long int N;
  cin >> N;
  long int ansx=N;
  long int ansy=1;
  long int tmpx,tmpy;
  long int ans;
  long int i=2;
  while(i*i<=N){
    if(N%i==0){
      tmpx=N/i;
      tmpy=i;
      if((tmpx-1)+(tmpy-1)<(ansx-1)+(ansy-1)){
        ansx=tmpx;
        ansy=tmpy;
      }
    }
    i++;
  }
  cout << (ansx-1)+(ansy-1) << endl;
}

Measured memory_bytes: 256
//-------All power is within you,you can do Anything and Everything.---------//
 
    #include <bits/stdc++.h>
    using namespace std;
  
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ M $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//

    #define pb push_back
    #define MP make_pair
    #define F first
    #define S second
    #define int long long
    #define fo(i,a,b) for(int i=a;i<b;i++)
    #define rfo(i,b,a) for(int i=b;i>=a;i--)
    #define deb(x) cout<<#x<<" "<<x<<endl;
    #define mem( a, val ) memset(a, val, sizeof( a ) )
    #define deci( x ) cout<<fixed<<setprecision( x );
    #define bitcount( x ) __builtin_popcountll( x )
 
    
    typedef vector<int> vi;
    typedef pair<int,int> pi; 
    
    const int MOD =  1000000007 ;
    const int MAX = 2e6 + 7;
    const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
    const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ V $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//  
    
    int i,j,k,t,n,q,l,r,mid;
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ F $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
    
    int pw,x,y;
    int cst[MAX],val[MAX];
    void solve()
    {
        cin>>pw>>n;
        int dp[n+1][pw+1];
        fo(i,0,n)
        {
            cin>>x>>y;
            cst[i+1]=y;
            val[i+1]=x;
        }

        fo(i,0,n+1)
        fo(j,0,pw+1)
        dp[i][j]=MOD*MOD;

        fo(i,0,n+1)
        {
            dp[i][0]=0;
        }

        fo(i,1,n+1)
        {
            fo(j,1,pw+1)
            {
                if(val[i]<=j)
                dp[i][j]=min(dp[i-1][j],dp[i][j-val[i]]+cst[i]);
                else
                dp[i][j]=min(dp[i-1][j],cst[i]);
                // cout<<dp[i][j]<<" ";
            }
            // cout<<endl;
        }

        cout<<dp[n][pw]<<endl;

    }
    
//*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*//
//                          GAME STARTS FROM HERE                            //

    int32_t main() 
      {
        
        // int start,stop=clock();
        // cout<<"time:"<<(stop-start)/double(CLOCKS_PER_SEC)*1000<<endl;
        ios_base::sync_with_stdio(0);
        cin.tie(NULL);
        
        // cin>>t;while(t--)
        solve();
        
      return 0;
      }

Measured memory_bytes: 80512
#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int N = 1e6 + 2;
int dv[N];
signed main(){
    int t = 1; //cin >> t;
    while(t--){
    	int n; cin >> n;
    	vector<int> a(n);
    	for(int i = 0; i < n; i++) 
    		cin >> a[i];
    	int mx = *max_element(a.begin(),a.end());
    	for(int i = 0; i < n; i++)
    	{
    		for(int j = a[i]; j <= mx; j += a[i])
    			dv[j]++;
    	}
    	int ans = 0;
    	for(int i = 0; i < n; i++)
    		if(dv[a[i]] == 1)
    			ans++;
    	cout << ans;
    }    
}

Measured memory_bytes: 12616
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Solve is
   N : Integer;
   A : Integer;
   B : Integer;
   Max : Integer;
   Min : Integer;
begin
   Get (N);
   Get (A);
   Get (B);
   Max := A;
   if B < A then
      Max := B;
   end if;
   if A+B <= N then
      Min := 0;
   else
      Min := A+B-N;
   end if;
   Put (Integer'Image (Max));
   Put (Integer'Image (Min));
end Solve;

Measured memory_bytes: 3612
a = list(input())
b = list(input())
c = list(input())
x = "a"

while True:
    if x == "a":
        if len(a) == 0:
            print("A")
            exit()
        x = a.pop(0)
    if x == "b":
        if len(b) == 0:
            print("B")
            exit()
        x = b.pop(0)
    if x == "c":
        if len(c) == 0:
            print("C")
            exit()
        x = c.pop(0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#define chmin(x, y) x = min(x, y);
using namespace std;

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;

int main(int argc, char const *argv[])
{
    ll h, w;
    cin >> h >> w;
    ll ans = INF;
    ll a, b, c;
    rep(i, 1, h)
    {
        a = w * i;
        b = w * ((h - i) / 2);
        c = w * ((h - i + 1) / 2);
        chmin(ans, max({a, b, c}) - min({a, b, c}));
    }
    rep(i, 1, w)
    {
        a = h * i;
        b = h * ((w - i) / 2);
        c = h * ((w - i + 1) / 2);
        chmin(ans, max({a, b, c}) - min({a, b, c}));
    }
    rep(i, 1, h)
    {
        a = w * i;
        b = (h - i) * (w / 2);
        c = (h - i) * ((w + 1) / 2);
        chmin(ans, max({a, b, c}) - min({a, b, c}));
    }
    rep(i, 1, w)
    {
        a = h * i;
        b = (w - i) * (h / 2);
        c = (w - i) * ((h + 1) / 2);
        chmin(ans, max({a, b, c}) - min({a, b, c}));
    }
    cout << ans << endl;

    return 0;
}


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

#define loop(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < n; ++i)
#define dump(a) cerr << #a << " = " << (a) << "(L:" << __LINE__ << ")" << endl

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

void solve(long long X) {
    if (30 <= X) cout << YES << endl;
    else cout << NO << endl;
}

int main() {
    long long X;
    scanf("%lld", &X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3776
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int MAXN=1005;
const int MOD=1e9+7;

int h,w;
ll k;
char s[MAXN][MAXN];

ll ksm(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) res=res*x%MOD;
        x=x*x%MOD;
        y>>=1ll;
    }
    return res;
}

struct Mat{
    ll a[2][2];
    Mat friend operator * (Mat x,Mat y){
        Mat c; memset(c.a,0,sizeof c.a);
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;
        return c;
    }
};

int wk1(){
	int C=0;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			C+=s[i][j];
	return ksm(C,(k-1)%(MOD-1));
}

int wk(int lr,int ud){
	int C=0;
	for(int i=0;i<h;i++)
		for(int j=0;j<w;j++)
			C+=s[i][j];
	int V=ksm(C,(k-1)%(MOD-1));
	int E0=0;
	if(lr){
		for(int i=0;i<h;i++)
			for(int j=0;j<w-1;j++)
				E0+=(s[i][j]&s[i][j+1]);
	}else{
		for(int i=0;i<h-1;i++)
			for(int j=0;j<w;j++)
				E0+=(s[i][j]&s[i+1][j]);
	}
	Mat S,T;
	memset(S.a,0,sizeof S.a);
	memset(T.a,0,sizeof T.a);
	S.a[0][0]=E0,S.a[0][1]=C;
	T.a[0][0]=lr+ud,T.a[1][0]=E0,T.a[1][1]=C;
	ll t=k-2;
	while(t){
		if(t&1)S=S*T;
		T=T*T;t>>=1;
	}
	return (V-S.a[0][0]+MOD)%MOD;
}

int main(){
	scanf("%d%d%lld",&h,&w,&k);
	for(int i=0;i<h;i++) scanf("%s",s[i]);
	if(k==1) return puts("1"),0;
	for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            s[i][j]=(int)(s[i][j]=='#');
	int lr=0,ud=0;
	for(int i=0;i<w;i++) ud+=(s[0][i]&s[h-1][i]);
	for(int i=0;i<h;i++) lr+=(s[i][0]&s[i][w-1]);
	if(lr&&ud) puts("1");
	else if(!lr&&!ud) printf("%d\n",wk1());
	else printf("%d\n",wk(lr,ud));
}


Measured memory_bytes: 1152
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

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

using namespace std;

vector<bool> check(string str) {
    vector<bool> set('z' - 'a' + 1, false);

    REP(i, str.size()) { set[str[i] - 'a'] = true; }

    return set;
}

int main() {
    string str;
    cin >> str;

    if (str.size() == 26) {
        int fail = -1;
        for (int i = str.size() - 1; i >= 0; i--) {
            if (str[i - 1] > str[i])
                continue;
            else {
                fail = i - 1;
                break;
            }
        }

        if (fail == -1) {
            cout << -1 << endl;
            return 0;
        }

        char chr = str[fail];
        str.erase(str.begin() + fail, str.end());

        auto set = check(str);
        for (int i = 0; i <= chr - 'a'; i++) set[i] = true;

        REP(i, 'z' - 'a' + 1) {
            if (!set[i]) {
                str += i + 'a';
                cout << str << endl;
                return 0;
            }
        }
    } else {
        auto set = check(str);

        REP(i, 'z' - 'a' + 1) {
            if (!set[i]) {
                str += i + 'a';
                cout << str << endl;
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int
main()
{
	for (;;)
	{
		int m, f, r;
		scanf("%d %d %d", &m, &f, &r);

		if (m == -1 && f == -1 & r == -1)
			break;

		if (m == -1 || f == -1)        puts("F");
		else if (m+f >= 80)            puts("A");
		else if (m+f >= 65)            puts("B");
		else if (m+f >= 50)            puts("C");
		else if (m+f >= 30 && r >= 50) puts("C");
		else if (m+f >= 30)            puts("D");
		else                           puts("F");
	}

	return 0;
}

Measured memory_bytes: 1012
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
//#define LOCAL
using namespace std;
typedef long long ll;
multimap<string,ll>m;
typedef multimap<string, ll>::iterator mmi;

int main() {
#ifdef LOCAL
ifstream fin("1.txt");
streambuf*p;
p=cin.rdbuf(fin.rdbuf());
#endif // LOCAL
ll q;
cin>>q;
for(ll i=0;i<q;i++){
    ll a;
    string key;
    cin>>a>>key;
    if(0==a){
        ll x;
        cin>>x;
        pair<string, ll>p1(key, x);
        m.insert(p1);
    }else if(1==a){
        if(m.count(key)){
            pair<mmi, mmi>getm=m.equal_range(key);
            for(mmi it=getm.first;it!=getm.second;it++){
                cout<< it->second<<endl;
            }
        }
       // else cout<<'0'<<endl;
    }else if(2==a){
        m.erase(key);
    }else if(3==a){
        string r;
        cin>>r;
        map<string, ll>::iterator i1, i2;
        i1=m.lower_bound(key);
        i2=m.upper_bound(r);
        for(;i1!=i2;i1++){
            cout<<i1->first<<' '<<i1->second<<endl;
        }
    }
}

#ifdef LOCAL
fin.close();
#endif // LOCAL
}



Measured memory_bytes: 24736
"""

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e

辺の重み <= 連結成分の頂点の重みの総和
となる必要がある

辺を取り除くと、連結成分の重みの総和はちいさくなる
→大きい辺は自身を取り除くことでしか条件達成できない

つまり、現状で連結成分の総和よりも辺の重みが大きいものを貪欲に取り除けばよい
逆に、くっつけると条件を満たすのをくっつけてくのは？
→ 1-1-1で重みが3の時、むり

貪欲を高速化するしかない

まず、辺を昇順ソート

二分探索して、現在の重み以上の辺をremove
残りをunion-findして、連結成分ごとに分割
→ 辺が1つづつ取り除かれる最悪の場合、O(M**2)になる

基本的に小さい辺が残り、大きいほうから消えていく？
(つまり、残ってる辺に単調性は成り立つか)
→全体でみれば成り立たないが、連結成分で見れば成り立っている

→つまり、時刻さえ正しく求められれば部分永続ufで小さいほうからつけていけばいいことになる
→本当か？結局分離に O(N)かかるのでは…

辺を大きいほうから見て行って、現在の連結成分の大きさが条件を満たしているか調べればいい？
1回目の操作では上から一定数が削られる
→2回目の操作では、各独立成分で上からいくつかが削られる

→大きいほうから見て行って、現在残せるのを後で消さなければいけない事態は起こらない

→つまり、上で残すと決めた辺と小さい辺のufを計算できればいい？
→小さい辺のufは部分永続で楽々

大きい辺は…
小さい辺からくっつけていく過程で考える？
小さい辺から付けていったとき、どこかのタイミングで頂点の重みが超えればいい？
→ちょっと違うけど方針としては良さそう

正確に考えてみる
辺をufした時点で連結成分の重みが辺以上→採用確定 & その連結成分の保留中辺も全て採用
そうでない場合→採用を保留にする
で解けそうだ

保留リストの大きさはufの時に小さいほうを大きいほうに併合でマージテク計算量になる
必要なのは数だけなのでマージも必要なかった

"""

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,h,w):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            h[ap] += h[bp]
            w[ap] += w[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            h[bp] += h[ap]
            w[bp] += w[ap]
        else:
            p[bp] = ap
            rank[ap] += 1
            h[ap] += h[bp]
            w[ap] += w[bp]

        return False

from sys import stdin
N,M = map(int,stdin.readline().split())
X = list(map(int,stdin.readline().split()))

p = [i for i in range(N)]
rank = [0] * N
wait = [0] * N
h = [i for i in X] #頂点の重み合計

YAB = []
for i in range(M):
    A,B,Y = map(int,stdin.readline().split())
    YAB.append((Y,A-1,B-1))
YAB.sort()

for i in range(M):
    Y,A,B = YAB[i]
    uf_union(A,B,p,rank,h,wait)

    np = uf_find(A,p)
    nweight = h[np]
    if nweight >= Y:
        wait[np] = 0
        #print (0,Y,nweight)
    else:
        wait[np] += 1
        #print (1,Y,nweight)

#print (wait)
print (wait[uf_find(0,p)])


Measured memory_bytes: 100064
#include <bits/stdc++.h>
namespace ac {
    using namespace std;
}
using namespace std;
using namespace ac;
typedef int64_t ll;
namespace ac {
    template<typename T> map<T, bool> sieveOfEratosthenes(T n) {
        map<T, bool> res;
        res[0] = false;
        res[1] = false;
        for (size_t i = 2; i <= (size_t)n; i++) {
            res[i] = true;
        }
        // size_t p = 0;
        for (size_t i = 2; i <= (size_t)n; i++) {
            if (res[i]) {
                // prime[p++] = i;
                for (size_t j = 2 * i; j <= (size_t)n; j += i) {
                    res[j] = false;
                }
            }
        }
        return res;
    }
}
int table2017[100005];
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll n;
        in >> n;
        auto s = sieveOfEratosthenes(100005);
        memset(table2017, 0, sizeof(table2017));
        for (int i = 1; i <= 100000; i++) {
            table2017[i] = (s[i] && s[(i + 1) / 2]) + table2017[i - 1];
        }
        for (int i = 0; i < n; i++) {
            ll l, r, ans = 0;
            in >> l >> r;
            ans = table2017[r] - table2017[l - 1];
            out << ans << '\n';
        }
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 5760
N=int(input())
h=list(map(int,input().split()))
h1=abs(h[0]-h[1])
h0=0
for i in range(1,N-1):
    h0,h1=h1,min(
    abs(h[i+1]-h[i-1])+h0,
    abs(h[i+1]-h[i])+h1
    )
print(h1)

Measured memory_bytes: 13980