akhauriyash/Code-Regression huggingface dataset:
#include <string>
#include <algorithm>
#include <queue>
#include <iostream>
#include <stdio.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

int h,w;
char a[1000][1000];
int d[1000][1000]={};
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
queue<P> que;
int dmax=0;

void bfs(){
  while (que.size()){
    P p = que.front(); que.pop();
    for (int i =0;i<4;i++){
      int nx = p.first + dx[i],ny=p.second + dy[i];
      if (0 <= nx && nx < h && 0 <= ny && ny < w && a[nx][ny] == '.' && d[nx][ny] == 0){
	d[nx][ny] = d[p.first][p.second] + 1;
	que.push(P(nx,ny));
      }
    }
  }
  return ;
}

int main(){
  cin >> h >> w;
  for (int i =0;i<h;i++){
    for (int j =0;j<w;j++){
      cin >> a[i][j];
      if (a[i][j] == '#'){
      	que.push(P(i,j));
      }
    }
  }
  bfs();
  for (int i = 0;i<h;i++){
    for (int j = 0;j<w;j++){
      dmax = max(d[i][j],dmax);
    }
  }
  cout << dmax << endl;
}


Measured memory_bytes: 11280
n,*a=map(int,open(0).read().split())

c=0
left=0
right=n
def merge(A,left,mid,right):
    global c
    L=A[left:mid]+[float("inf")]
    R=A[mid:right]+[float("inf")]
    i=0
    j=0
    for r in range(left,right):
        if L[j]>R[i]:
            c+=1
            A[r]=R[i]
            i+=1
        else:
            c+=1
            A[r]=L[j]
            j+=1

def mergesort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergesort(A,left,mid)
        mergesort(A,mid,right)
        merge(A,left,mid,right)
        
mergesort(a,left,right)

print(*a)
print(c)


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

int main(){
    int N;
    cin >> N;
    vector<int> B(N-1);
    for(int i=0; i < N-1; i++){
        cin >> B.at(i);
    }
    int ans = B.at(0);
    for(int i = 0; i < N-2; i++){
        ans += min(B.at(i), B.at(i+1));
    }
    ans += B.at(N-2);
    cout << ans << endl;
}

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

int main() {
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i=0; i<K; i++){
    int x;
    cin >> x;
    for(int j=0; j<x; j++){
      int y;
      cin >> y;
      A.at(y-1)=1;
    }
  }
  int ans = 0;
  for (int i=0; i<N; i++){
    ans += A.at(i);
  }
  cout << N - ans << endl;
}


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

int f(long long a, long long b, long long x){
  long long s = a*x/b;
  long long t = a*(x/b);
  return s-t;
}
int main(){
  long long a, b, n;
  cin >> a >> b >> n;
  long long ans=0;
  if(b>n){
    ans = f(a,b,n);
  }else{
    ans = f(a,b,b-1);
    }
  cout << ans << endl;
}

Measured memory_bytes: 3524
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<vector<int>> G;

int subtree(int v){
    vector<int> a;
    for(auto nv : G[v]){
        a.push_back(subtree(nv));
    }
    int res = 0;
    sort(a.rbegin(), a.rend());
    rep(i,a.size()){
        chmax(res, a[i] + i + 1);
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    G.resize(n);
    rep(i,n-1){
        int a;
        cin >> a;
        --a;
        G[a].push_back(i+1);
    }
    cout << subtree(0) << endl;
    return 0;
}


Measured memory_bytes: 17932
H, W, M = list(map(int, input().split()))
HW = set(tuple(int(x) - 1 for x in input().split()) for _ in range(M))
h = [0] * H
w = [0] * W
for hi, wi in HW:
	h[hi] += 1
	w[wi] += 1
hm = max(h)
wm = max(w)

hh = [i for i, v in enumerate(h) if v == hm]
ww = [i for i, v in enumerate(w) if v == wm]

ans = hm + wm - 1
for h in hh:
	for w in ww:
		if (h, w) not in HW:
			ans += 1
			break 	
	else:
		continue
	break
print(ans)


Measured memory_bytes: 83464
import math
import itertools


def distance(start, end):
    return math.sqrt(sum((x - y) ** 2 for x, y in zip(start, end)))


N, D = map(int, input().split())
Xs = []
for _ in range(N):
    Xs.append(list(map(int, input().split())))

ans = 0
for p, q in itertools.combinations(Xs, 2):
    d = distance(p, q)
    if math.floor(d) == math.ceil(d):
        ans += 1
print(ans)


Measured memory_bytes: 3064
#

import sys
input=sys.stdin.readline

def main():
    K=int(input())
    lunlun=[1,2,3,4,5,6,7,8,9]
    ind=0
    lll=9
    for dig in range(12):
        l=lll
        for i in lunlun[ind:]:
            s=str(i)
            x=int(s[dig])
            if 0<=x-1<=9:
                lunlun+=[int(s+str(x-1))]
                lll+=1
            if 0<=x<=9:
                lunlun+=[int(s+str(x))]
                lll+=1
            if 0<=x+1<=9:
                lunlun+=[int(s+str(x+1))]
                lll+=1
            if lll>K:
                break
        ind=l
    lunlun.sort()
    print(lunlun[K-1])
    
    
if __name__=="__main__":
    main()


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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

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

    int r0, w0, c, r;
    while (cin >> r0 >> w0 >> c >> r, r0) {
        rep(x, 100000) {
            double y = 1. * (r0 + x * r - c * w0) / c;
            if (y >= 0) {
                cout << x << endl;
                break;
            }
        }
    }
}

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

