akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define N 1000000

int main(void){
  int p[N];
  int i,j,n;

  p[0]=0; p[1]=0; p[2]=1;
  for( i=3;i<N;i++ ){
    p[i] = i%2;
  }
  
  for( i=2;i<N;i++ ){
    if( p[i]==1 ){
      for( j=i*2;j<N;j+=i )
	p[j]=0;
    }
  }
  
  for( i=1;i<N;i++ )
    p[i] += p[i-1];
  // p[i] : number of primes that is smaller than i

  while( 1 ){
    if( scanf("%d ",&n)!=1 )
      break;
    printf("%d\n",p[n] );
  }


  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<4;i++)
    cout<<s[i];
    cout<<" ";
    for(int i=4;i<s.size();i++)
    cout<<s[i];
    cout<<endl;
    return 0;
}

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


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();
		
		int n = Integer.parseInt(input);
		int k = Integer.parseInt(br.readLine());
		
		int light = 1;
		for(int i = 0; i < n; i++){
			if(light > k){
				light += k;
			}
			else {
				light *= 2;
			}
		}
		
		System.out.println(light);

	}

}


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

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

  bool cards[4][13] = {0};
  char marks[4] = { 'S', 'H', 'C', 'D' };

  for (int i = 0; i < n; i++) {
    char mark;
    int rank;
    cin >> mark >> rank;

    if (mark == 'S') {
      cards[0][rank - 1] = 1;
    } else if (mark == 'H') {
      cards[1][rank - 1] = 1;
    } else if (mark == 'C') {
      cards[2][rank - 1] = 1;
    } else if (mark == 'D') {
      cards[3][rank - 1] = 1;
    }
  }

  for (int p = 0; p < 4; p++) {
    for (int q = 0; q < 13; q++) {
      if (!cards[p][q]) cout << marks[p] << " " << q + 1 << endl;
    }
  }

  return 0;
}



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

using namespace std;

bool comp(pair<int,int> a, pair<int,int> b){
	return a.first < b.first;
}

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

	int n,t;
	cin >> n >> t;
	vector<pair<int,int>> v;
	for(int i=0; i<n; i++){
		int cost, time;
		cin >> cost >> time;
		v.push_back(make_pair(cost, time));
	}
	sort(v.begin(), v.end(), comp);
	for(auto x:v){
		if(x.second <= t){
			cout << x.first;
			return 0;
		}
	}
	cout << "TLE";
	return 0;
}

Measured memory_bytes: 3552
import numpy as np

d = int(input())

c = list(map(int, input().split()))

sd = np.zeros((d, 26), dtype=np.int)
for i in range(d):
  s = list(map(int, input().split()))
  s_array = np.array(s)
  sd[i, :] = s_array

pp = np.zeros(26, dtype=np.int)
  
for i in range(d):
  pp += c
  pp_max = np.argmax(pp)+1
  pp_max_val = np.max(pp)
  # print(np.sum(pp), pp_max, pp_max_val)
  sd_max = np.argmax(sd[i,:])+1
  sd_max_val = np.max(sd[i,:])
  # print(sd_max, sd_max_val)
  sorted_pp = np.sort(pp)
  if np.sum(pp[:13]) >= sd_max_val:
    t = pp_max
    pp[pp_max-1] = 0
  else:
    t = sd_max
  print(t)

Measured memory_bytes: 27424
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
//#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n, r;
    deque<int> d(50);
    stack<int> s, t;
    while (cin >> n >> r && n) {
        FOR(i, 0, n)d[i] = n - i;
        while (r--) {
            int p, c; cin >> p >> c;
            FOR(i, 0, p - 1) {
                s.push(d.front());
                d.pop_front();
            }
            FOR(i, 0, c) {
                t.push(d.front());
                d.pop_front();
            }
            while (!s.empty()) {
                d.push_front(s.top());
                s.pop();
            }
            while (!t.empty()) {
                d.push_front(t.top());
                t.pop();
            }
        }
        cout << d.front() << "\n";
    }
}


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

Measured memory_bytes: 3164
#include<iostream>
#include<vector>
#include<algorithm>
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

using namespace std;

