akhauriyash/Code-Regression huggingface dataset:
# include <bits/stdc++.h>
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
using lint = long long;
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; }

int main()
{
    int a, b, h;
    cin >> a >> b >> h;

    cout << (a + b) * h / 2 << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

typedef struct {
    int p1;
    int p2;
    int p3;
} TRIANGLE;

void sort(int *p)
{
    int i, j;
    int t;
    
    for (i = 0; i < 3; i++){
        for (j = 0; j < 2; j++){
            if (p[j] > p[j + 1]){
                t = p[j];
                p[j] = p[j + 1];
                p[j + 1] = t;
            }
        }
    }
}

int main(void)
{
    int N;
    int p[3];
    TRIANGLE poligon[1000];
    int i, j;
    int n;
    int cnt;
    
    scanf("%d", &N);
    
    cnt = 0;
    n = 0;
    for (i = 0; i < N; i++){
        scanf("%d%d%d", &p[0], &p[1], &p[2]);
        sort(p);
        for (j = 0; j < n; j++){
            if (poligon[j].p1 == p[0] && poligon[j].p2 == p[1] && poligon[j].p3 == p[2]){
                cnt++;
                break;
            }
        }
        if (j == n){
            poligon[n].p1 = p[0];
            poligon[n].p2 = p[1];
            poligon[n].p3 = p[2];
            n++;
        }
    }
    
    printf("%d\n", cnt);

    return (0);
}



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

int main(void){
  int A,B;
  int an;
  char str[10];

  fgets(str,sizeof(str),stdin);
  A=atoi(strtok(str," "));
  B=atoi(strtok(NULL," "));

  an=A+B;
  if(an<A-B){
    an=A-B;
  }
  if(A*B>an){
    an=A*B;
  }

  printf("%d",an);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    
    int a,b,c,max,mid,min;
    cin>>a>>b>>c;
    
    max=a;
    if(max<b)max=b;
    if(max<c)max=c;
    
    if(max==a)mid=b,min=c;
    if(max==b)mid=a,min=c;
    if(max==c)mid=a,min=b;
    
    cout<<max*10+mid+min<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    long double a, b, x;
    cin >> a >> b >> x;
    long double ans;
    if (a * a * b > 2 * x) {
        ans = atan(a * b * b / 2 / x);
    } else {
        ans = atan(2 * (a * a * b - x) / a / a / a);
    }
    cout << setprecision(12) << ans / M_PI * 180 << endl;
}


Measured memory_bytes: 256
/*************************************************************************
    > File Name: b.cpp
    > Author: Amano Sei
    > Mail: amano_sei@outlook.com 
    > Created Time: 2020年01月19日 星期日 21时30分06秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    if(a > b)
        swap(a, b);
    while(b--)
        printf("%d", a);
    return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
// O(n loglog n)
void eratosthenes(long long n, vector<bool>& table, vector<long long>& primes)
{
	table.resize(n+1);
	fill(table.begin(), table.end(), true);
	if (n >= 0)
		table[0] = false;
	if (n >= 1)
		table[1] = false;
	for (int i = 2; i*i <= n; i++) {
		if (table[i] == false)
			continue;
		for (int j = i+i; j <= n; j+=i) {
			table[j] = false;
		}
	}
	for (int i = 0; i < n+1; i++) {
		if (table[i])
			primes.push_back(i);
	}
}
int main(void)
{
	int n;
	cin >> n;
	vector<bool> table;
	vector<long long> primes;
	map<int, long long> m;
	eratosthenes(n, table, primes);
	for (int i = 2; i <= n; i++) {
		int tmpn = i;
		for (int j = 0; primes[j]*primes[j] <= tmpn; j++) {
			while (tmpn % primes[j] == 0) {
				tmpn /= primes[j];
				m[primes[j]]++;
			}
		}
		if (table[tmpn])
			m[tmpn]++;

	}
	long long ans = 0;
	long long count75 = 0, count3 = 0, count5 = 0, count15 = 0, count25 = 0;
	for (auto e : m) {
		//printf("%d: %d\n", e.first, e.second);
		if (e.second >= 74)
			count75++;
		if (e.second >= 2)
			count3++;
		if (e.second >= 4)
			count5++;
		if (e.second >= 14)
			count15++;
		if (e.second >= 24)
			count25++;
	}
	ans += count75;
	ans += (count3-1) * count25;
	ans += (count5-1) * count15;
	if (count5 >= 2)
		ans += (count3-2) * count5 * (count5-1)/2;
	cout << ans << endl;
	return 0;
}

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

int main(){
  string S;
  cin>>S;
  for(int i=0; i<S.size(); i++)
    if((i%2 == 0 && S[i]=='L') || (i%2 == 1 && S[i]=='R')){
      cout<<"No"<<endl;
      return 0;
    }
  cout<<"Yes"<<endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int main()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s.insert(s.begin(), '?');
    s.push_back('?');
    char t[200006], d[200006];
    for(int i = 1; i <= q; i++){
        cin >> t[i] >> d[i];
    }
    int nr = n + 1;
    int nl = 0;
    for(int i = q; i > 0; i--){
        if(nr - nl == 1){
            cout << 0 << endl;
            return 0;
        }
        if(d[i] == 'R'){
            if(t[i] == s[nr - 1]){
                nr--;
            }
            if(t[i] == s[nl]){
                nl--;
            }
        }
        if(d[i] == 'L'){
            if(t[i] == s[nr]){
                nr++;
            }
            if(t[i] == s[nl + 1]){
                nl++;
            }
        }
    }
    cout << n - nl - (n - nr + 1) << endl;
}

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

	
int main(){
	int n,m;
	cin >> n >> m;
	auto a = set<int>();
	auto dp = vector<long long>(n+1,0);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 0; i < m; i++)
	{	
		int num;
		cin >> num;
		a.insert(num);
		if(num==1) dp[1] = 0; 
	}
	
	for (int i = 0; i < n-1; i++)
	{
      		if(a.find(i+2)!=a.end()){
            	dp[i+2] = 0;
            }else{
              dp[i+2] += dp[i+1]+dp[i];
              dp[i+2] %= 1000000007;
            }
		
	}
	
	cout << dp[n];
}


Measured memory_bytes: 5760
from collections import Counter
n = int(input())
ai = list(map(int,input().split()))
pl = []
mi = []
for i in range(n):
    pl.append(i+ai[i])
    mi.append(i-ai[i])
x = Counter(pl)
y = Counter(mi)
cnt = 0
for i in x.keys():
    cnt += x[i]*y[i]
print(cnt)


Measured memory_bytes: 63384
import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)

Measured memory_bytes: 58540
i,N,R[200000],max,min;
main(){
    for(scanf("%d",&N);i<N;scanf("%d",&R[i++]));
    max=R[1]-R[0];
    min=R[0];
    for(i=1;i<N;i++){
        max=max<R[i]-min?R[i]-min:max;
        min=min>R[i]?R[i]:min;
    }
    printf("%d\n",max);
}

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

vector<ll> comdiv(ll x){
    vector<ll> res;
    stack<ll> big;
    for(ll i = 1; i*i <= x; i++){
        if(x%i == 0){
            res.push_back(i);
            big.push(x/i);
        } 
    }
    while(!big.empty()){
            res.push_back(big.top());
            big.pop();
    }
    return res;
}

int main(){
    ll n;
    cin >> n;
    vector<ll> li = comdiv(n);
    ll ans = 0;
    if(n == 1){
        cout << ans << endl;
        return 0;
    }
    li.erase(li.begin());
    for(auto p:li){
        p--;
        if((n/p) == n%p) ans += p;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	int nmax = 0, count = 0;
	int a, b;
	for (int i = 0; i < M; ++i) {
		cin >> a >> b;
		if (a < N) {
			count += N - a;
			nmax = max(nmax, N - a);
		}
	}
	cout << count - nmax << endl;
	return 0;
}

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

#define ll long long
#define MAXN 200005

using namespace std;

ll dp[MAXN], bit[MAXN];

void upd(int x, ll y, int n) {

    for(int i = x; i <= n; i += i & -i)
        bit[i] = max(bit[i], y);
}

ll get(int x) {

    ll ans = 0;
    for(int i = x; i > 0; i -= i & -i)
        ans = max(ans, bit[i]);
    return ans;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    int h[n];
    for(int i = 0; i < n; i++)
        cin >> h[i];
    ll a[n];
    for(int i = 0; i < n; i++)
        cin >> a[i];
    
    for(int i = 0; i < n; i++) {
        dp[i] = get(h[i] - 1) + a[i];
        upd(h[i], dp[i], n);
    }

    ll ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}


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

public class Main {
	
	public static class Fisher implements Comparable<Fisher>{
		int number, fished;

		public Fisher(int number, int fished) {
			super();
			this.number = number;
			this.fished = fished;
		}

		@Override
		public int compareTo(Fisher arg0) {
			return arg0.fished - this.fished == 0 ? this.number - arg0.number : arg0.fished - this.fished;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		final int n = sc.nextInt();
		
		Fisher[] fish = new Fisher[n];
		
		for(int i = 0; i < n; i++){
			final int a = sc.nextInt();
			final int v = sc.nextInt();
			
			fish[i] = new Fisher(a, v);
		}
		
		Arrays.sort(fish);
		
		System.out.println(fish[0].number + " " + fish[0].fished);

	}

}

Measured memory_bytes: 17328
import numpy as np
import bisect

n=int(input())
a=sorted([int(i) for i in input().split()])
b=sorted([int(i) for i in input().split()])
c=sorted([int(i) for i in input().split()])

count=0
index_b=0
index_c=0
count_b=[0]*(n+1)
for i in range(n):
        count_b[i+1]=bisect.bisect_left(a,b[i])+count_b[i]
for i in range(n):
        count+=count_b[bisect.bisect_left(b,c[i])]
print(count)

Measured memory_bytes: 38048
n = int(input())
MOD = 10**9+7
dp = [[[[0]*4 for _ in range(4)] for _ in range(4)] for _ in range(n+1)]
dp[0][3][3][3] = 1
for i in range(1,n+1):
    for c1 in range(4):
        for c2 in range(4):
            for c3 in range(4):
                for a in range(4):
                    if c2 == 0 and c1 == 1 and a == 2:
                        continue
                    if c2 == 0 and c1 == 2 and a == 1:
                        continue
                    if c2 == 1 and c1 == 0 and a == 2:
                        continue
                    if c3 == 0 and c1 == 1 and a == 2:
                        continue
                    if c3 == 0 and c2 == 1 and a == 2:
                        continue
                    dp[i][c2][c1][a] += dp[i-1][c3][c2][c1]
                    dp[i][c2][c1][a] %= MOD
ans = 0
for c1 in range(4):
    for c2 in range(4):
        ans += sum(dp[i][c1][c2])
        ans %= MOD
print(ans)


Measured memory_bytes: 3316
w,h,n = map(int,input().split())
ans = 0
x,y = map(int,input().split())
for i in range(n-1):
    nx,ny = map(int,input().split())
    if (nx >= x) == (ny >= y):
        cost = max(abs(nx-x), abs(ny-y))
    else:
        cost = abs(nx-x)+abs(ny-y)
    ans += cost
    x,y = nx,ny
print(ans)



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

int main(){ 
    int n;
    cin>>n;
    int b=0;
    vector<int> a(n);
    for(int i=0;i<n;i++) {
    cin>>a[i];
    }
    for(int j=0;j<100;j++){
    for(int i=0;i<n;i++){
        if(a[i]%2==1){
            cout <<b;
            return 0;
        }
        if(i==n-1){
            b++;
        }
        a[i]=a[i]/2;
    }
    }
    return 0;
}


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

int main(){
	int n,k;
    cin >> n >> k;
    VI a(n);
    rep(i,n) cin >> a[i];

    cout << (n+k-3)/(k-1) << endl;

	return 0;
}

Measured memory_bytes: 640
N = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)

cnt = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            c = L[i]
            b = L[j]
            a = L[k]
            if c < a+b and c > b-a and a != b and b != c and c != a:
                cnt += 1
print(cnt)


Measured memory_bytes: 73600
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const ll inf=1e9+7;

int main(){
  int a,p;
  cin>>a>>p;

  cout<<(a*3+p)/2<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << "Hello World" << endl; 
	}
	if (n == 2) {
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}
}	

Measured memory_bytes: 3524
#include<iostream>

int main()
{
	int n;
	int x[3], y[3], z[3], w[3];
	while( std::cin >> n, n )
	{
		for( int i = 0; i != n; ++i )
		{
			x[2] = y[2] = z[2] = w[2] = 0;
			for( int j = 0; j != 2; ++j )
				std::cin >> x[j] >> y[j] >> z[j] >> w[j];

			x[2] += x[0]*x[1] - y[0]*y[1] - z[0]*z[1] - w[0]*w[1];
			y[2] += x[0]*y[1] + y[0]*x[1] + z[0]*w[1] - w[0]*z[1];
			z[2] += x[0]*z[1] - y[0]*w[1] + z[0]*x[1] + w[0]*y[1];
			w[2] += x[0]*w[1] + y[0]*z[1] - z[0]*y[1] + w[0]*x[1];
		
			std::cout << x[2] << ' ' << y[2] << ' ' << z[2] << ' ' << w[2] << std::endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1164
//****************************//
/**********  main *************/
//****************************//
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, a, b) for(i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())