using namespace std;


int H, W;
string S[12];
clock_t start;
vector< int > v;

int cmp(int a, int b) {
  for(int i = 0; i < W; i++) {
    if(S[a][v[i]] != S[b][v[W - 1 - i]]) return false;
  }
  return true;
}

bool rec() {
  vector< int > used(H);
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < i; j++) {
      if(used[j]) continue;
      if(cmp(i, j)) {
        used[i] = true;
        used[j] = true;
        break;
      }
    }
  }
  for(int i = 0; i < H; i++) {
    if(used[i]) continue;
    if(cmp(i, i)) {
      used[i] = true;
      break;
    }
  }
  return count(begin(used), end(used), 0) == 0;
}


int main() {
  start = clock();
  cin >> H >> W;
  v.resize(W);
  iota(begin(v), end(v), 0);
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }
  mt19937 mt(1333);
  while(clock() - start < 1.95 * CLOCKS_PER_SEC) {
    shuffle(begin(v), end(v), mt);
    if(rec()) {
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define ll long long
#define ull unsigned long long
#define vi vector<int>

const double PI = 3.14159265358979323846;

ll gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

int main() {
    int N;
    cin >> N;
    string S;
    set<string> s;
    rep(i, N) {
        cin >> S;
        s.insert(S);
    }
    cout << s.size() << endl;
}


Measured memory_bytes: 19180
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using vb = vector<bool>;
using boolGraph = vector<vb>;
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;

vl fac, finv, inv;

void com_init(const int MAX) {
  fac.resize(MAX);  fac[0] = fac[1] = 1;
  finv.resize(MAX); finv[0] = finv[1] = 1;
  inv.resize(MAX);  inv[1] = 1;
  for (int i=2; i<MAX; ++i) {
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;
  }
}

ll combination(int n, int r) {
  if (n < r) return 0;
  if (n < 0 || r < 0) return 0;
  return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD;
}

void solve() {
  int x, y; cin >> x >> y;

  if ((x+y)%3 != 0) {
    cout << 0 << endl;
    return;
  }

  int move = (x+y) / 3;

  com_init(move + 1);

  int counter = x - move;

  cout << combination(move, counter) << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  return 0;
}


Measured memory_bytes: 15872
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
using namespace std;

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

    string dp[110];

    dp[4]=dp[7]="Yes";
    dp[1]=dp[2]=dp[3]=dp[5]=dp[6]="No";

    for(int i=8;i<110;i++){
        if(dp[i-4]=="Yes"||dp[i-7]=="Yes")dp[i]="Yes";
        else dp[i]="No";
    }

    cout<<dp[N]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	int n;
	cin >> n;
	cout << (n - 1) / 2 << endl;

	return 0;
}


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

int main(void){
    
    int N,len;
    cin >> N;
    len =N * 0.9;
    
    for(int i=len;i<=N;i++){
        if((int)(i* 1.08) == N){
            cout << i <<endl;
            break;
        }
       
       if(i == N) cout << ":(" <<endl;
    }
    
}

Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    
    
    int cost = 0;
    int xy = min(x,y);
    if(a*xy+b*xy > c*2*xy){
        cost+=c*2*xy;
    }
    else{
        cost+=a*xy+b*xy;
    }
    x-=xy;
    y-=xy;
    // cout << x << " " <<y << endl;
    if(a*x > c*2*x){
        cost+= c*2*x;
    }
    else{
        cost+= a*x;
    }
    if(b*y > c*2*y){
        cost+= c*2*y;
    }
    else{
        cost+= b*y;
    }
    cout << cost << endl;
    return 0;
}

Measured memory_bytes: 888
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	int a[3];

	for (int i = 0; i < 3; i++)
	{
		scanf("%d", &a[i]);
	}

	for (int i = 0; i < 3; i++)
	{
		if (a[i] == a[(i + 1) % 3] && a[(i + 1) % 3] != a[(i + 2) % 3])
		{
			printf("Yes\n");

			return 0;
		}
	}

	printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <iostream>

using namespace std;