int main(){
  int N, x;
  cin >> N >> x;
  if (x == 1 || x == 2 * N - 1) {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;
  
  vector<int> v;
  v.reserve(2 * N);
  REP(i, 2, 2 * N - 1) {
    if (i != N && i != x) v.push_back(i);
  }

  //  reverse(v.begin(), v.end());
  
  if (x > N) {
    cout << 1 << endl;
    REP (i, 0, v.size() / 2 + 1) {
      cout << v[i] << endl;
    }
    cout << 2 * N - 1 << endl;
    cout << x << endl;
    REP (i, v.size() / 2 + 1, v.size()) {
      cout << v[i] << endl;
    }
    cout << N << endl;
  } else if (x < N ) {
    cout << 2 * N - 1 << endl;
    REP (i, 0, v.size() / 2) {
      cout << v[i] << endl;
    }
    cout << x << endl;
    cout << 1 << endl;
    REP (i, v.size() / 2, v.size()) {
      cout << v[i] << endl;
    }
    cout << N << endl;
  } else {
    REP(i, 0, 2 * N - 1) {
      cout << i + 1 << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define ll long long
//#define cccgift
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
inline void read(T &x)
{
    static char ch;bool f=1;
    for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
    for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
}
template<typename T>
void print(T x)
{
    if (x<0) x=-x,putchar('-');
    if (x>9) print(x/10);
    putchar(x%10+48);
}
template<typename T>
inline void print(T x,char ap) {print(x);if (ap) putchar(ap);}
template<typename T>
inline void chkmax(T &x,const T &y) {x=x<y?y:x;}
template<typename T>
inline void chkmin(T &x,const T &y) {x=x<y?x:y;}
struct node{
	int x,y;
	ll val;
	bool operator <(const node &b)const {return val>b.val||(val==b.val&&x>b.x);}
} c[200001];
int n,a[200001],b[200001];
ll k;
inline bool check(ll x) {
	ll tot=0;
	for(res i=1;i<=n;++i) tot+=max(0ll,(ll)c[i].x-x/c[i].y);
	return tot<=k;
}
int main()
{
	read(n),read(k);
	for(res i=1;i<=n;++i) read(a[i]);
	for(res i=1;i<=n;++i) read(b[i]);
	sort(a+1,a+1+n),sort(b+1,b+1+n),reverse(b+1,b+1+n);
	for(res i=1;i<=n;++i) c[i].x=a[i],c[i].y=b[i],c[i].val=(ll)a[i]*b[i];
	sort(c+1,c+1+n);
	ll l=0,r=c[1].val,tot=r;
	while(l<=r) {
		ll mid=l+r>>1;
		if(check(mid)) tot=mid,r=mid-1;
		else l=mid+1;
	}
	print(tot,'\n');
	return 0;
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?), set tle
    * do something instead of nothing and stay organized
*/ 

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

int main() {
  long long a, b, k;
  cin >> a >> b >> k;
  if(a >= k) cout << a-k << " " << b;
  else if(a+b >= k) cout << 0 << " " << a+b-k;
  else cout << 0 << " " << 0;
}


Measured memory_bytes: 256
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long

typedef long long int64;
typedef vector<int> VI64;
typedef vector<pair<int,int>> VII64;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;

int32_t main()
{
	IOS;
	int T=1;
	//cin>>T;
	while(T--)
	{
		string s;
		cin>>s;
		int q,i;
		cin>>q;
		int xo=0;
		while(q--)
		{
			int tem;
			cin>>tem;
			if(tem==1)
			{
				xo^=1;
			}
			else
			{
				char c;
				cin>>tem>>c;
				if(tem==1)
				{
					if(xo)
					{
						s.push_back(c);
					}
					else
						s.insert(0,1,c);
				}
				else
				{
					if(!xo)
					{
						s.push_back(c);
					}
					else
						s.insert(0,1,c);
				}
			}
			
		}
		if(xo)
			reverse(ALL(s));
		cout<<s;
	}

	return 0;
}

Measured memory_bytes: 912
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf = 1<<16;
int N,x,y,z,need[100010],tot[20],ans,md[inf],all;
bool vis[inf];
int read()
{
	static int x;
	static char ch;
	x = 0;
	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';
	return x;
}
int length(int x)
{
	int len = 0; 
	while (x)
	{
		len += x & 1;
		x >>= 1;
	}
	return len;
}
int find(int now)
{
	if (!now) return 0;
	if (vis[now]) return md[now];
	vis[now] = true;
	int ret = 20,next;
	for (int i = 1;i<=15;++i)
	 if ((now >> i) & 1)
	  for (int j = 1;j<=15;++j)
	   if ((i!=j) && ((now>>j)&1))
	     {
	     	next = now ^ (1<<i) ^ (1<<j) ^ (1<<(i ^ j));
	     	if (length(next) < length(now)) ret = min(ret , find(next) + 1 + (~next >> (i ^ j) & 1));
		 }
	 return md[now] = ret;	
}
int main()
{
	N = read();
	for (int i = 1;i<N;++i)
	{
		x = read() + 1;
		y = read() + 1;
		z = read();
		need[x]^=z;need[y]^=z;
	}
	ans = 0;
	for (int i = 1;i<=N;++i) tot[need[i]]++;
	for (int i = 1;i<=15;++i) ans += tot[i] >> 1,all |= (tot[i] & 1) << i;
	ans += find(all);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 896
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=1050;
//ここまでテンプレ
int main(){
	int N;
	cin>>N;
	int six[100]={46656,7776,1296,216,36,6,1};
	int nine[100]={59049,6561,729,81,9};
	int ans=INF;
	for(int i=0;i<=N;i++){
		int temp=0;
		int M=i,L=N-i;
		for(int j=0;j<7;j++){
			temp+=M/six[j];
			M-=six[j]*(M/six[j]);
		}
		for(int j=0;j<5;j++){
			temp+=L/nine[j];
			L-=nine[j]*(L/nine[j]);
		}
		if(L)
			continue;
		ans=min(ans,temp);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

typedef struct directedGraph{
  int *vertex;
  int *next;
  int *start;
  int v,e;
  int pointer;
} graph;

graph* newGraph(const int v,const int e){
  graph *g=(graph *)malloc(sizeof(graph));
  g->vertex=(int *)calloc(e,sizeof(int));
  g->next=(int *)calloc(e,sizeof(int));
  g->start=(int *)calloc(v,sizeof(int));
  for(int i=0;i<v;i++) g->start[i]=-1;
  g->v=v;
  g->e=e;
  g->pointer=0;
  return g;
}

void freeGraph(graph *g){
  free(g->vertex);
  free(g->next);
  free(g->start);
  free(g);
  return;
}

void addEdge(graph *g,const int from,const int to){
  const int p=g->pointer;
  g->vertex[p]=to;
  g->next[p]=g->start[from];
  g->start[from]=p;
  g->pointer++;
  return;
}

typedef struct node{
  int t;
  int c;
} node;

#define POS(rad,v) ((rad)*n+(v))

void run(void){
  int n,m;
  scanf("%d%d",&n,&m);
  graph *g=newGraph(n,2*m);
  while(m--){
    int a,b;
    scanf("%d%d",&a,&b);
    a--;b--;
    addEdge(g,a,b);
    addEdge(g,b,a);
  }
  const int f=10;
  node *dp=(node *)calloc(n*(f+1),sizeof(node));
  int i;
  for(i=0;i<(f+1)*n;i++) dp[i]=(node){0,0};
  int q;
  scanf("%d",&q);
  for(i=1;i<=q;i++){
    int v,d,c;
    scanf("%d%d%d",&v,&d,&c);
    v--;
    dp[POS(d,v)]=(node){i,c};
  }
  for(i=f;i>0;i--){
    for(int v=0;v<n;v++){
      if(dp[POS(i-1,v)].t<dp[POS(i,v)].t) dp[POS(i-1,v)]=dp[POS(i,v)];
      for(int p=g->start[v];p!=-1;p=g->next[p]){
	int u=g->vertex[p];
	if(dp[POS(i-1,u)].t<dp[POS(i,v)].t){
	  dp[POS(i-1,u)]=dp[POS(i,v)];
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d\n",dp[POS(0,i)].c);
  }
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 11136
from collections import defaultdict
 
N = int(input())
raw_numbers = list(map(int, input().split()))
Q = int(input())
 
total = sum(raw_numbers)
 
numbers = defaultdict(int)
 
for num in raw_numbers:
    numbers[num] += 1

for i in range(Q):
    a, b = map(int, input().split())
    taken = numbers[a]
    total -= numbers[a]*a
    numbers[b] += numbers[a]
    numbers[a] = 0
    total += taken*b
    print(total)

Measured memory_bytes: 89616
import itertools

n = int(input())
a = list(map(int,input().split()))

s = sum(a)
ac = list(itertools.accumulate(a))
#print(ac)

ans = 10**20

for i in range(n-1):
  ans = min(ans,abs(ac[i]*2-s))
  
print(ans)  

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

typedef long long ll;

#define PB push_back
#define MP make_pair

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> c(1000001);
    for (int i = 0; i < n; ++i) {
        int ai; cin >> ai;
        ++c[ai];
    }
    int ans = 0;
    for (int i = 1; i < 1000001; ++i) {
        if (c[i] == 1) ++ans;
        if (c[i] == 0) continue;
        for (int j = i; j < 1000001; j += i) c[j] = 0;
    }
    cout << ans << "\n";
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* print new lines
*/

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

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

int main(){
    int H, W;
    int white = -1;
    string s;
    cin >> H >> W;
    vector<vector<int>> g(H+2, vector<int>(W+2, -1));
    for (int i = 1; i <= H; i++)
    {
        cin >> s;
        for (int j = 0; j < W; j++)
        {
            if(s[j] == '.') {
                g[i][j+1] = 0;
                white++;
            }
        }
    }
    
    vector<vector<int>> dist(H+2, vector<int>(W+2, -1));
    queue<pair<int, int>> que;
    dist[1][1] = 0;
    que.push(make_pair(1,1));

    while (!que.empty())
    {
        int y, x;
        tie(y, x) = que.front();
        que.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i], nx = x + dx[i];
            if(g[ny][nx] == -1) continue;
            if(dist[ny][nx] != -1) continue;
            dist[ny][nx] = dist[y][x] + 1;
            que.push(make_pair(ny, nx));
        }
    }
//    cout << white << dist[H][W] << endl;
    if(dist[H][W] == -1) cout << "-1" << endl;
    else cout << white - dist[H][W] << endl;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <climits>
#include <map>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

using Pair = pair<int, int>;
using lint = long long;

#define rep(i, n) for (int i = 0; i < (n); i++)

// const int mod = 1e9 + 7;
// const int mod = 998244353;

template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

int main(){
    int k;
    cin >> k;
    rep(i, k) cout << "ACL";
    cout << endl;
}



Measured memory_bytes: 3636
def resolve():
    n = int(input())
    c = [[0] * 10 for i in range(10)]
    for i in range(n+1):
        b = i % 10
        for j in range(6):
            if i//(10**(j+1)) == 0:
                a = i//(10**j)
                break
        c[a][b] += 1
    ans = 0
    for i in range(1,10):
        for j in range(1,10):
            ans += c[i][j] * c[j][i]
    print(ans)
resolve()

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

using namespace std;

typedef long long ll;
const ll mod = 1e9+7;
ll fact [1001];
ll dp[1005][1005];
ll N,A,B,C,D;

ll p(ll x, ll a) {
  ll res = 1;
  while(a > 0) {
    if(a & 1) res = x * res % mod;
    
    x = x * x % mod;

    a >>= 1;
    
  }
  return res % mod;
}

ll r_fact(ll x) {
  return p(x,mod-2);
}

ll get_P(ll n, int r) {
  return fact[n] * r_fact(fact[n-r]) % mod;
}

int main() {
  cin >> N >> A >> B >> C >> D;

  fact[0] = 1;
  for(int i = 1; i <= N; i++) {
    fact[i] = (fact[i-1] * i) % mod;
  }

  dp[A-1][0] = 1;
  for(int i = A; i <= B; i++) {
    for(int j = 0; j <= N; j++) dp[i][j] = dp[i-1][j];
    for(int k = C; k <= D; k++) {
      for(int j = i * k; j <= N; j++) {
	dp[i][j] = (dp[i][j] + (dp[i-1][j-i*k] * get_P(j,i*k) % mod) * r_fact(p(fact[i],k) * fact[k] % mod) % mod) % mod;
      }
    }
  }
  cout << dp[B][N] << endl;
}
  

  

  


Measured memory_bytes: 8064
#include<stdio.h>
int main(){
	int N,x,y,z,i;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d %d %d",&x,&y,&z);
		x = x*x;
		y = y*y;
		z = z*z;
		if(x>y&&x>z){
			if(x==(z+y))printf("YES\n");
			else printf("NO\n");
		}
		else if(y>z&&y>x){
			if(y==(x+z)) printf("YES\n");
			else printf("NO\n");
		}
		else {
			if(z==(x+y))printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}

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

int main(){
    int x[3000];
    int y[3000];

    int i;

    for(i=0;; i++){
        cin >> x[i] >> y[i];

        if(!x[i] && !y[i]) break;
    }

    for(i=0;; i++){
        if(!x[i] && !y[i]) break;
        if(x[i] <= y[i]){
            cout << x[i] << " " << y[i] << endl;
        }
        else{
            cout << y[i] << " " << x[i] << endl;
        }
    }
}


Measured memory_bytes: 3036
n=int(input())
l,r=[],[]
for i in range(n):
    x,y=map(int,input().split())
    l.append((x,y))
l.sort()
l.sort(key=lambda a: a[1],reverse=True)
for i in range(n):
    x,y=map(int,input().split())
    r.append((x,y))
r.sort()
ans=0
chk=[1]*n
for i in range(n):
    for j in range(n):
        if l[i][0]<r[j][0] and l[i][1]<r[j][1] and chk[j]:
            chk[j]=0
            ans+=1
            break
print(ans)


Measured memory_bytes: 39024
def accum(ary, k)
  num = ary.size
  ary_sum = Array.new(num, 0)
  ary_lim = num
  prev = 0
  for i in 0...num do
    curr = ary[i] + prev
    if curr > k && ary_lim == num
      ary_lim = i
    end
    ary_sum[i] = curr
    prev = curr
  end
  return [ary_sum, ary_lim]
end

n, m, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
a_sum, a_lim = accum(a, k)
b_sum, b_lim = accum(b, k)
#p a_sum, a_lim
#p b_sum, b_lim
max_count = b_lim
for i in 0...a_lim do
  r = k - a_sum[i]
  j = b_sum.bsearch_index { |x| x > r }
  j = b_lim if j.nil?
#  p j
  count = (i + 1) + j
  max_count = count if max_count < count
end
puts max_count


Measured memory_bytes: 44556
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


#define INF 1e9+7
#define LLINF 1e18+7
#define N 250000

const ll MOD=998244353;

main(){
    int h,w;cin>>h>>w;
    pii d={1,0},r={0,1};
    vector<pii> v;
    rep(i,w-1)v.pb(r);
    rep(i,h-1)v.pb(d);
    bool flag=true;
    vector<string> mat;
    rep(i,h){
        string s;cin>>s;
        mat.pb(s);
    }
    do{
        pii now={0,0};
        vector<string> tmp(h,string(w,'.'));
        tmp[0][0]='#';
        rep(i,h+w-2){
            now.first+=v[i].first;
            now.second+=v[i].second;
            tmp[now.first][now.second]='#';
        }
        if(mat==tmp){
            cout<<"Possible";return 0;
        }
    }while(next_permutation(all(v)));
    cout<<"Impossible";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main()
{
	int K, A, B;
	scanf("%d%d%d", &K, &A, &B);
	bool ok = false;
	for (int i = A; i <= B; i++) {
		if (i % K == 0) {
			ok = true;
			break;
		}
	}
	puts(ok ? "OK" : "NG");
	return 0;
}


Measured memory_bytes: 1648
#define _USE_MATH_DEFINES // for C++  
#include "bits/stdc++.h"
#define NUM ((long long)1000000007)
#define int long long

using namespace std;

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

    int a, b, tmp = 0, sub;
    cin >> a >> b;
    sub = b - a;
    for (size_t i = 1; i < sub; i++)
    {
        tmp += i;
    }
    cout << tmp - a << endl;
}

Measured memory_bytes: 256
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]
ans=0
inf=float("inf")
for i in range(h):
   for j in range(w):
      if S[i][j]!="#":
         dp=[[inf for _ in range(w)]for _ in range(h)]
         dp[i][j]=0
         que=deque([(i,j)])
         while que:
            si,sj=que.popleft()
            for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
               if 0<=ni<h and 0<=nj<w and S[ni][nj]!="#":
                  if dp[ni][nj]>dp[si][sj]+1:
                     dp[ni][nj]=dp[si][sj]+1
                     ans=max(ans,dp[si][sj]+1)
                     que.append((ni,nj))
print(ans)
                     

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

int main() {
	ll n;
	cin >> n;
	if(n % 2 == 0 || n % 5 == 0) {
		cout << -1 << endl;
	}
	else{
		ll a = 7, cnt = 1;
		while(true) {
			if(a % n == 0) {
				break;
			}
			cnt++;
			a = (a*10+7)%n;
		}
		cout << cnt << endl;
	}
}

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

int main(){
	char s[3];
  	cin>>s;
  	int flag[2]={0};
  	for(int i=0;i<3;i++){
    	if(s[i]=='A') flag[0]=1;
      	else if(s[i]=='B') flag[1]=1;
    }
  
  	if(flag[0]==1 && flag[1]==1){
    	cout<<"Yes"<<endl;
    }else{
    	cout<<"No"<<endl;
    }
}

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

struct unionFind
{
  vector<int> d; // 根： 木のサイズ x -1, それ以外： 親のID
  unionFind(int n = 0) : d(n, -1) {}
  int find(int x)
  {
    if (d[x] < 0)
      return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y)
  {
    // root化しておく
    x = find(x);
    y = find(y);
    if (x == y)
      return false;

    // x を y に unite
    // d[x] のほうが多きい（=サイズが小さい）場合はswap
    if (d[x] > d[y])
      swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -d[find(x)]; }
};

int deg[100005];
vector<int> to[100005];

int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  unionFind uf(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    deg[a]++;
    deg[b]++;
    uf.unite(a, b);
  }
  rep(i,k) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    if (uf.same(a, b)) {
      deg[a]++;
      deg[b]++;
    }
  }
  rep(i,n) {
    int ans = uf.size(i) - 1 - deg[i];
    cout << ans << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 3968
#include <stdio.h>



int main (){

    // int num[9] = {1,2,3,4,5,6,7,8,9};
    int input;
    int flag = 0;
    scanf("%d", &input);

    for(int i = 1; i <= 9; i++){
        for (int j = 1; j <= 9 ; j++){
            // int temp = i*j;
            if (input == (i*j)){
                flag = 1;
               break;
            }
        }
    }

    if (flag == 1){
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 1632
#include <stdio.h>

#define MAX 100005
#define NIL -1

typedef struct { int p, l, r;} Node;

Node T[MAX];
int n, D[MAX];

void print(int u) {
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if( T[u].p == NIL ) printf("root, ");
  else if( T[u].l == NIL ) printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i=0, c=T[u].l; c != NIL; i++, c=T[c].r) {
    if(i) printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

void rec(int u, int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}

int main(void) {
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0;i<n;i++) {
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++) {
      scanf("%d",&c);
      if(j==0) T[v].l=c;
      else T[l].r =c;
      l = c;
      T[c].p = v;
    }
  }
  for(i=0;i<n;i++) {
    if(T[i].p == NIL) r = i;
  }
  
  rec(r,0);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}


Measured memory_bytes: 6384
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
// typedef int128_t ll;
// typedef cpp_int ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

// #define NDEBUG 1
// debug用出力 https://trap.jp/post/998/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T)
{
    cerr << H << " ";
    debug_out(T...);
}
#ifdef NDEBUG
#define debug(...)
#else
#define debug(...) debug_out(__VA_ARGS__)
#endif

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

// 別の書き方を使ってみる

// constexpr inline ll mod = 1'000'000'007;
constexpr int max_n = 200'000 + 5;

int n, q;
int cnts[max_n];

int hd[max_n]; // n : 頂点数
int nxt[2*max_n], to[2*max_n]; // 2*(n-1)+1 : 辺の個数+1
int edge_cnt;
inline void add_edge(int u, int v) { // u to v
    edge_cnt++; // 辺が1つ増える
    to[edge_cnt] = v; // edge_cnt本目の辺の行き先はv
    nxt[edge_cnt] = hd[u]; // edge_cnt本目の辺の次に見る(uから出る)辺は、はじめに見ていた(uから出る)辺であるhd[u]本目の辺
    hd[u] = edge_cnt; // 新しくはじめに見る(uから出る)辺はedge_cnt本目の辺
}

void dfs(const int cur = 0, const int parent = -1, const int cnt = 0)
{
    cnts[cur] += cnt;
    for (int e = hd[cur]; e > 0; e = nxt[e]) {
       const int child = to[e];
       if (child == parent) { continue; }
       dfs(child, cur, cnts[cur]);
   }
}

int main()
{
    // 入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        add_edge(a,b);
        add_edge(b,a);
    }
    rep(j, q)
    {
        int p,x;
        cin >> p >> x;
        p--;
        cnts[p] += x;
    }

    // 集計
    dfs();

    rep(i, n)
    {
        cout << cnts[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 23928
#include <bits/stdc++.h>
using namespace std;
int a[114514];
int main()
{
	int n, cnt = 0;
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &a[i]);
	for(int i=1; i<=n; i+=2)
		if(a[i] % 2)
			cnt++;
	printf("%d", cnt);
	return 0;
}


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

uint xor128(){
	static uint x=123456789;
	static uint y=333333333;
	static uint z=555555555;
	static uint w=88888888;
	uint t=x^(x<<11);
	x=y;y=z;z=w;
	return w=(w^(w>>19))^(t^(t>>8));
}
struct node{
	node*l,*r;
	int cnt,val,Min;
};
node pool[400000];
int p;

inline int cnt(node*t){return t?t->cnt:0;}
inline int Min(node*t){return t?t->Min:INF;}

inline node*update(node*t){
	t->cnt=cnt(t->l)+cnt(t->r)+1;
	t->Min=min({t->val,Min(t->l),Min(t->r)});
	return t;
}
inline node*merge(node*l,node*r){
	if(!l)return r;
	if(!r)return l;
	if(xor128()%(cnt(l)+cnt(r))<(uint)cnt(l)){
		l->r=merge(l->r,r);
		return update(l);
	}
	else{
		r->l=merge(l,r->l);
		return update(r);
	}
}
inline pair<node*,node*>split(node*t,int k){
	if(!t)return make_pair((node*)NULL,(node*)NULL);
	if(k<=cnt(t->l)){
		auto p=split(t->l,k);
		t->l=p.second;
		return make_pair(p.first,update(t));
	}
	else{
		auto p=split(t->r,k-cnt(t->l)-1);
		t->r=p.first;
		return make_pair(update(t),p.second);
	}
}

int main(){
	int n,q;scanf("%d%d",&n,&q);
	node*root=NULL;
	rep(i,n){
		int a;scanf("%d",&a);
		node*t=&pool[p++];
		*t={NULL,NULL,1,a,a};
		root=merge(root,t);
	}
	rep(i,q){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		if(x==0){
			z++;
			auto a=split(root,y);
			auto b=split(a.second,z-y-1);
			auto c=split(b.second,1);
			root=merge(merge(merge(a.first,c.first),b.first),c.second);
		}
		else if(x==1){
			z++;
			auto a=split(root,y);
			auto b=split(a.second,z-y);
			printf("%d\n",Min(b.first));
			root=merge(merge(a.first,b.first),b.second);
		}
		else{
			auto a=split(root,y);
			auto b=split(a.second,1);
			b.first->val=b.first->Min=z;
			root=merge(merge(a.first,b.first),b.second);
		}
	}
}


Measured memory_bytes: 9492
import math
a, b, h, m = map(int, input().split())

t = 60 * h + m
hr = t / 2
mr = m * 6

r = math.radians(abs(hr - mr))
c = a * a + b * b - 2 * a * b * math.cos(r)
print(math.sqrt(c))

Measured memory_bytes: 9504
from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

n,k=map(int,input().split())
mod=10**9+7
ans=[n-k+1]
for i in range(2,k+1):
        if n-k+1<i:
                ans.append(0)
        else:
                k_sep=(combinations_count(k-1,i-1))%mod
                if n-k==i-1:
                        l_sep=1
                elif n-k==i:
                        l_sep=n-k+1
                else:
                        l_sep=(combinations_count(n-k-1,i-2)+2*combinations_count(n-k-1,i-1)+combinations_count(n-k-1,i))%mod
                ans.append((k_sep*l_sep)%mod)
for ii in range(k):
        print(ans[ii])

Measured memory_bytes: 3444
#include <iostream>
#include <map>

using namespace std;

long long len, total = 0;
string s;
map<long long, long long> m;
int main() {
    cin >> s;
    len = s.length();
    for (long long i = 0; i < len; i++) {
        long long num = s[i]+0;
        m[num]++;
    }
    for (long long i = 0; i < 26; i++) {
        if (m[i+97] > 1) {
            total += (m[i+97]*(m[i+97]-1))/2;
        }
    }
    long long comb = (len*(len-1))/2;
    long long result = comb - total + 1;
    cout << result;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A= sc.nextInt(),B=sc.nextInt();
		int Amin= A*100/8, Amax=(A+1)*100/8,Bmin= B*100/10, Bmax=(B+1)*100/10;
		if(A%2==1) {
			Amin+=1;
		}
		int ans = -1;
		for(int i=Amin;i<Amax;i++) {
			if(Bmin<=i&&Bmax>i) {
				ans = i;
				break;
			}
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 23892
H,W,K = map(int,input().split())
s = [list(input()) for _ in range(H)]
import numpy as np
ans = np.array([[0]*W]*H)
k=1
for i,m in enumerate(s):
  l=0
  for j,n in enumerate(m):
    if n == '#':
      ans[i,j-l:j+1]=k
      k+=1
      
ans = np.maximum.accumulate(ans,axis=1)

for i,m in enumerate(ans):
  l=1
  for j,n in enumerate(m):
    if n!=0:
      ans[i,0:l]=n
      break
    else:
      l+=1
      
ans = np.maximum.accumulate(ans,axis=0)
l=0
for h in range(H):
  x = np.any(ans[h,:]==0)
  if x:
    l+=1
  else:
    ans[0:l,:]=ans[h,:]
    break
    
ans = list(ans)
for i in ans:
  print(' '.join(i.astype(str)))

Measured memory_bytes: 15204
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

int main(void) {
	string L;
	cin >> L;

	int N = L.size();
	vector<vector<ll>> dp(N + 1, vector<ll>(2));

	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <=1 ; j++) {
			if (j == 1) {
				dp[i + 1][j] += 3*dp[i][j];
				dp[i + 1][j] %= DIV;
			}
			else {
				if (L[i] == '1') {
					dp[i + 1][0] += 2*dp[i][j];
					dp[i + 1][0] %= DIV;
					dp[i + 1][1] += dp[i][j];
					dp[i + 1][1] %= DIV;
				}
				else {
					dp[i + 1][j] += dp[i][j];
					dp[i + 1][j] %= DIV;
				}
			}
		}
	}

	cout << (dp[N][0] + dp[N][1])%DIV << endl;
}


Measured memory_bytes: 5760
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

long long ai[100];

void sort(long long* N, long long len)
{
    long long i,j;

    for(i=0; i<len; i++)
    {
        for(j=len-1; j>i; j--)
        {
            if(N[j] < N[j-1])
            {
                long long ti;
                long long temp = N[j];
                N[j]   = N[j-1];
                N[j-1] = temp;

                ti = ai[j];
                ai[j] = ai[j-1];
                ai[j-1] = ti;
            }
        }
    }
}

int main(int argc, void **arg)
{
    long long n;
    char s[101][16];
    long long p[101];

    scanf("%lld", &n);

    for (long long i = 0; i < n; i++)
    {
        scanf("%s %lld", s[i], &p[i]);
    }
    s[100][0] = '\0';
    p[100] = 0;

    for (long long i = 0; i < n; i++)
    {
        long long x = n + 1;
        char smin = 0x7F;

        for (long long i = 0; i < n; i++)
        {
            int cmp; 
            if( s[i][0] == '\0' ) continue;
            if( x == n + 1 ) {
                x = i;
                continue;
            }

            cmp = strcmp(s[i], s[x]);
            if( cmp == 0 ) {
                if( p[x] < p[i] )
                    x = i;
            }
            else if( cmp < 0 )
            {
                x = i;
            }
        }

        printf("%lld\n", x + 1);
        s[x][0] = '\0';
    }

    return 0;
}


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

int n;
vector<__int128_t> s, t;

void init() {
  map<__int128_t, __int128_t> mp;
  vector<__int128_t> prime;
  bool f[101010];
  memset(f, true, sizeof f);

  f[0] = f[1] = false;
  for (int i = 2; i <= 100000; ++i) {
    if (f[i]) {
      if (i < 2200) prime.push_back(i);
      mp[(int64_t)i * i] = i;
      for (int j = 2 * i; j <= 100000; j += i) {
        f[j] = false;
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    int64_t m;
    cin >> m;

    __int128_t a, b;
    a = b = 1;

    for (auto &p : prime) {
      int cnt = 0;
      while (m % p == 0) {
        ++cnt;
        m /= p;
      }

      cnt %= 3;
      for (int j = 0; j < cnt; ++j) a *= p;
      for (int j = (3 - cnt) % 3; j > 0; --j) b *= p;
    }

    if (mp.count(m)) {
      a *= mp[m];
      b *= m;
    } else {
      a *= (__int128_t)m * m;
      b *= m;
    }

    s.push_back(a);
    t.push_back(b);
  }
}

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

  map<__int128_t, int> mp;
  map<__int128_t, __int128_t> po;
  for (int i = 0; i < n; ++i) {
    mp[s[i]]++;
    po[s[i]] = t[i];
  }

  int ans = n;
  for (auto &i : mp) {
    if (i.first == 1) {
      ans -= i.second - 1;
      continue;
    }

    __int128_t uku = po[i.first];
    if (mp.count(uku) && uku < i.first) {
      ans -= min(mp[uku], i.second);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 19580
#include <stdio.h>
#include <stdlib.h>

#define INIT_CAP 10
#define INF 1000000000

inline int nextInt(void) {
	int ch;
	int sign, x;

	do {
		ch = getchar();
	} while (ch < '-');

	if (ch == '-') {
		sign = -1;
		ch = getchar();
	} else
		sign = 1;

	x = 0;
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}

	return sign * x;
}

inline void printInt(int x) {
	char ch[10];
	int cnt;

	if (x < 0) {
		putchar('-');
		x = -x;
	}

	cnt = 0;
	do {
		ch[cnt++] = '0' + x % 10;
		x /= 10;
	} while (x);

	while (cnt--)
		putchar(ch[cnt]);
}

typedef struct {
	int to, w;
} Edge;

typedef struct {
	Edge *elem;
	int cap, size;
} VecEdge;

typedef struct {
	int num, d;
} PNumDis;

VecEdge adj[10000];
PNumDis heap[500000];
int hsize;
int d[10000];

void init(int n) {
	while (n--)
		adj[n] = (VecEdge){malloc(sizeof(Edge) * INIT_CAP), INIT_CAP, 0};
}

inline void add(int from, int to, int w) {
	if (adj[from].size == adj[from].cap) {
		adj[from].cap <<= 1;
		adj[from].elem = realloc(adj[from].elem, sizeof(Edge) * adj[from].cap);
	}
	adj[from].elem[adj[from].size++] = (Edge){to, w};
}

inline void insert(int num, int d) {
	int i;
	for (i = hsize++; i > 0 && d < heap[i - 1 >> 1].d; i = i - 1 >> 1)
		heap[i] = heap[i - 1 >> 1];
	heap[i] = (PNumDis){num, d};
}

inline int calcNextIdx(int i) {
	return i * 2 + 1 + (i * 2 + 2 < hsize && heap[i * 2 + 1].d > heap[i * 2 + 2].d);
}

inline PNumDis delete(void) {
	int i;
	int nextIdx;
	const PNumDis root = heap[0], last = heap[--hsize];

	for (i = 0; i * 2 + 1 < hsize && last.d > heap[nextIdx = calcNextIdx(i)].d; i = nextIdx)
		heap[i] = heap[nextIdx];
	heap[i] = last;

	return root;
}

void dijkstra(int n, int s) {
	int i;

	for (i = 0; i < n; i++)
		d[i] = INF;

	d[s] = 0;
	insert(s, 0);
	while (hsize > 0) {
		const PNumDis fromP = delete();

		if (fromP.d > d[fromP.num])
			continue;

		for (i = 0; i < adj[fromP.num].size; i++) {
			const Edge e = adj[fromP.num].elem[i];
			if (fromP.d + e.w < d[e.to]) {
				d[e.to] = fromP.d + e.w;
				insert(e.to, d[e.to]);
			}
		}
	}
}

int main(void) {
	int i;
	int n;

	scanf("%d", &n);

	init(n);
	for (i = 0; i < n; i++) {
		int u = nextInt(), k = nextInt();
		while (k--) {
			int v = nextInt(), c = nextInt();
			add(u, v, c);
		}
	}

	dijkstra(n, 0);

	for (i = 0; i < n; i++) {
		printInt(i);
		putchar(' ');
		printInt(d[i]);
		putchar('\n');
	}

	return 0;
}

Measured memory_bytes: 5652
h,w=map(int,input().split())
A=[['.']*(w+2)]
for i in range(h):
    s=list(input())
    A.append(['.']+s+['.'])
A.append(['.']*(w+2))
for i in range(2,h+1):
    for j in range(2,w+1):
        if A[i][j]=='#' and A[i-1][j]=='.' and A[i+1][j]=='.' and A[i][j-1]=='.' and A[i][j+1]=='.':
            print('No')
            exit()
print('Yes')

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

bool compare(pair<string, int> a, pair<string, int> b) {
    if(a.first != b.first) {
        return a.first < b.first;
    }
    if(a.second != b.second) {
        return a.second > b.second;
    }else{
        return true;
    }
}

int main() {
    int n;
    cin>>n;
    vector<pair<string, int>> sp(n);
    int a[n];
    for(int i=0;i<n;i++) cin>>sp.at(i).first>>sp.at(i).second;
    for(int i=0;i<n;i++) a[i]=sp.at(i).second;
    sort(sp.begin(), sp.end(), compare);
  	//for(int i=0;i<n;i++) i!=n-1? cout<<a[i]<<' ': cout<<a[i]<<endl;
  	//for(int i=0;i<n;i++) i!=n-1? cout<<sp.at(i).second<<' ': cout<<sp.at(i).second<<endl;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(sp.at(i).second==a[j]) cout<<j+1<<endl;
        }
    }
}


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

int fac(int N);

int main()
{
    int N;
    cin >> N;
    long double ans = 0;
    vector<int> x(N), y(N), route(N);
    rep(i, N)
    {
        cin >> x.at(i) >> y.at(i);
        route.at(i) = i;
    }
    int f = fac(N);
    rep(i, f)
    {
        rep(j, N - 1)
        {
            int a1 = route.at(j);
            int a2 = route.at(j + 1);
            long double diff_x = x.at(a1) - x.at(a2);
            long double diff_y = y.at(a1) - y.at(a2);
            long double d = sqrt(diff_x * diff_x + diff_y * diff_y);
            ans += d;
        }
        next_permutation(all(route));
    }
    cout << fixed << setprecision(15) << ans / f << endl;
}

int fac(int N)
{
    if (N == 0)
    {
        return 1;
    }
    return N * fac(N - 1);
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]
B = [0] * N
ans = []
for i in range(N, 0, -1):
    y = 1
    x = i * y
    s = 0
    while x <= N:
        s += B[x-1]
        y += 1
        x = i * y
    if s % 2 != A[i-1]:
        B[i-1] = 1
        ans.append(i)

M = sum(B)
ans = map(str, ans)
ans = " ".join(ans)

print(M)
print(ans)

Measured memory_bytes: 18960
M=10**9+7
n=int(input())
a=list(map(int, input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,n):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Measured memory_bytes: 5612
from itertools import takewhile
from functools import reduce


def gen_prime_candidates():
    yield 2
    yield 3
    n = 0
    while 1:
        yield n + 5
        yield n + 7
        n += 6


def calc_exp(n, p):
    e = 0
    while n % p == 0:
        e += 1
        n /= p
    return e, n


def factorize(n):
    f = ()
    for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):
        e, n = calc_exp(n, p)
        if e:
            f += (p, )
    if n > 1:
        f += (n, )
    return f


def phi(n):
    return reduce(lambda x, p: x * (p-1) / p, factorize(n), n)


n = int(input())
print(int(phi(n)))



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

int main(){
	ll n,k;
	string s;
	cin>>n>>k;
	cin>>s;
	ll z[n+1],j=0,res=0,sum=0;
	memset(z,0,sizeof(z));
	ll a=0,cnt=k;
	ll right=0,left=0;
	while(right<n){
		while(right<n&&s[right]=='1')right++;
		res = max(res,right-left);
		while(right<n&&s[right]=='0')right++;
		k--;
		if(k<0){
			while(left<n&&s[left]=='1')left++;
			while(left<n&&s[left]=='0')left++;
		}
		res=max(res,right-left);
	}

	cout<<res<<endl;
}


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

using namespace std;

int main()
{
    int X,a,b,c;
    cin>>X;
    a=X/100;
    for(int i=0;i<=a;i++){
            if(100*a<=X&&100*a+5*a>=X){
            cout<<1<<endl;
            exit(0);
        }   
    }
    cout<<0<<endl;
}

Measured memory_bytes: 256
def solve():
    N = int(raw_input())
    A = [int(_) for _ in raw_input().split()]
    A.sort()
    ret = abs(A[N-1] - A[0])
    rever = [0] * (N - 1)
    for i in range(1, N-1):
        if A[i] >= 0:
            ret = ret + A[i]
            rever[i-1] = 1
        else:
            ret = ret - A[i]
    print ret
    def PrintAndCalcSave(a, b, rever):
        if rever == 0:
            print a, b
            return a - b
        else:
            print b, a
            return b - a

    cnt = 0
    if A[N-1] > A[0]:
        save = PrintAndCalcSave(A[N-1], A[0], rever[cnt])
    else:
        save = PrintAndCalcSave(A[0], A[N-1], rever[cnt])
    cnt += 1
    for i in range(1, N - 1):
        if A[i] >= 0:
            save = PrintAndCalcSave(A[i], save, rever[cnt])
        else:
            save = PrintAndCalcSave(save, A[i], rever[cnt])
        cnt += 1

if __name__ == '__main__':
    solve()


Measured memory_bytes: 42612
unittest
{
	assert( [ "30 100" ].parse.expand.solve == 100 );
	assert( [ "12 100" ].parse.expand.solve == 50 );
	assert( [ "0 100" ].parse.expand.solve == 0 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ab = input.front.split.to!( long[] );
	return tuple( ab[ 0 ], ab[ 1 ] );
}

auto solve( long a, long b )
{
	if( 13 <= a ) return b;
	if( 6  <= a ) return b / 2;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<functional>
#include<string>
using namespace std;

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

int main(){
	char in[10],fld[3][3];
	while(cin>>in){
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				fld[i][j] = in[i*3+j];
			}
		}
		bool wo=false,wx=false;
		for(int y=0;y<3;y++){
			for(int x=0;x<3;x++){
				for(int i=0;i<8;i++){
					int co=0,cx=0;
					for(int j=0;;j++){
						int ny = y+dy[i]*j,
							nx = x+dx[i]*j;
						if(ny<0 || 3<=ny || nx<0 || 3<=nx) break;
						if(fld[ny][nx]=='o') co++;
						else if(fld[ny][nx]=='x') cx++;
					}
					if(co==3) wo=true;
					else if(cx==3) wx=true;
				}
			}
		}
		if(wo) puts("o");
		else if(wx) puts("x");
		else puts("d");
	}
    return 0;
}

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

int main() {
  string s, t;
  cin >> s;
  cin >> t;
  int count = 0; 
  
  for (int i = 0; i < 3; i++) {
    if (s.at(i) == t.at(i)){
      count += 1;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,x;cin >> n >> x;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    ll ans=0;
    if(a[0]>x){
        ans+=a[0]-x;
        a[0]=x;
    }
    FOR(i,1,n){
        if(a[i-1]+a[i]>x){
            ans+=a[i-1]+a[i]-x;
            a[i]-=a[i-1]+a[i]-x;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3956