double pi = 3.141592653589793;

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

int main() {

    std::cin.tie(0);

    int a;
    int res;
    int i, tmp;

    cin >> a;

    res = a + a*a + a*a*a;

    cout << res << endl;

    return 0;
}


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

int main(){
    int a,b,k;
    cin >> a >> b >> k;
    if(((b-a+1) <= k*2)){
        for(int i = a;i <= b;i++){
            cout << i << endl;
        }
    }
    else{
        for(int i = a;i < a+k;i++) cout << i << endl;
        for(int i = b - k + 1;i < b+1;i++) cout << i << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
//#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main()
{
	int N, X, Y, ans = -1;
	cin >> N;
	vector<int>V(N), C(N);
	rep(i, N)cin >> V[i];
	rep(i, N)cin >> C[i];
	for (int i = 0; i < (1 << N); i++)
	{
		X = Y = 0;
		for (int j = 0; j < N; j++)
		{
			if ((i >> j) & 1)
			{
				X += V[j];
				Y += C[j];
			}
		}
		ans = max(ans, X - Y);
	}
	cout << ans;
}

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

n, q = map(int, input().split())
INF = 2**31-1

Len = (n-1).bit_length()
size = 2**Len
tree = [INF]*(2*size)
lazy = [None]*(2*size)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>1
    lc = 0 if l & 1 else (L&-L).bit_length()
    rc = 0 if r & 1 else (R&-R).bit_length()
    for i in range(Len):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
        
        

def propagates(ids):
    #上から更新
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i]=tree[2*i]=lazy[2*i+1]=tree[2*i+1]=v
        lazy[i]=None

#[l,r)の探索
def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R]=tree[R]=x
        if L&1:
            lazy[L]=tree[L]=x
            L+=1
        L>>=1;R>>=1
    #値を更新し終わったら、最小値を下から更新
    for i in ids:
        if 2*i+1<size*2:
            tree[i]=min(tree[i*2],tree[i*2+1])
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = INF
    while L<R:
        if R&1:
            R-=1
            s = min(s,tree[R])
        if L&1:
            s = min(s,tree[L])
            L+=1
        L>>=1;R>>=1
    return s