int main(){
    double r;
    double area,line;
    
    cin >> r;
    
    area = r*r*3.141592653589;
    line = 2.0*r*3.141592653589;
    
    printf("%6f %6f",area,line);
    
    return 0;
}


Measured memory_bytes: 3196
//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007 
#define MAXN 1000005

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N; cin>>N;
    vector<pair<ll,ll>> v;
    
    for(ll i=0;i<N;++i)
    {
        ll x,y; cin>>x>>y;
        v.push_back({x,y});
    }
    
    sort(v.begin(),v.end());
    ll mn1 = v[0].first - v[0].second;
    ll mn2 = v[0].first + v[0].second;
    ll ans = LLONG_MIN;
    
    for(ll i=1;i<N;++i)
    {
        ll one = v[i].first - v[i].second;
        ll two = v[i].first + v[i].second;
        
        ans = max(ans,one - mn1);
        ans = max(ans,two - mn2);
        mn1 = min(mn1,one);
        mn2 = min(mn2,two);
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 7400
#include <cstdio>
#include <algorithm>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

constexpr int MAX_N = 100000;

int N, M;
int ball[MAX_N];
bool fl[MAX_N];

int main()
{
  scanf( "%d%d", &N, &M );

  fl[0] = true;
  std::fill( ball, ball+N, 1 );

  rep( i, M )
  {
    int x, y;
    scanf( "%d%d", &x, &y );
    --x; --y;
    if( fl[x] )
      fl[y] = true;
    --ball[x]; ++ball[y];

    if( !ball[x] )
      fl[x] = false;
  }

  int ans = 0;
  rep( i, N ) if( fl[i] )
    ++ans;

  printf( "%d\n", ans );

  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 k = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		if (a <= b / k * k) {
			System.out.println("OK");
		} else {
			System.out.println("NG");
		}

		sc.close();
	}

}