ans = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:
        ans.append(query(b[0],b[1]+1))
    else:
        update(b[0],b[1]+1,b[2])
        
print('\n'.join(map(str,ans)))


Measured memory_bytes: 17588
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define pb(b) push_back(b) 
#define all(a) a.begin(),a.end()
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
const int mod=1e9+7;
/* 
UnionFind：素集合系管理の構造体(union by size)
isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
treeSize(x): x を含む集合の要素数。
*/
struct UnionFind{
 vector<int>size,parents;
 UnionFind(){}
 UnionFind(int n){//make n trees.
  size.resize(n,0);
  parents.resize(n,0);
  for(int i=0;i<n;i++)makeTree(i);
 }
 void makeTree(int x){
   parents[x]=x;//the parent of x is x
   size[x]=1;
  }
 bool isSame(int x,int y){return findRoot(x)==findRoot(y);}
 bool unite(int x,int y){
  x = findRoot(x);
  y = findRoot(y);
  if(x==y)return false;
  if(size[x]>size[y]){
   parents[y]=x;
   size[x]+=size[y];
  } 
  else{
   parents[x]=y;
   size[y]+=size[x];
  }
  return true;
 }
 int findRoot(int x){//木の根を探す,計算量削減のため低く
  if(x!=parents[x])parents[x]=findRoot(parents[x]);
  return parents[x];
 }
 int treeSize(int x){return size[findRoot(x)];}
};
/*pi*/const double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/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;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll i,fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=0,tmp=n;while(tmp/10>0){tmp/=10;d++;}return d;}
/*迷路移動*/const int dx[4]={1,0,-1,0};const int dy[4]={0,1,0,-1};
llfor;////////////////////////////////////////////////////////////
int main(){
 ll n,m;
 cin>>n>>m;
 ll a[n+10],b[n+10],c[m+10],d[m+10];
 rep(i,0,n)cin>>a[i]>>b[i];
 rep(i,0,m)cin>>c[i]>>d[i];

 ll memo,tmp;
 rep(i,0,n){
  tmp=1e9;
  rep(j,0,m){
   ll e=abs(a[i]-c[j])+abs(b[i]-d[j]);
   if(tmp>e){
    tmp=e;
    memo=j+1;
   }
  }
  pr(memo);
 }
return 0;}

Measured memory_bytes: 3608
# Keitai Message

ans = []

words = [0, [".", ",", "!", "?", " "]
        , ["a", "b", "c"]
        , ["d", "e", "f"]
        , ["g", "h", "i"]
        , ["j", "k", "l"]
        , ["m", "n", "o"]
        , ["p", "q", "r", "s"]
        , ["t", "u", "v"]
        , ["w", "x", "y", "z"]
        ]

n = int(input())
for j in range(n):
    a = list(input())
    tips = []
    cnt = 1
    ansT = ""
    for i in range(1, len(a)):
        if a[i] == a[i-1]:
            cnt += 1
        else:
            tips.append([int(a[i-1]), cnt])
            cnt = 1
    tips.append([int(a[-1]), cnt])

    for i in tips:
        if i[0] == 0:
            pass
        else:
            ansT += words[i[0]][i[1] % len(words[i[0]]) - 1]

    ans.append(ansT)

for i in ans:
    print(i)



Measured memory_bytes: 5656
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def prime(n,is_prime=True):
    """
    n: positive integer
    if is_prime: return n is prime
    else: return list of prime <= n
    """
    if n<=1: return False if is_prime else []
    S=[1]*(n+1)
    S[0]=0; S[1]=0
    for i in range(2,n):
        if S[i]==0: continue
        for j in range(2*i,n+1,i):
            S[j]=0
    if is_prime: return bool(S[n])
    else: return [p for p in range(n+1) if S[p]]
def resolve():
    n=int(input())
    P=prime(n,False)
    bin=[0]*(n+1)
    for p in P:
        q=p
        while(q<=n):
            bin[p]+=n//q
            q*=p
    ans=1
    for b in bin:
        ans=ans*(b+1)%MOD
    print(ans)
resolve()

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_V = int(2e5) + 5;
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir[] = {"R", "D", "L", "U"};
#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 (ll i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

struct edge {
    ll from, to, a, b;
    edge(ll u, ll v, ll a, ll b) : from(u), to(v), a(a), b(b){};
};

vector<edge> G[MAX_V];
ll dmin[MAX_V];

void add_edge(ll u, ll v, ll a, ll b) {
    G[u].push_back(edge(u, v, a, b));
    G[v].push_back(edge(v, u, a, b));
}

ll f(ll b, ll a, ll x) { return ll(ceil(b / double(a + x) + double(x))); }

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;  //小さいものから取り出す
    fill(dmin, dmin + MAX_V, LLINF);
    dmin[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (dmin[v] < p.first) continue;
        for (auto &e : G[v]) {
            ll k = max(0.0, pow(e.b, 0.5) - (e.a + dmin[v])), cost;
            cost = f(e.b, e.a + dmin[v], 0);
            if (k > 0) {
                cost = min(cost,min(f(e.b,e.a+dmin[v],floor(k)),f(e.b,e.a+dmin[v],ceil(k))));
            }
            if (dmin[e.to] > dmin[v] + cost) {
                dmin[e.to] = dmin[v] + cost;
                que.push(P(dmin[e.to], e.to));
            }
        }
    }
}

int main() {
    ll n, m, s, g;
    cin >> n >> m >> s >> g;
    REP(i, m) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        add_edge(u, v, a, b);
    }
    dijkstra(s);
    cout << (dmin[g]!=LLINF?dmin[g]:-1) << endl;
    return 0;
}