Measured memory_bytes: 35716
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _dbg(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _dbg(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_dbg(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const int N=1e5+1;
int a[N];
int32_t main(){
    int n;
    cin>>n;
    map<int,int> m;
    forn(i,n){
        cin>>a[i];
        m[a[i]]++;
    }
    if(n%3==0){
        vector<pii> v;
        for(auto p:m)v.pb(p);
        if(v.size()>3){
            cout<<"No\n";
        }else if(v.size()==3){
            int ok=1;
            forn(i,3)ok&=v[i].s==n/3;
            if((v[0].f^v[1].f)==v[2].f&&ok){
                cout<<"Yes\n";
            }else{
                cout<<"No\n";
            }
        }else if(v.size()==2){
            if(v[0].s<v[1].s)swap(v[0],v[1]);
            if(v[0].s==2*n/3&&v[1].s==n/3&&(v[0].f^v[1].f)==v[0].f){
                cout<<"Yes\n";
            }else{
                cout<<"No\n";
            }
        }else{
            if(m[0]==n){
                cout<<"Yes\n";
            }else cout<<"No\n";            
        }
    }else{
        if(m[0]==n){
            cout<<"Yes\n";
        }else cout<<"No\n";
    }


    return 0;
}


Measured memory_bytes: 7924
import bisect
n,q=map(int,input().split())
s=list(input())
former_list=[]
latter_list=[]

for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        former_list.append(i+1)
        latter_list.append(i+2)
for j in range(q):
    l,r=map(int,input().split())
    start=bisect.bisect_left(former_list,l)
    end=bisect.bisect_right(latter_list,r)
    print(end-start)

Measured memory_bytes: 13784
#pragma optimize("O3")
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define PI 3.14159265358979323846
#define INF 1 << 30

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

int main(void) {
	int num, m, i, j, k, a, b, q;
	ll l;
	cin >> num >> m >> l;
	vector<vector<ll>> d(num, vector<ll>(num, INF));
	vector<vector<int>> ans(num, vector<int>(num, 500));
	rep(i, m) {
		cin >> a >> b;
		a--, b--;
		cin >> d[a][b];
		d[b][a] = d[a][b];
	}
	rep(i, num)
		d[i][i] = 0;
	rep(k, num) {
		rep(i, num) {
			rep(j, num)
				chmin(d[i][j], d[i][k] + d[k][j]);
		}
	}
	rep(i, num) {
		for (j = i + 1; j < num; j++) {
			if (d[i][j] <= l)
				ans[i][j] = ans[j][i] = 1;
		}
	}
	rep(k, num) {
		rep(i, num) {
			rep(j, num)
				chmin(ans[i][j], ans[i][k] + ans[k][j]);
		}
	}
	cin >> q;
	rep(i, q) {
		cin >> a >> b;
		a--, b--;
		if (ans[a][b] == 500)
			printf("-1\n");
		else
			cout << ans[a][b] - 1 << "\n";
	}
	return 0;
}

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++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 irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout << d << endl;
#define coutd(d) cout << std::setprecision(10) << d << endl;
#define cinline(n) getline(cin, n);
#define replace_all(s, b, a) replace(s.begin(), s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }

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

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

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

ll dp[101][200005];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n,w; cin>>n>>w;
  vector<ll> W(n), V(n);
  rep(i,n) cin>>W[i]>>V[i];
  
  rep(i,n){
    for(int j=0; j<=w; j++){
      if(j>=W[i]) dp[i+1][j]=max(dp[i][j], dp[i][j-W[i]]+V[i]);
      else chmax(dp[i+1][j], dp[i][j]);
    }
  }
  cout<<dp[n][w]<<endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
  }
  int ans=0;
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  for(int i=0;i<n-2;i++){
    for(int j=i+1;j<n-1;j++){
      for(int k=j+1;k<n;k++){
        if(vec.at(j)+vec.at(k)>vec.at(i)){
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int rate;
  string color;

  cin >> rate >> color;

  if (rate < 3200)
    cout << "red" << endl;
  else
    cout << color << endl;

  return 0;
}


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


int c;
vector<int> v;
vector<int> w;
void init(){
  c= 0;
  v.clear();
  w.clear();
}


bool input(){
  cin>>c;
  if(c==0)return false;
  int a;
  cin>>a;
  v.resize(a);
  w.resize(a);
  for(int i=0;i<a;i++){
    char tmp;
    cin>>v[i]>>tmp>>w[i];
  }
  return true;
}


vector<int> solve(){
  vector<int> ans(2);
  ans[0] = 1;
  ans[1] = 2;
  vector<vector<int>> dp(1100,vector<int>(1100,0));
  for(int i=0;i<c+10;i++){
    if(w[0]<=i){
      dp[0][i] = v[0];
    }
  }
  for(int i=1;i<v.size();i++){
    for(int j=0;j<c+10;j++){
      dp[i][j] = dp[i-1][j];
      if(w[i]<=j) dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
    }
  }
  ans[0] = dp[v.size()-1][c];
  for(int i=c;i>0;i--){
    if(dp[v.size()-1][i]==dp[v.size()-1][i-1])continue;
    else{
      ans[1] = i;
      return ans;
    }
  }
  ans[1] = 0;
  return ans;
}

int main(){
  int case_n = 0;
  while(init(),input()){
    case_n++;
    auto ans = solve();
    cout<<"Case "<<case_n<<":"<<endl;
    cout<<ans[0]<<endl;
    cout<<ans[1]<<endl;
  }
}

Measured memory_bytes: 5820
A, B = map(int, input().split())

grid = [["#" for _ in range(100)] for _ in range(100)]
for i in range(50, 100):
    for j in range(100):
        grid[i][j] = "."

a_count = 0
for i in range(49):
    for j in range(100):
        if a_count >= A - 1:
            continue
        if i % 2 == 1 and j % 2 == 1:
            grid[i][j] = "."
            a_count += 1

b_count = 0
for i in range(51, 100):
    for j in range(100):
        if b_count >= B - 1:
            continue
        if i % 2 == 1 and j % 2 == 1:
            grid[i][j] = "#"
            b_count += 1

print(100, 100)
for i in range(100):
    print("".join(grid[i]))


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

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;

struct UnionFind{
  vector<int> par,num;

  UnionFind(int N) : par(N),num(N){
    for(int i=0;i<N;i++){
      par[i] = i;
      num[i] = 1;
    }
  }

  int root(int x){
    if(par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    par[rx] = ry;
    num[ry] = num[ry]+num[rx]; 
  }

  int get_num(int x){
    int rx = root(x);
    return num[rx];
  }

  bool same(int x, int y){
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};


int main(void){
  ll n,k;
  cin >> n >> k;
  if(n%k < k-n%k){
    cout << n%k << endl;
  }
  else{
    cout << k-n%k << endl;
  }
  return 0;
}


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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer buffer = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(buffer.nextToken());
			int b = Integer.parseInt(buffer.nextToken());
			
			System.out.println(a * b + " " + (a + b ) * 2);
	}
}


Measured memory_bytes: 24300
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            (long x, long y) = Slice2<long>();
            var g = new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
            var h = new long[] { 0, 1, 3, 1, 2, 1, 2, 1, 1, 2,  1,  2,  1 };
            if (h[x] == h[y])
                WriteLine("Yes");
            else
                WriteLine("No");
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

Measured memory_bytes: 27400
def resolve():
    s = input()
    ls = len(s)
    for i in range(ls):
        for j in range(i, ls):
            if s[:i] + s[j:] == "keyence":
                print("YES")
                return 0
    print("NO")
    return 0


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
int main(){
FASTIO
int n;
cin>>n;
vector<int> a(n);
set<int> s;
for(int i=0;i<n;i++){
	 cin>>a[i];
	 s.insert(a[i]);
}
if(s.size()==n){
	cout<<"YES";
}
else{
	cout<<"NO";
}
return 0;
}


Measured memory_bytes: 10368
import java.util.Scanner;
public class Main {
 
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        int C = stdIn.nextInt();
         
        double Cc = C * Math.PI /180;
         
        double L = Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Cc));
        double h = b * Math.sin(Cc);
        double S = b * Math.sin(Cc) * a /2;
         
        System.out.println(S);
        System.out.println(L + a + b);
        System.out.println(h);
    }
}


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

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String[] diceNumber01 = br.readLine().split("\\s");
			String[] diceNumber02 = br.readLine().split("\\s");
			
			Dice dice01 = new Dice(diceNumber01);
			Dice dice02 = new Dice(diceNumber02);
			
			String order = "NNNNWNNNWNNNENNNENNNWNNN";
			char[] orderChar = order.toCharArray();
			if (dice01.equals(dice02, orderChar)) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}

		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}
		
	}

}