Measured memory_bytes: 32372
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <tuple>
#include <functional>
#include <cstring>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int  i = 0; i < n; i++)
#define irep2(i,a,n) for(int i = a; i < n; i++)
#define lrep(i,n) for(long long  i = 0; i < n; i++)
#define lrep2(i,a,n) for(long long i = a; i < n; i++)

typedef long long ll;
typedef std::vector<int> v_int;
typedef std::vector<std::vector<int> > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<std::vector<ll> > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<std::vector<std::string> > v2_string;
typedef std::pair<ll, ll> pll;

using namespace std;


int main() 
{
    int n, t;
    ll ans = 0;
    cin >> n >> t;
    
    int pre_time = 0;
    irep(i, n) {
        ans += t;

        int time; 
        cin >> time;
            
        if((time - pre_time) < t && time != 0) {
            ans -= (t - (time-pre_time));
        }
        pre_time = time; 
    }

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


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
        // TODO ?????????????????????????????????????????????
        
        boolean first=true;
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String line;
            while ((line = br.readLine()) != null) {
            	String[] str=line.split(" ");
            	int w=Integer.parseInt(str[0]);
            	int h=Integer.parseInt(str[1]);
            	int x=Integer.parseInt(str[2]);
            	int y=Integer.parseInt(str[3]);
            	int r=Integer.parseInt(str[4]);
            	
            	if(w>=x+r&&x-r>=0&&y-r>=0&&y+r<=h){
            		System.out.println("Yes");
            	}else{
            		System.out.println("No");
            	}
            	break;
            }
        }
    }
}

Measured memory_bytes: 24332
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846264338327950L
#define ld long double
int main() {
ld a,b,h,m;cin>>a>>b>>h>>m;
ld rad=PI*2*((ld)h / 12.0 + ((ld)m / 60.0) / 12.0 - (ld)m / 60.0);
ld rsq = (ld)(a * a + b * b) - (ld)(2 *a*b) * cosl(rad);
rsq=sqrt(rsq);
cout<<fixed<<setprecision(15)<<rsq<<endl;
//printf("%20.20Lf\n", sqrtl(rsq));
}

Measured memory_bytes: 4052
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for i in range(H)]
visited = [[-1] * W for j in range(H)]

d = deque([[Ch - 1, Cw - 1]])
wq = deque([[Ch - 1, Cw - 1]])

visited[Ch - 1][Cw - 1] = 0
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
warp_move = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2],
             [-1, -2], [-1, -1], [-1, 1], [-1, 2],
             [0, -2], [0, 2],
             [1, -2], [1, -1], [1, 1], [1, 2],
             [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
             ]
warp = 0

while len(d) > 0 or len(wq) > 0:
    while len(d) > 0:
        y, x = d.popleft()
        wq.append([y, x])
        for i, j in move:
            nexty, nextx = y + i, x + j
            if nexty == Dh - 1 and nextx == Dw - 1:
                print(warp)
                exit()
            if nextx >= 0 and nextx < W and nexty >= 0 and nexty < H:
                if S[nexty][nextx] == "." and visited[nexty][nextx] == -1:
                    visited[nexty][nextx] = warp
                    d.append([nexty, nextx])

    warp += 1
    while len(wq) > 0:
        y, x = wq.popleft()
        for i, j in warp_move:
            warp_y, warp_x = y + i, x + j
            if warp_y == Dh - 1 and warp_x == Dw - 1:
                print(warp)
                exit()
            if warp_x >= 0 and warp_x < W and warp_y >= 0 and warp_y < H:
                if S[warp_y][warp_x] == "." and visited[warp_y][warp_x] == -1:
                    visited[warp_y][warp_x] = warp
                    d.append([warp_y, warp_x])
print(-1)


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

int main() {
  int t, n;
  for (int i = 0; i < 4; i++) {
    cin >> t >> n;
    if (t == 1) cout << 6000 * n << endl;
    if (t == 2) cout << 4000 * n << endl;
    if (t == 3) cout << 3000 * n << endl;
    if (t == 4) cout << 2000 * n << endl;
  }
  return 0;
}


Measured memory_bytes: 3108
//Count ABC
#include <bits/stdc++.h> //C++の機能を「全て」読み込むための命令
#define rep(i,n) for(int i=0; i<(n); ++i)
#define cout(x) cout<<(x)<<endl
using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll inf=1e18;
const int N=2e5+10;
ll factorial(ll x){//階乗の計算
    if(x==0||x==1) return 1;
    return x*factorial(x-1);
}
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;}//最小公倍数
int num_digit(ll a){//桁数を求める
    int num_dig = 0;
    while(a!=0){
        a /= 10;
        ++num_dig;
    }
    return num_dig;
}
vector<ll> digit(ll a){//桁の数字を求める
    vector<ll> dig(num_digit(a));
    for(int i=num_digit(a)-1; i>=0; --i){
        dig[i] = a%10;
        a /= 10; 
    }
    return dig;
}


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

    int cnt=0;
    for(int i=0;i<=n-3;++i){
        if(s.substr(i,3)=="ABC") ++cnt;
    }
    cout(cnt);
    return 0;
}

Measured memory_bytes: 256
def main():
    x = int(input())
    if x <= 599:
        print(8)
    elif x <= 799:
        print(7)
    elif x <= 999:
        print(6)
    elif x <= 1199:
        print(5)
    elif x <= 1399:
        print(4)
    elif x <= 1599:
        print(3)
    elif x <= 1799:
        print(2)
    elif x <= 1999:
        print(1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61720
#include<stdio.h>
#define N 1000
void sort(int A[],int n){
  int i;
  for(i=1;i<=n;i++){
    if(i>1){
      printf(" ");
    }
    printf("%d",A[i]);
  }
  printf("\n");
}

int main(){
  int n,i,j;
  int A[N+1];
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
  }
  sort(A,n);
  for(j=2;j<=n;j++){
    int key=A[j];
    i=j-1;
    while(i>0&&A[i]>key){
      A[i+1]=A[i];
      i--;
    }
    A[i+1]=key;
    sort(A,n);
  }
  return 0;
}


Measured memory_bytes: 2100
import numpy as np
import sys
from numba import njit, i4
read = sys.stdin.read

@njit((i4[:],), cache=True)
def solve(stdin):
	h, w, m = stdin[:3]

	row = np.zeros(h, np.int32)
	col = np.zeros(w, np.int32)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		row[y] += 1
		col[x] += 1

	max_cnt_y = max(row)
	max_cnt_x = max(col)
	max_pair = np.sum(row == max_cnt_y) * np.sum(col == max_cnt_x)
	for i in range(3, m * 2 + 3, 2):
		y, x = stdin[i: i + 2] - 1
		if row[y] == max_cnt_y and col[x] == max_cnt_x:
			max_pair -= 1

	return max_cnt_y + max_cnt_x - (max_pair == 0)

print(solve(np.fromstring(read(), dtype=np.int32, sep=' ')))

Measured memory_bytes: 114620
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024*1024), bufio.MaxScanTokenSize)
}

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

func nextFloat() float64 {
	sc.Scan()
	f, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

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

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = nextInt()
	}
	return result
}

func main() {
	N := nextInt()
	X := nextInt()
	T := nextInt()
	var num int
	for N > 0 {
		N -= X
		num++
	}
	fmt.Println(num * T)
}

func move(a, b int) int {
	ret := b
	if a == 0 {
		return 0
	} else if a-b < 0 {
		return a
	}
	return ret
}


Measured memory_bytes: 1800
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#define ll              long long
#define PII             pair<int, int>
#define rep(i,a,b)      for(int  i=a;i<=b;i++)
#define dec(i,a,b)      for(int  i=a;i>=b;i--)
using namespace std;
int dir[4][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846;
const double eps = 1e-6;
const int mod =1e9+7;
const int N = 1e5+5;
//if(x<0 || x>=r || y<0 || y>=c)

inline ll read()
{
	ll x = 0; bool f = true; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = false; c = getchar(); }
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return f ? x : -x;
}
ll gcd(ll m, ll n)
{
	return n == 0 ? m : gcd(n, m % n);
}
ll lcm(ll m, ll n)
{
	return m * n / gcd(m, n);
}
bool prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}
ll qpow(ll m, ll k, ll mod)
{
    ll res = 1, t = m;
    while (k)
    {
        if (k & 1)
            res = res * t % mod;
        t = t * t % mod;
        k >>= 1;
    }
    return res;
}      

int main()
{
    ll n,w;
    cin >> n >> w;
    vector<pair<ll, ll>> a(n + 1);
    vector<vector<ll>> dp(n + 1,vector<ll>(w+1));
    rep(i, 1, n)
    {
        cin >> a[i].first>>a[i].second;
    }
    rep(i, 1, n)
    {
        rep(j, 0, w)
        {
            if ( j >=a[i].first)
                dp[i][j] = max(dp[i - 1][j],dp[i - 1][j-a[i].first] + a[i].second);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    ll res = 0;
    rep(i, 1, w)
    {
        res = max(res, dp[n][i]);
    }
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 80256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



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

    int n;
    cin >> n;
    vector<int> a, b;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back(x + y);
        b.push_back(x - y);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cout << max(a[n-1] - a[0], b[n-1] - b[0]) << endl;
    return 0;
}


Measured memory_bytes: 5136
#include<bits/stdc++.h>
using namespace std;
 int main() {
	int a,b,c;
   cin>>a>>b>>c;
   if(a==b) {
   	if(a==c) cout<<"No";
     else cout<<"Yes";
   }
   else if(a==c) {
   	if(a==b) cout<<"No";
     else cout<<"Yes";
   }
   else if(b==c) {
   	if(a==b) cout<<"No";
     else cout<<"Yes";
   }
   else cout<<"No";
 }

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#include<functional>
//#include<bits/stdc++.h>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ld pi = 3.141592653589793238;
//printf("%.10f\n", n);

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll modpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y % 2) { res *= x; res %= mod; }
		x = x * x % mod; y /= 2;
	}
	return res;
}
ll keta(ll n) {
	ll res = 0;
	while (n >= 1) {
		res += n % 10; n /= 10;
	}
	return res;
}
ll nCk(ll n, ll k) {
	ll a = 1, b = 1;
	for (int h = n - k + 1; h <= n; h++) { a *= h; a %= mod; }
	for (int h = 1; h <= k; h++) { b *= h; b %= mod; }
	return a * modpow(b, mod - 2) % mod;
}
bool IsPrime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) { // 素数ではない
			return false;
		}
	}
	// 素数である
	return true;
}