class Dice {
	private int number[];
	private int work[];

	public Dice() {

	}

	public Dice(String[] args) {
		number = new int[args.length];
		work = new int[args.length];
		// サイコロの初期化
		for (int i = 0; i < args.length; i++) {
			number[i] = Integer.parseInt(args[i]);
		}
	}

	public void rollDice(char action, int num) {
		for (int i = 0; i < num; i++) {
			this.work[i] = this.number[i];
		}

		switch (action) {
		case 'E':
			// West→Top, South→South, Top→East, Bottm→West, North→North, East→Bottom
			setNumber(work[3], work[1], work[0], work[5], work[4], work[2]);
			break;
		case 'N':
			// South→Top, Bottom→South, East→East, West→West, Top→Nouth, Nouth→Bottom
			setNumber(work[1], work[5], work[2], work[3], work[0], work[4]);
			break;
		case 'S':
			// North→Top, Top→South, East→East, West→West, Bottom→North, South→Bottom
			setNumber(work[4], work[0], work[2], work[3], work[5], work[1]);
			break;
		case 'W':
			// East→Top, South→South, Bottom→East, Top→West, North→North, West→Bottom
			setNumber(work[2], work[1], work[5], work[0], work[4], work[3]);
			break;
		default :
			break;
		}
	}

	public void setNumber(int n1, int n2, int n3, int n4, int n5, int n6) {
		this.number[0] = n1;
		this.number[1] = n2;
		this.number[2] = n3;
		this.number[3] = n4;
		this.number[4] = n5;
		this.number[5] = n6;
	}
	
	public int[] getNumber () {
		return this.number;
	}

	public int takeTopNumber() {
		return this.number[0];
	}
	
	public int takeSouthNumber() {
		return this.number[1];
	}
	
	public int takeEastNumber() {
		return this.number[2];
	}
	
	public boolean equals(Object obj, char[] order) {
		if (obj == this) {
			return true;
		}
		if (obj == null) {
			return false;
		}
		if (!(obj instanceof Dice)) {
			return false;
		}
		
		Dice another = (Dice)obj;
		
		boolean isSame = false;
		for (int i = 0; i < order.length; i++) {
this.rollDice(order[i], another.getNumber().length);
			for (int j = 0; j < another.getNumber().length; j++) {
				if (this.number[j] == another.number[j]) {
					isSame = true;
					
				} else {
					isSame = false;
					break;
				}
			}
			if (isSame) {
				break;
			}
			

		}		
		return isSame;
	}
}




Measured memory_bytes: 24624
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 競プロ_Csharp {
    class Program {
        static void Main(string[] args) {

            while (true) {

                int[] ar = NextInts();
                if (ar[0] == 0 && ar[1] == 0) return;
                int start = 1, end = ar[0];
                int sum = ar[1];
                int ans = 0;

                for (int i = start; i <= end - 2; i++) {
                    for (int j = i + 1; j <= end - 1; j++) {
                        for (int k = j + 1; k <= end; k++) {
                            if (i + j + k == sum) ans++;
                        }
                    }
                }

                Println(ans);

            }

        }

        public static void Print (Object o) {
            Console.Write(o);
        }

        public static void Println (Object o) {
            Console.WriteLine(o);
        }

        public static string NextString() {
            return Console.ReadLine();
        }

        public static string[] NextStrings () {
            return Console.ReadLine().Split();
        }

        public static int NextInt () {
            return int.Parse(Console.ReadLine());
        }

        public static int[] NextInts () {
            string[] a = Console.ReadLine().Split();
            int[] b = new int[a.Length];
            for (int i = 0; i < a.Length; i++) {
                b[i] = int.Parse(a[i]);
            }
            return b;
        }

        public static double NextDouble () {
            return double.Parse(Console.ReadLine());
        }

    }
}



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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,k,mi=10000000000;
	cin>>n>>k;
	vector<ll>v(n),dp(n);
	for(ll i=0;i<n;i++) cin>>v.at(i);
	dp.at(0)=0;
	for(ll i=1;i<n;i++){
		for(ll j=1;j<k+1;j++){
			if(i>=j){
				mi=min(abs(v[i-j]-v[i])+dp[i-j],mi);
			}
		}
		dp.at(i)=mi;
		mi=10000000000;
	}
	cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1792