ll test[12345678];
signed main() {
	ll n, m, k, a, b, c = 0, d = 0, cnt = 0, ans = 0;
	string s, t;
	cin >> n;
	for (ll x = 1; x <= 100; x++) {
		for (int y = 1; y <= 100; y++) {
			for (int z = 1; z <= 100; z++) {
				ll hh = pow(x, 2) + pow(y, 2) + pow(z, 2) + (x * y) + (y * z) + (z * x);
				test[hh]++;
			}
		}
	}
	for (int h = 1; h <= n; h++) {
		cout << test[h] << endl;
	}
	return 0;
}

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

int main() {
    int W;
    int c = 0;
    while(++c, cin >> W, W) {
        int N;
        cin >> N;
        vector<vector<int>> dp(N+1, vector<int>(W+1, -1));
        dp[0][0] = 0;
        for(int i=0; i<N; ++i) {
            int v, w;
            scanf("%d,%d", &v, &w);
            for(int j=0; j<=W; ++j) {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
                if(j+w <= W && dp[i][j] != -1) {
                    dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j] + v);
                }
            }
        }
        int w = 0;
        for(int i=0; i<=W; ++i) {
            if(dp[N][w] < dp[N][i]) {
                w = i;
            }
        }
        cout << "Case " << c << ':' << endl;
        cout << dp[N][w] << endl;
        cout << w << endl;
    }
}


Measured memory_bytes: 6804
#include "iostream"
#include "vector"
using namespace std;

int main(){
    int n, d, x;
    while(cin >> n >> d >> x){
        int ans = x;

        for(int i = 0 ; i < n ; ++i){
            int a;
            cin >> a;
            for(int j = 1 ; j <= d ; j += a){
                ++ans;
            }
        }

        cout << ans << '\n';
    }

    cout << flush;

    return 0;
}

Measured memory_bytes: 256
X, Y, Z, K = gets.split(' ').map(&:to_i)
score = []
score2 = []

a = gets.split(' ').map(&:to_i).sort.reverse
b = gets.split(' ').map(&:to_i).sort.reverse
c = gets.split(' ').map(&:to_i).sort.reverse

a.each do |i|
  b.each do |j|
    score.push(i + j)
  end
end

score = score.sort.reverse

score.slice(0..K).each do |i|
  c.each do |j|
    score2.push(i + j)
  end
end

score2 = score2.sort.reverse

K.times do |i|
  puts score2[i]
end

Measured memory_bytes: 106992
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <complex>
#include <tuple>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
// #define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define reps(i,n) for(int i=1;i<=int(n);++i)
#define repr(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define reprs(i,x) for(int i=((int)(x));i>0;i--)
#define iceil(x,y) (x+y-1)/y
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define LF "\n"

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII> PP;

ll N;

int main(){
	FAST;
	cin >> N;
	ll a;
	ll b1=0, b2=0, b4=0;
	rep(i,N) {
		cin >> a;
		if (a%4==0) b4++;
		else if (a%2==0) b2++;
		else b1++;
	}

	if (b2==0) {
		if (b1 <= (b4+1)) cout << "Yes\n";
		else cout << "No\n";
	}
	else {
		if (b1 <= b4) cout << "Yes\n";
		else cout <<"No\n";
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define MOD 1000000007
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  string a[H];
  long long dp[H][W] = {};
  for (int i=0; i<H; i++) cin >> a[i];

  for (int i=0; i<H; i++) {
    if (a[i][0] == '.') dp[i][0] = 1;
    else break;
  }
  for (int j=0; j<W; j++) {
    if (a[0][j] == '.') dp[0][j] = 1;
    else break;
  }
  for (int i=1; i<H; i++) {
    for (int j=1; j<W; j++) {
      if (a[i-1][j] == '.') dp[i][j] = dp[i-1][j];
      if (a[i][j-1] == '.') dp[i][j] += dp[i][j-1];
      dp[i][j] %= MOD;
    }
  }
  cout << dp[H-1][W-1] << endl;
}


Measured memory_bytes: 9088
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
using namespace std;

int main(void){

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

    int count = 0;

    for(int i=0;i<n-2;i++){
        if(a[i]<a[i+1] && a[i+1]<a[i+2])count++;
        else if(a[i]>a[i+1] && a[i+1]>a[i+2])count++;
       // cout<<a[i]<<" "<<count<<endl;
    }

    cout<<count<<endl;


    return 0;

}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
string S[2020];
int L[1600][1600],R[1600][1600];
int dp[1515][1515];


void solve() {
	int i,j,k,l,r,x,y,x2,y2; string s;
	
	cin>>N;
	FOR(y,N) {
		cin>>S[y];
		FORR(c,S[y]) {
			if(c!='#') c-='0';
			else c=0;
		}
	}
	ll ret=0;
	for(y=N-1;y>=0;y--) {
		L[y][N]=N;
		R[y][N]=-1;
		for(x=N-1;x>=0;x--) {
			int down=(y<N-1) && (S[y+1][x]>0);
			int right=(x<N-1) && (S[y][x+1]>0);
			
			if(S[y][x]==0) {
				for(y2=y;y2<N;y2++) {
					L[y][x]=N;
					R[y][x]=-1;
				}
			}
			else {
				dp[y][x]=dp[y+1][x]+dp[y][x+1];
				L[y][x]=x;
				if(down&&right) {
					R[y][x]=R[y][x+1];
					
					int r=0;
					for(y2=y+1;y2<N;y2++) {
						if(L[y2][x+1]<=R[y2][x] && r<L[y2][x+1]) {
							dp[y][x]-=dp[y2][L[y2][x+1]];
						}
						r=R[y2][x];
						R[y2][x]=max(R[y2][x],R[y2][x+1]);
						L[y2][x]=min(L[y2][x],L[y2][x+1]);
					}
					
					
				}
				else if(down) {
					R[y][x]=x;
				}
				else if(right) {
					R[y][x]=R[y][x+1];
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=L[y2][x+1];
						R[y2][x]=R[y2][x+1];
					}
				}
				else {
					R[y][x]=x;
					for(y2=y+1;y2<N;y2++) {
						L[y2][x]=N;
						R[y2][x]=0;
					}
				}
				ret+=S[y][x]*dp[y][x];
				dp[y][x]+=S[y][x];
			}
		}
	}
	
	
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 12800
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
using namespace std;


#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


vector<char> ans;

void solve(ll & a, ll & b, char c) {
	a++;
	b--;
	ans.push_back(c);
}
bool move(ll &a, ll &b, char aa, char bb) {
	if (a == 0 and b == 0) return false;
	if (a >= b) solve(b, a, bb);
	else solve(a, b, aa);
	return true;
}

bool move2(ll& a, ll& b, char aa, char bb, ll a1, ll a2, vector<ll> s) {
	if (a == 0 and b == 0) return false;
	if (a > b) solve(b, a, bb);
	else if(a < b) solve(a, b, aa);
	else if (a == b) {
		if(s[a1] <= s[a2])solve(a, b, aa);
		else  solve(b, a, bb);
	}
	return true;
}

int main() {
	ll n, a, b, c;
	cin >> n >> a >> b >> c;
	vector<string> s(n);
	REP(i, n) cin >> s[i];
	bool ok = true;
	vector <vector<ll>> v(n + 1, vector<ll>(3));
	REPR(i, n - 1) {
		REP(j, 3)v[i][j] = v[i + 1][j] + 1;
		if (s[i] == "AB") v[i][0] = 0;
		if (s[i] == "AC") v[i][1] = 0;
		if (s[i] == "BC") v[i][2] = 0;
	}
	if (a + b + c >= 3 or a + b + c == 1) {
		REP(i, n) {
			if (s[i] == "AB") if (!move(a, b, 'A', 'B')) ok = false;
			if (s[i] == "AC") if (!move(a, c, 'A', 'C')) ok = false;
			if (s[i] == "BC") if (!move(b, c, 'B', 'C')) ok = false;
		}
		
	}
	else if (a + b + c == 0)ok = false;
	else if (a + b + c == 2) {
		REP(i, n) {
			if (s[i] == "AB") if (!move2(a, b, 'A', 'B', 1, 2, v[i])) ok = false;
			if (s[i] == "AC") if (!move2(a, c, 'A', 'C', 0, 2, v[i])) ok = false;
			if (s[i] == "BC") if (!move2(b, c, 'B', 'C', 0, 1, v[i])) ok = false;
		}
	}
	if (!ok) {
			cout << "No" << endl;
			return 0;
	}
	cout << "Yes" << endl;
	REP(i, n) cout << ans[i] << endl;
}



Measured memory_bytes: 11908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(true) {
        string S;
        getline(cin, S);
        if(S == ".") break;
        string T;
        getline(cin, T);
        if(S == T) {
            cout << "IDENTICAL" << endl;
            continue;
        }
        vector<string> s, t;
        s.push_back("");
        t.push_back("");
        bool on = false;
        for(int i = 0; i < S.size(); i++) {
            if(S[i] != '"') {
                s.back().push_back(S[i]);
                continue;
            }
            s.push_back("");
            on = !on;
        }
        on = false;
        for(int i = 0; i < T.size(); i++) {
            if(T[i] != '"') {
                t.back().push_back(T[i]);
                continue;
            }
            t.push_back("");
            on = !on;
        }
        int diff = 0;
        /*
        for(int i = 0; i < s.size(); i++) {
            cerr << s[i] << " ";
        }
        cerr << endl;
        for(int i = 0; i < t.size(); i++) {
            cerr << t[i] << " ";
        }
        cerr << endl;
        */
        if(s.size() != t.size()) diff = 100;
        for(int i = 0; i < min(s.size(), t.size()); i++) {
            if(s[i] == t[i]) continue;
            //cerr << i << endl;
            if(i % 2 == 0) {
                //cerr << i << endl;
                diff = 100;
            }
            else diff++;
        }
        if(diff == 1) cout << "CLOSE" << endl;
        else cout << "DIFFERENT" << endl;
    }
    return 0;
}


Measured memory_bytes: 3212
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
list = []
for i in range(M):
  a[i], b[i] = map(int, input().split())
for i in range(M):
  if a[i] == 1:
    list.append(b[i])
  elif b[i] == N:
    list.append(a[i])
list = sorted(list)
ans = 'IMPOSSIBLE'
for i in range(len(list)-1):
  if list[i] == list[i+1]:
    ans = 'POSSIBLE'
    break
print(ans)

Measured memory_bytes: 25372