N,M,K= map(int, raw_input().split())
flag=0

for x in range(N+1):
    for y in range(M+1):
        if M*x+N*y-2*x*y == K:
            print 'Yes'
            flag=1
            break
        else:
            continue
    if flag==1:
        break
if flag==0:
    print 'No'


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

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

#define INF 1e16

ll n,k,s;
ll x[2222],y[2222],z[2222];
bool used[2002];
vector<int> g[2222];

bool is_cross(int i,int j){
  return (abs(x[i]-x[j])<=s)&&(abs(y[i]-y[j])<=s)&&(abs(z[i]-z[j])<=s);
}

ll cross_surf(int i,int j){
  ll xx=s-abs(x[i]-x[j]);
  ll yy=s-abs(y[i]-y[j]);
  ll zz=s-abs(z[i]-z[j]);
  return 2*(xx*yy+yy*zz+zz*xx);
}

int main(){
	cin.sync_with_stdio(false);
  while(1){
    rep(i,2222)g[i].clear();
    cin>>n>>k>>s;
    if(n==0)break;
    rep(i,n){
      cin>>x[i]>>y[i]>>z[i];
    }
    if(k==1){
      cout<<s*s*6<<endl;
      continue;
    }
    rep(i,n)rep(j,i){
      if(is_cross(i,j)){
        g[i].pb(j);
        g[j].pb(i);
      }
    }
    ll res=INF;
    rep(i,n){
      for(int j: g[i]){
        memset(used,0,sizeof(used));
        used[i]=used[j]=true;
        ll sum=s*s*6*2-cross_surf(i,j);
        int cnt=2;
        int last;
        rep(hoge,k-2){
          for(int nxt:g[j]){
            if(used[nxt])continue;
            used[nxt]=true;
            sum+=s*s*6-cross_surf(j,nxt);
            last=nxt;
            cnt++;
            j=nxt;
          }
        }
        if(cnt==k)minch(res,sum-(k>2&&is_cross(i,last)?cross_surf(i,last):0));
      }
    }
    if(res==INF)cout<<-1<<endl;
    else cout<<res<<endl;
  }
	return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    --c[i];
  }
  const int N = 200000;
  const int md = 1000000007;
  vector<int> dp(n + 1, 0);
  vector<int> last(N, -1);
  dp[0] = 1;
  for (int i = 0; i < n; i++) {
    dp[i + 1] = dp[i];
    if (last[c[i]] != -1 && last[c[i]] != i - 1) {
      (dp[i + 1] += dp[last[c[i]] + 1]) %= md;
    }
    last[c[i]] = i;
  }
  cout << dp[n] << '\n';
  return 0;
}


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


using namespace std;

using int64 = long long;
bool bit[200001];

int main() {
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;

  for(int i = 0; i < N; i++) bit[i] = S[i] == 'A';

  int last = N;
  while(K--) {
    while(last >= 2 && bit[last - 1] && !bit[last - 2]) {
      last -= 2;
    }
    if(last == 0) break;
    if(last == 1) K %= 2;
    if(bit[0]) {
      bit[0] = false;
    } else {
      for(int i = 0; i < last; i++) bit[i] = !bit[i + 1];
    }
  }

  for(int i = 0; i < N; i++) cout << "BA"[bit[i]];
  cout << endl;

}


Measured memory_bytes: 1020
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
#define YMAX 250001
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
const int MAX = 200000;
const int MOD = 1e+9+7;
ll fac[MAX], finv[MAX], inv[MAX];
pair<vll,vll > prime_factor_decomp(ll n) {
    vll p, e;
    ll m = n;
    for (ll i = 2; i * i <= n; i++) {
        if (m % i != 0) continue;
        int c = 0;
        while (m % i == 0) c++, m /= i;
        p.push_back(i);
        e.push_back(c);
    }
    if (m > 1) {
        p.push_back(m);
        e.push_back(1);
    }
    return mp(p, e);
}
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n,int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
ll NHK(ll n,ll k){
	return COM(n+k-1,k)%MOD;
}
int main(){
	COMinit();
	ll N,M;
	ll toori=1;
	scan(N);scan(M);
	pair<vll, vll > soinsu=prime_factor_decomp(M);
	rep(i,soinsu.second.size()){
		//printf("soinsu:%lld ruijo:%lld\n",soinsu.first[i],soinsu.second[i]);
		toori*=(NHK(N,soinsu.second[i]))%MOD;
		toori%=MOD;
	}
	prin(toori);
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

void dfs(const vector<vecint> &g, int s, vector<int>& nodes) {
  for (int v : g[s]) {
    if (nodes[v] == -1) {
      dfs(g, v, nodes);
    }
  }
  for (int v : g[s]) {
    if (nodes[v] == -1) {
      nodes[v] = s;
    }
  }
}

int main()
{
  int n, m;
  cin>>n>>m;
  vector<vecint> g(n);
  vecint d(n);
  REP(i,n+m-1) {
    int a, b;
    cin>>a>>b;
    --a;--b;
    g[a].push_back(b);
    ++d[b];
  }
  int root = 0;
  REP(i,n) {
    if (d[i] == 0) root = i;
  }
  vecint nodes(n, -1);
  dfs(g, root, nodes);
  REP(i,n) {
    cout << nodes[i]+1 << endl;
  }
  return 0;
}


Measured memory_bytes: 13312
#include<bits/stdc++.h>
#define MOD (long long)(1e9+7)
using namespace std;
string a,b;
int dp[3001][3001];
int main()
{
	cin >> a >> b;
	int n=a.size(),m=b.size();
	for(int i=1; i<=n; i++)	
		for(int j=1; j<=m; j++)
		{
			if(i==1) dp[i][j]=(dp[i][j-1]|(a[i-1]==b[j-1]));
			else if(j==1) dp[i][j]=(dp[i-1][j]|(a[i-1]==b[j-1]));
			else
			{
				if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
				else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	
	//for(int i=1; i<=n; cout<<'\n',i++)	
	//	for(int j=1; j<=m; j++)
	//	{
	//		cout << dp[i][j] << ' ';
	//	}
	string ans;
	while(n && m)
	{
		if(dp[n][m] == dp[n-1][m-1]+1 && a[n-1]==b[m-1]) ans.push_back(a[--n]),m--;
		else
		{
			if(dp[n-1][m] > dp[n][m-1]) n--;
			else m--;
		}
	}
	for(int i=ans.size()-1; i>=0; i--) cout << ans[i];
	return 0;
}

Measured memory_bytes: 38720
import math,sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili=lambda:list(map(int,sys.stdin.readlines()))
li = lambda:list(map(int,input().split()))
#for deque append(),pop(),appendleft(),popleft(),count()
I=lambda:int(input())
S=lambda:input().strip()
mod = 1000000007

n=I()
a=[]
b=[]
for i in range(n):
    x,l=li()
    a.append([x-l,x+l])
a.sort()
l,r=a[0][0],a[0][1]
#print(a)
c=0
d=0
for i in range(1,n):
    k=a[i]
    p,q=k[0],k[1]
    if(l<=p and r>=q):
        l,r=p,q
        c+=1
    elif(r<p):
        l,r=p,q
    elif(r==p):
        l,r=p,q
    else:
        c+=1


print(n-c)
    

Measured memory_bytes: 20888
#!/usr/bin/env python3
import sys
from fractions import gcd
# from math import gcd


def solve(A: int, B: int, C: int, D: int):
    ci = B//C - (A-1)//C
    di = B//D - (A-1)//D
    l = C*D // gcd(C,D)
    xi = B//l - (A-1)//l

    # print(ci,di,xi)
    print(B-A+1-ci-di+xi)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()


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

using namespace std;
#define ll long long

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__ "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a;
#define lcoutln(a) cout << a << endl;
#define lcerr(a) cerr << a;
#define lcerrln(a) cerr << a << endl;
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif

int N, M;
bool m[50][50];

bool hou[50];

int dfs(int x = 0)
{
	int res = 1;
	hou[x] = true;
	reps(i,0,  N) {
		if (m[x][i] && !hou[i]) {
			res += dfs(i);
		} } return res;
}

int DFS(int r, int c)
{
	m[r][c] = false;
	m[c][r] = false;
	bool f;
	rep(i, N) hou[i] = false;
	int res = dfs();
	f = res != N;
	m[r][c] = true;
	m[c][r] = true;
	return f;
}

signed main()
{
	cin >> N >> M;
	rep(i, M) {
		CIN(int, t);
		CIN(int, tt);
		t--;tt--;
		m[t][tt] = m[tt][t] = true;
	}
	int res = 0;
	rep(i, N-1) reps(j, i+1,N) {
		if(m[i][j]) res += DFS(i, j);
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 256
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K, Q = lr()
points = np.full(N, K - Q)
for _ in range(Q):
    a = ir() - 1
    points[a] += 1

A = (points > 0)
for i in range(N):
    print('Yes' if A[i] else 'No')


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

using namespace std;

const int N = 2e5 + 5;
int arr[N], v[N];

int main() {
    //freopen("in.txt", "rt", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
    for (int i = n; i > 0; --i) {
        int z = 0;
        for (int j = i * 2; j <= n; j += i) {
            z ^= v[j];
        }
        if (z != arr[i]) v[i] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        if (v[i]) ans.push_back(i);
    }
    printf("%d\n", (int) ans.size());
    for (auto x:ans) printf("%d ", x);
}

Measured memory_bytes: 2936
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    import re
    pattern="^A[a-z]+C[a-z]+$"
    print("AC" if re.match(pattern,input()) else "WA")
resolve()

Measured memory_bytes: 38384
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

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

int main() {
	char c;
	cin >> c;
	if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
		cout << "vowel" << endl;
	}else{
		cout << "consonant" << endl;
	}
}

Measured memory_bytes: 256
#include<stdio.h>
int n,m;
int i,j;
int c[15][15],d[15][15];

int main(){
	while(1){
		scanf("%d %d",&m,&n);
		if(n==0&&m==0)return 0;
		int ans=0;
		for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&c[i][j]);
		for(i=0;i<n;i++)for(j=0;j<m;j++){
			d[i][j]=0;
		}
		for(i=0;i<m;i++)if(c[0][i]!=1)d[0][i]=1;
		for(i=0;i<n;i++)for(j=0;j<m;j++){
			if(c[i][j]==0){
				if(j-1>=0&&j-1<m&&i+1<n&&c[i+1][j-1]==0)d[i+1][j-1]+=d[i][j];
				if(j+1>=0&&j+1<m&&i+1<n&&c[i+1][j+1]==0)d[i+1][j+1]+=d[i][j];
				if(i+1<n&&c[i+1][j]!=1)d[i+1][j]+=d[i][j];
			}
			if(c[i][j]==2){
				if(i+2<n&&c[i+2][j]!=1)d[i+2][j]+=d[i][j];
			}
		}
		for(i=0;i<m;i++)if(c[n-2][i]==2)ans+=d[n-2][i];
		for(i=0;i<m;i++)if(c[n-1][i]!=1)ans+=d[n-1][i];
		printf("%d\n",ans);
	}
}
				

Measured memory_bytes: 1032
#include<cstdio>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<stack>
using namespace std;

int operate(int n1,int n2,char op){
	if(op == '+')return n1 + n2;
	if(op == '-')return n1 - n2;
	if(op == '*')return n1 * n2;
}

bool stringIsNum(string input){
	for(int i = 0;i < input.length();i++){
		if(!isdigit(input[i]))return false;
	}
	return true;
}
int main(){
	string input;
	stack<int> num;
	int k;
	string n;
	
	getline(cin,input);
//	cin >> input;
	do{
		k = input.find(' ');
		if(k != -1)n = input.substr(0,k);
		else n = input;
		string input2(input.begin() + k + 1,input.end());
		input = input2;
//		cout << n << endl;
		if(stringIsNum(n)){
			num.push(atoi(n.c_str()));
		}else{
			int n1 = num.top();
			num.pop();
			int n2 = num.top();
			num.pop();
			num.push(operate(n2,n1,n[0]));
		}
	}while(k != -1);
	
	cout << num.top() << endl;
}


Measured memory_bytes: 3224
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [a, b] = input[0].map(Number);

  return Math.ceil((a + b) / 2);
};

console.log(main(read()));


Measured memory_bytes: 29656
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
//#define int long long
template<typename T> inline bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }
const int dh[2] = {0, 1};
const int dw[2] = {1, 0};
const int MAX_D = 15000;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> G(H, vector<int>(W));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> G[i][j];
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        int B; cin >> B; G[i][j] = abs(G[i][j] - B);
    }
    
    bool dp[H][W][MAX_D] = {0};
    bool seen[H][W] = {0};
    dp[0][0][G[0][0]] = true;
    queue<pair<int, int>> que;
    que.emplace(0, 0);
    
    while (!que.empty()) {
        int h, w; tie(h, w) = que.front(); que.pop();
        if (seen[h][w]) continue;
        seen[h][w] = true;
        for (int i = 0; i < 2; i++) {
            int nh = h + dh[i], nw = w + dw[i];
            if (H <= nh || W <= nw) continue;
            int value = G[nh][nw];
            for (int d = 0; d < MAX_D; d++) if (dp[h][w][d]) {
                if (d + value < MAX_D) dp[nh][nw][d + value] = true;
                if (abs(d-value) < MAX_D) dp[nh][nw][abs(d - value)] = true;
            }
            if (!seen[nh][nw]) que.emplace(nh, nw);
        }
    }
    
    int ans = MAX_D;
    for (int d = 0; d < MAX_D; d++) if (dp[H-1][W-1][d]) {
        chmin(ans, d);
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 93824