akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

ll digits(ll n) {
    ll res = 1;
    while(n / 10 != 0) {
        n /= 10;
        res++;
    }
    return res;
}

vector<ll> enum_divisors(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (n / i != i) res.push_back(n / i);
        }
    }
    //sort(res.begin(), res.end());
    return res;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);
    
    ll n;
    cin >> n;

    vector<ll> f = enum_divisors(n);

    ll ans = 100;
    for (int i = 0; i < f.size(); i++) {
        ans =  min(ans, max(digits(f[i]), digits(n / f[i])));
    }
    cout << ans << endl;
    
}

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

#define pb push_back
#define mp make_pair
#define ll long long int

const int N = 1000000007;
int main()
{
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);    

 	int h,w;
 	cin >> h >> w;
 	char a[h][w];
 	for (int i=0;i<h;i++)
 	{
 		for (int j=0;j<w;j++)
 			cin >> a[i][j];
 	}   

 	ll dp[h][w];
 	for (int i=0;i<h;i++)
 	{
 		for (int j=0;j<w;j++)
 			dp[i][j]=0;
 	}

 	dp[0][0]=1;
 	for (int i=0;i<h;i++)
 	{
 		for (int j=0;j<w;j++)
 		{
 			if (a[i][j]=='#')
 				continue;
 			if (i-1>=0)
 				dp[i][j]=((dp[i][j]%N)+(dp[i-1][j]%N))%N;
 			if (j-1>=0)
 				dp[i][j]=((dp[i][j]%N)+(dp[i][j-1]%N))%N;
 		}
 	}

 	cout << dp[h-1][w-1] << endl;

 	/*for (int i=0;i<h;i++)
 	{
 		for (int j=0;j<w;j++)
 			printf("%lld ",dp[i][j]);
 		printf("\n");
 	}*/


	return 0;
}

Measured memory_bytes: 9088
#include<cstdio>
#include<cstdlib>
#define L 1000010
using namespace std;

//?????????????????????????????£??????RS?????????
typedef struct pp
{
	char name[15];int t;
}RS;

int head,tail,n;
RS Q[L];

//enqueue????£?
void enqueue(RS x)
{
	Q[tail]=x;
	tail=(tail+1)%L;
	
}

//dequeue????£?
RS dequeue()
{
	RS x=Q[head];
	head=(head+1)%L;
	return x;
}


int main()
{
	int time=0,n=0,q=0;
	scanf("%d%d",&n,&q);
	
	for(int i=0;i<n;i++)
	{
		scanf("%s",Q[i].name);
		scanf("%d",&Q[i].t);
		tail++;
	}
	
	for(;head!=tail;)
	{
		if(Q[head].t<=q)
		{
			time+=Q[head].t;
			printf("%s %d\n",Q[head].name,time);
			dequeue();
		}
		else
		{
			time+=q;
			Q[head].t-=q;
			enqueue(dequeue());
		}
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int inf = 1e9;

int32_t main(){
	cin.tie(0); ios::sync_with_stdio(0);
	
	int n, k;
	cin >> n >> k;
	int a[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	vector<int> dp(k+1, 0);
	dp[0] = 0;
	for(int pedras = 1; pedras <= k; pedras++){
		for(int item = 0; item < n; item++){
			if(pedras - a[item] < 0)
				break;
			if(dp[pedras - a[item]] == 0){
				dp[pedras] = 1;
				break;
			}
		}
		//cout << dp[pedras] << " ";
	}
	//cout << endl;
	
	//cout << dp[k] << endl;
	cout << (dp[k] == 0 ? "Second" : "First") << endl;
}


Measured memory_bytes: 640
s = input()
n = len(s)
if s[0] == s[1]:
  print(1, 2)
  exit()
for i, v in zip(range(n - 1), range(n - 2)):
  if s[i] == s[i + 1]:
    print (i + 1, i + 2)
    break
  if s[v] == s[v + 2]:
    print (v + 1, v + 3)
    break
else:
  print(-1, -1)

Measured memory_bytes: 3188
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
      	int b = sc.nextInt();
      	int c = sc.nextInt();
      	int d = sc.nextInt();
   	    int e = sc.nextInt();
   
      	if (a==0){
          System.out.print(1);
        }
      	if (b==0){
          System.out.print(2);
        }
      	if (c==0){
          System.out.print(3);
        }
      	if (d==0){
          System.out.print(4);
        }
      	if (e==0){
          System.out.print(5);
        }
      
	}
}

Measured memory_bytes: 35656
using System;
class Program
{
    static void Main(string[] args)
    {
        int a, b, c;
        string[] str = Console.ReadLine().Split(' ');//2つ以上のスペース区切り入力の取得
        b = int.Parse(str[0]);  //数値で受け取りたい場合は変換する
        c = int.Parse(str[1]);
        int ans;
        if(b<=c)
        {
            ans = b;
        }
        else
        {
            ans = b - 1;
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11092
#include <stdio.h>

int mod = 1000000007;

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

int minv(int a)
{
	return mpow(a, mod-2);
}

int main(void)
{
	int n, k;
	long long mfact[200005];
	long long nPr[200005];
	
	scanf("%d%d", &n, &k);
	
	if (n <= k) k = n - 1;
	
	mfact[0] = 1; nPr[0] = 1;
	for (int i = 1; i <= 200004
	; i++) {
		mfact[i] = mfact[i-1] * i % mod;
		nPr[i] = nPr[i-1] * (n-i+1) % mod;
	}
	
	long long ans = 1;
	
	for (int i = 1; i <= k; i++)
		ans = (ans + (nPr[i] * minv(mfact[i]) % mod) * (nPr[i+1] * minv(n) % mod * minv(mfact[i]) % mod) % mod) % mod;
	
	printf("%lld", ans);
	
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
 
using namespace std;
 
#define sf(n) scanf("%d", &n)
#define pd(n) printf("%.10lf", n)
#define pf(n) printf("%d", n)
#define p() printf("\n")
#define ps() printf(" ")
#define ll long long
#define ull unsigned long long
#define MAX 1e9
const int mod = 1000 * 1000 * 1000 + 7;
#define ex 1e18
#define dbl 2e09
#define qu(q) queue<int> q
#define pqu(q) priority_queue<int> q
#define len(s) s.length()
#define sz(x) int(x.size())
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define clr(x) x.clear()
#define LOG(x) std::cout << x << std::endl;
 
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = 3.14159265359;
 
int dx[6] = {-1,-1,0,0,1,1};
int dy[6] = {-1,0,-1,1,0,1};

const int N = 2e5+5;

int a[N],taken[N];
map<int,int>mp;


int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
        mp[a[i]]+=1;
    }
    ll ans=0;
    for(int i=1;i<=n;++i){
        if(mp[i] and !taken[i]){
            ans+=(mp[i]*1LL*(mp[i]-1))/2;
            taken[i]=1;
        }
    }
    for(int i=0;i<n;++i){
        cout<<ans-((mp[a[i]]*1LL*(mp[a[i]]-1))/2)+((mp[a[i]]-2)*1LL*(mp[a[i]]-1))/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 13056
n = gets.chomp.to_i
x = 0; y = 0; t = 0
n.times do 
	tt, xx, yy = gets.chomp.split(" ").map(&:to_i)
	if (xx-x).abs + (yy-y).abs > tt - t || ((xx-x).abs + (yy-y).abs).even? != (tt-t).even? then
		puts "No"
		exit
	end
	t = tt
	x = xx
	y = yy
end
puts "Yes"


Measured memory_bytes: 1788
n = int(input())

c = [i for i in range(n + 1)]

six = 1
while 6 ** six <= n:
    for i in range(6 ** six, n + 1):
        c[i] = min(c[i - (6 ** six)] + 1, c[i])
    six += 1
nine = 1
while 9 ** nine <= n:
    for i in range(9 ** nine, n + 1):
        c[i] = min(c[i - (9 ** nine)] + 1, c[i])
    nine += 1
print(c[-1])

Measured memory_bytes: 7064
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }


int main() {
	IOS;
	int n;
	string s, t;
	cin >> n >> s >> t;
	string res = "";
	REP(i, n) {
		res += s[i];
		res += t[i];
	}
	put(res);
	return 0;
}


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

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vector<vector<t>>;
typedef long long ll;
typedef vc<int> vi;
typedef vvc<int> vvi;
typedef pair<int, int> pi;

#define endl "\n"

#define k first
#define v second
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()

#define ALL(a) a.bg, a.ed

template <class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p) {
    return os << "( " << p.k << ", " << p.v << " )";
}

template <class t>
ostream &operator<<(ostream &os, const vc<t> &v) {
    os << "[ ";
    for (int i = 0; i < v.size(); i++) {
        os << v[i];
        if (i != v.size() - 1) {
            os << ", ";
        }
    }
    return os << " ]";
}

// void backtrack(int &result, int &n, vector<int> &pos, int &idx) {
//     if (n == 0) {
//         result++;
//     } else if (0 < n && idx < pos.size()) {
//         // backtrack(result, n, pos, idx + 1);
//         for (int i = idx; i < pos.size(); i++) {
//             n -= pos[i];
//             backtrack(result, n, pos, i);
//             n += pos[i];
//         }
//     }
// }

// g++ -std=c++17 -O2 -Wall template.cpp -o template
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << fixed << setprecision(18);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // Solution

    // vi pos(3);
    // int n;
    // cin >> pos[0] >> pos[1] >> pos[2] >> n;
    // int result = 0;
    // int idx = 0;
    // backtrack(result, n, pos, idx);
    // cout << result << endl;

    int r, g, b, n;
    cin >> r >> g >> b >> n;
    int tot = 0;
    for (int i = 0; i <= 3000; i++) {
        for (int j = 0; j <= 3000; j++) {
            auto bc = (double)(n - j * r - i * g) / b;
            if (floor(bc) == ceil(bc) && floor(bc) >= 0) {
                tot++;
            }
        }
    }
    cout << tot << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<list>
#include<vector>
#include<algorithm>
#include<numeric>
#include<queue>
#include<utility>
#include <map>

using namespace std;

int main(int argc, char const *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.tie(0);
    /*
    cin>>x;
    cout<<x<<endl;
    */
    int a,b,c,i,j,k,n,m,x,y,z,cnt=0,ans=0;
    string s;
    cin>>n>>s;
    for(i=0,j=s.size();i<j;i++){
        s[i]=(((s[i]-'A')+n)%26)+'A';
    }
    cout<<s<<endl;

}

Measured memory_bytes: 256
def c(x,n)
  count=0
  f=Array.new(n,false)
  q=[0]
  while q.size!=0 do
    v=q.pop
    if f[v] then
      next
    end
    x[v].each{|t|
      q<<t
    }
    f[v]=true
    count+=1
  end
  return count
end

n,m=gets.split.map(&:to_i)
z=m.times.map{gets.split.map(&:to_i)}

ans=0
z.combination(m-1){|g| 
  x=n.times.map{[]}
  g.each{|a|
    x[a[0]-1]<<a[1]-1
    x[a[1]-1]<<a[0]-1
  }
  ans+=1 if c(x,n)!=n
}

p ans

Measured memory_bytes: 1916
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

fn main() {
    input! {
        s: chars
    }

    let mut is_ok = true;
    if s[0] != 'A' {is_ok = false};
    let mut cnt = 0;
    for i in 2..s.len()-1 {
        if s[i] == 'C' {
            cnt += 1;
        }
    }
    if cnt != 1 {
        is_ok = false;
    }
    for i in 0..s.len() {
        if !(s[i] == 'A' || s[i] == 'C' || s[i].is_lowercase()) {
            is_ok = false;
        }
    }
    println!("{}", if is_ok {"AC"} else {"WA"});
}

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

int maxtime(int num){
  int time;
  time = (num + 9) / 10 * 10;
  return time;
}

int lasttime(int num){
  return  maxtime(num) - num;
}


int main(){
  int a, b, c, d, e, sum = 0;
  cin >> a >> b >> c >> d >> e;
  sum = maxtime(a) + maxtime(b) + maxtime(c) + maxtime(d) + maxtime(e);
  sum -= max({lasttime(a), lasttime(b), lasttime(c), lasttime(d), lasttime(e)});
  cout << sum << endl;
  return 0;     
}


Measured memory_bytes: 256
def configsort(arr,k)
    arr2=Array.new
    arr3=Array.new(k+1,0)
    arr.each {|n| arr3[n] +=1}
    for i in 1..k
        arr3[i] = arr3[i] + arr3[i-1]
    end
    for j in 0..arr.count-1
        arr2[arr3[arr[j]]-1] = arr[j]
        arr3[arr[j]] -= 1
    end
    return arr2
end
n =gets.to_i
arr =gets.split(" ").map(&:to_i)
puts configsort(arr,10000).join(" ")


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

int dp[1001][100001];
int weight[101];
int value[101];

int main(){
	int n, w;
	cin >> n >> w;
	for(int i=0; i<n; i++) cin >> value[i] >> weight[i];
	
	for(int i=0; i<n; i++){
		for(int j=0; j<=w; j++){
			if(j>=weight[i]) dp[i+1][j] = max(dp[i][j], dp[i+1][j-weight[i]] + value[i]);
			else dp[i+1][j] = dp[i][j];
		}
	}
	
	cout << dp[n][w] << endl;
	
	return 0;
}


Measured memory_bytes: 7400
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n,i;
    cin >> n;
 
    vector<int> vec(n);
 
    for(i=0;i<n;i++){
        cin >> vec.at(i);
    }
/*
    for(i=0;i<n;i++){
        cout << vec.at(i) << endl;
    }
    */
    int flag = 0;
 
    for(i=0;i<n;i++){
        if(vec.at(i)%2==0 && vec.at(i)%3 != 0 /*|| */ ){
            if(vec.at(i)%5 != 0){
                flag = 1;
            }
        }
    }
    
 
    if(flag==1){
        cout << "DENIED" << endl;
    }else{
        cout << "APPROVED" << endl;
    }
}
 
 

Measured memory_bytes: 256
/***************************************************
 * Problem Name : D - Knapsack 1.cpp
 * Problem Link : https://atcoder.jp/contests/dp/tasks/dp_d
 * OJ           : atCoder
 * Verdict      : Trying
 * Date         : 2019-01-26
 * Problem Type : Easy dp()
 * Author Name  : Saikat Sharma
 * University   : CSE, MBSTU
 ***************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<vector>
#include<queue>
#include<cstdlib>
#include<deque>
#include<stack>
#include<map>
#include<set>
#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FileRead freopen ("/home/saikat/Desktop/logN/input.txt", "r", stdin);
#define FileWrite freopen ("/home/saikat/Desktop/logN/output.txt", "w", stdout);
#define SET(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define pll pair <ll, ll>
#define debug cout <<"#########\n";
#define nl cout << "\n";
#define sp cout << " ";
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define ss(n) scanf("%s", n)
#define pf(n) scanf("%d", n)
#define pfl(n) scanf("%lld", n)
#define all(v) v.begin(), v.end()
#define Pow2(x) ((x)*(x))
#define Mod(x, m) ((((x) % (m)) + (m)) % (m))
#define Max3(a, b, c) max(a, max(b, c))
#define Min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define mk make_pair
#define MAX 100005
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

template <typename T>
std::string NumberToString ( T Number ) {
    std::ostringstream ss;
    ss << Number;
    return ss.str();
}
ll lcm (ll a, ll b) {
    return a * b / __gcd (a, b);
}
/************************************ Code Start Here ******************************************************/
int n, cap;
int p[MAX], w[MAX];
ll dp[103][MAX];
ll knapSack (int i, int W) {
    //~ debug;
    if (i >= n) {
        return 0;
    }

    if (dp[i][W] != -1) return dp[i][W];

    ll prof1 = 0, prof2 = 0;

    if (W + w[i] <= cap) {
        prof1 = (ll) p[i] + knapSack (i + 1, W + w[i]);
    }

    prof2 = knapSack (i + 1, W);
    return dp[i][W] = max (prof1, prof2);
}
int main () {
    __FastIO;
    cin >> n >> cap;

    for (int i = 0; i < n; i++) {
        cin >> w[i] >> p[i];
    }

    SET (dp, -1);
    cout << knapSack (0, 0) << "\n";
    return 0;
}


Measured memory_bytes: 80768
N = int(input())
res = 0
for i in range(N):
    if i+1 <= 9 and i+1 >= 1:
        res += 1
    elif i+1 <= 999 and i+1 >= 100:
        res += 1
    elif i+1 <= 99999 and i+1 >= 10000:
        res += 1
print(res)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
vector<int> g[200005];
int h[200005];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    cin >> h[i];
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    bool ok = true;
    for (int v : g[i])
      if (h[v] >= h[i])
        ok = false;
    ans += ok;
  }
  cout << ans << endl;
}

Measured memory_bytes: 11520
#include <iostream>
#include <stdio.h>
#include <vector>
#include <tuple>

using namespace std;

typedef long long ll;

int main() {
  //  https://atcoder.jp/contests/dp/tasks/dp_d

  ll N, W;
  cin >> N >> W;

  vector<ll> w(N+1), v(N+1);
  for (ll i=1; i<=N; i++) {
    cin >> w[i] >> v[i];
  }

  vector< vector<ll> > DP ( N+1 );
  DP[0] = vector<ll>(W+1, 0);

  for(auto i = 1; i <= N; i++ ) {
    DP[i] = vector<ll>(W+1, 0);

    for (auto iw = 0; iw <= W; iw++) {
      if (iw < w[i]) { DP[i][iw] = DP[i-1][iw];} 
      else {
        DP[i][iw] = max(
          DP[i-1][iw],
          DP[i-1][ iw-w[i]]  + v[i]  
        );
      }
    }
  }

  cout << DP[N][W];

  return 0;
}



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

vector<int> aisle[100001];

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    aisle[a - 1].push_back(b - 1);
    aisle[b - 1].push_back(a - 1);
  }

  int ans = 0;
  rep(i, n) {
    bool good = true;
    for(int m : aisle[i]) {
      if(h[i] <= h[m]) {
        good = false;
        break;
      }
    }
    if(good)
      ans++;
  }

  cout << ans;
}


Measured memory_bytes: 9068
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

class Main
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt(),m=sc.nextInt();
		
		boolean[] in=new boolean[n],ot=new boolean[n];
		
		int[] a=new int[m],b=new int[m];
		
		for(int i=0;i<m;i++)
		{
			int u=sc.nextInt()-1,v=sc.nextInt()-1;
			
			a[i]=Math.min(u,v);b[i]=Math.max(u,v);
			
			if(u==0)
			{
				in[v]=true;
			}
			
			if(v==n-1)
			{
				ot[u]=true;
			}
		}
		
		boolean ans=false;
		
		for(int i=0;i<n;i++)
		{
			if(in[i] && ot[i])
			{
				ans=true;
			}
		}
		
		out.println(ans?"POSSIBLE":"IMPOSSIBLE");out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}

Measured memory_bytes: 44840
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    public static class Task {

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            int[] z = new int[10];
            for (int i = 0; i < 3; i++) {
                z[sc.nextInt()]++;
            }
            if (z[5] == 2 && z[7] == 1) {
                pw.println("YES");
            } else {
                pw.println("NO");
            }

        }
    }

    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("input"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("input"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}

Measured memory_bytes: 21460
#include <stdio.h>
#include <malloc.h>

int main()
{
    long *a = (long int*)malloc(300000 * sizeof(long int));
	long *b = (long int*)malloc(300000 * sizeof(long int));
    int n,i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%ld",&a[i]);
    }
    for(j=0,i=n-1;i>=0;i=i-2)
    {
        b[j]=a[i];
        j++;
    }
    if(n%2==0)
    {

    for(i=i+1;i<n;i=i+2)
    {
        b[j]=a[i];
        
        j++;
    }
    }
    else
    {
    for(i=i+3;i<n;i=i+2)
    {
        b[j]=a[i];
        
        j++;

    }
    }

    for(j=0;j<n;j++)
    {
        printf("%ld ",b[j]);
    }

    return 0;
}




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


int main() {
    int x;
    cin >> x;
    if(x == 1)cout << "Hello World\n";
    else {
        int a,b;
        cin >> a >> b;
        cout << a + b << endl;
    }
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
using System;
using System.Linq;

public class Program
{
    static void Main()
    {
        char[] input = Console.ReadLine().ToCharArray();
        bool[] s = new bool[input.Length];
        for (int i = 0; i < input.Length; i++)
        {
            if(input[i] == '1')
                s[i] = true;
            else
                s[i] = false;
        }
        int ans = 0;
        for (int i = 1; i < s.Length; i++)
        {
            if (s[i - 1] == s[i])
            {
                s[i] = !s[i];
                ans++;
            }
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13204
#include<stdio.h>

int main(){
  int n,a[100000],i,visit[100001]={},cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  i=1;
  while(i!=2){
    visit[i]++;
    if(visit[i]>1){
      printf("-1\n");
      return 0;
    }
    i=a[i-1];
    cnt++;
  }
  printf("%d\n",cnt);
}

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

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

  if (S == "Sunny") {
    cout << "Cloudy" << endl;
  }
  else if (S == "Cloudy"){
    cout<< "Rainy" <<endl;
  }
  else{
    cout<< "Sunny" <<endl;
  }
}

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

#define PI 3.14159265358973

int main(void){
    // Your code here!
    int a,b,c;
    double S,l,h;
    
    scanf("%d %d %d", &a,&b,&c);

    S = a*b*sin(c*PI/180)/2;
    l = a+b+sqrt(a*a+b*b-2*a*b*cos(c*PI/180));
    h = S/a*2;
    
    printf("%lf\n%lf\n%lf\n",S,l,h);
    
}



Measured memory_bytes: 1988
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, [ $t:tt ]) => {{
    let len = read_value!($iter, usize);
    (0..len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  }};

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    a: i32,
    b: i32,
  }
  if a <= 9 && b <= 9 {
    puts!("{}\n", a * b);
  } else {
    puts!("-1\n");
  }
}


Measured memory_bytes: 4352
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])
    def root(self):
        for node in self.nodes.values():
            if node and node.nodetype() == 'root':
                return node
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        self.update_height()
        
        for child in self.children():
            child.parent = self
            child.update_depth()
    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()
            
    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()
                
    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'
    def degree(self):
        return len(self.children())
    
    def children(self):
        return [child for child in [self.left, self.right] if child]
    
    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode
                
tree = Tree()

n = int(input())
for i in range(n):
    id, left, right = map(int, input().split())
    tree.add_child(id, left, right)
orders = ['Preorder', 'Inorder', 'Postorder']

for order in orders:
    print(order)
    print('',*[node.id for node in tree.root().walk(order)])

Measured memory_bytes: 6828
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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; }

const int MAX = 100010;

struct UnionFind {
    vector<int> par;

    UnionFind(int n) {
        par.resize(n);
        rep(i, n) par[i] = i;
    }

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

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

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

int main() {
    int n, m, p[MAX];
    cin >> n >> m;
    rep(i, n) cin >> p[i];
    rep(i, n) p[i]--;

    UnionFind uf(n);

    rep(i, m) {
        int x, y; cin >> x >> y;
        x--; y--;
        uf.unite(p[x], p[y]);
    }

    int ans = 0;
    rep(i, n) {
        if (uf.same(i, p[i])) ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	int n,m,a[100],i,x=0,c=0;
	double y=0;
	scanf("%d %d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		y+=a[i];
	}
	y=y/(4*m);
	for(i=0;i<n;i++){
		if(y<=a[i]) c++;
	}
	if(c>=m) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 1624
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define RG register
using namespace std;
const int N=1e5+10;
int n,m,num[N],ans,cnt[N],bck[N],cs[N],maxx[N];
inline int read(){
	char ch=getchar(); int x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}
	return x*f;}
inline bool cmp(int a,int b){return a%m<b%m;}
inline int mx(int a,int b){return a>b ? a : b ;}
inline int mi(int a,int b){return a<b ? a : b ;}
int main()
{
//	freopen("Pair Cards.in","r",stdin);
	n=read(); m=read();
	for(RG int i=1;i<=n;i++) 
	{
		num[i]=read();
		cnt[num[i]%m]++; bck[num[i]]++;
	}
	ans+=cnt[0]/2;
	for(RG int i=1;i<m;i++)
	{
		if(i==m-i) 
		{
			ans+=cnt[i]/2; cnt[i]=0;
			continue;
		}
		int minn=mi(cnt[i],cnt[m-i]);
		ans+=minn; cnt[i]-=minn; cnt[m-i]-=minn;
	}
	for(RG int i=1;i<m;i++)
	{
		cnt[i]/=2;
		for(RG int j=i;j<=100000 && cnt[i]>0;j+=m)
		{
			ans+=mi(cnt[i], bck[j]/2);
			cnt[i]-=bck[j]/2;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8, pi = acos(-1.0);
bool eq(ld a, ld b){return (abs(b-a)<eps);}
ld dot(Point a, Point b){return real(conj(a)*b);}
ld cross(Point a, Point b){ return imag(conj(a)*b);}

class Line{
public:
  Point a,b;
};

bool Parallel(const Line& l1, const Line& l2){
  return eq(cross(l1.b-l1.a,l2.b-l2.a), 0);
}

bool Orthogonal(const Line& l1, const Line& l2){
  return eq(dot(l1.b-l1.a,l2.b-l2.a), 0);
}

void solve(Line s,Line t){
  Point sv=s.b-s.a,tv=t.b-t.a;
  Point result=s.a+sv*cross(tv,t.a-s.a)/cross(tv,sv);
  printf("%.10Lf %.10Lf\n",result.real(),result.imag());
}

int main(){
  int q;cin>>q;
  REP(i,q){
    ld real, imag;
    Line s1,s2;
    cin>>real>>imag;
    s1.a = Point(real,imag);
    cin>>real>>imag;
    s1.b = Point(real,imag);
    cin>>real>>imag;
    s2.a = Point(real,imag);
    cin>>real>>imag;
    s2.b = Point(real,imag);
    solve(s1,s2);
  }
}

Measured memory_bytes: 1236
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal variable
//------------------------------------------
int N,M;
VI Vec;

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int A, B, C, X, r=0;
    cin >> A >> B >> C >> X;
    REP(i, A+1)
    {
        REP(j, B+1)
        {
            REP(k, C+1)
            {
                int cost = 500*i+100*j+50*k;
                if (cost == X) r++;
            }
        }
    }
    cout << r << endl; 
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,mi=100001,m,sum=0,x;
  cin>>n>>x;
  for(int i=0;i<n;i++){
    cin>>m;
    mi=min(mi,m);
    sum+=m;
  }
  cout<<n+(x-sum)/mi<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>

using namespace std;

int main(){
	int n,m;
	while(1){
		scanf("%d",&n);
		if(n == 0){
			break;
		}
		scanf("%d",&m);
		char* data = new char[m + 1];
		scanf("%s",data);
		vector<int> v;
	
		char* pt = data;
		int self;
		bool flag;
		while(*pt != '\0'){
			if(*pt == 'I'){
				self = 0;
				while(1){
					flag = true;
					if( *(pt+1) == 'O' ){
						if( *(pt + 2) == 'I'){
							self += 1;
							flag = false;
							pt+=2;
						}
					}
					if(flag){
						break;
					}
				}
				if(self != 0){
					v.push_back(self);
				}
			}
			pt++;
		}
	
		int ans = 0;
		vector<int>::iterator it;
		for(it = v.begin();it<v.end();it++){
			if(*it >= n){
				ans += 1 + *it - n;
			}
		}
		printf("%d\n",ans);
		delete[] data;
	}
}

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

int main(){
    long n,max=1;
    cin>>n;
    for(long i=1;i<std::sqrt(n)+1;i++){
        if(n%i==0&&i>max) max=i;
    }
    long dif=n/max;
    cout<<(dif-1)+(max-1)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

//const long long MOD = 1000000007;
const long long MOD = 998244353;
const long long INF = 1LL << 60;



const long double PI = 3.14159265359;
const int MAX_N = 100010;


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	VE x(n), l(n); rep(i, n)cin >> x[i] >> l[i];
	VE a(n), b(n);
	rep(i, n) {
		a[i] = x[i] - l[i];
		b[i] = x[i] + l[i];
	}
	vector<P>tmp(n);
	rep(i, n) {
		tmp[i] = make_pair(b[i], a[i]);
	}
	sort(ALL(tmp));
	int ans = 0;
	int t = -INF;
	rep(i, n) {
		if (t <= tmp[i].second) {
			ans++; t = tmp[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define INIT_CAP 10
#define INF 1000000000

#define min(a, b) (((a) < (b)) ? (a) : (b))

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

typedef struct {
	int to, w;
} Edge;

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

typedef struct {
	int num, d;
} PNumDis;

VecEdge adj[30 * 30 * 4];
PNumDis heap[30 * 30 * 4 * 4];
int hsize;
int d[30 * 30 * 4];

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};
}

void freeAll(int n) {
	while (n--)
		free(adj[n].elem);
}

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, j, k, l;
	int w, h;

	while (scanf("%d %d", &w, &h), w) {
		int s[30][30];
		int c[4];

		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				scanf("%d", s[i] + j);

		for (i = 0; i < 4; i++)
			scanf("%d", c + i);

		init(h * w * 4);

		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				for (k = 0; k < 4; k++)
					for (l = 0; l < 4; l++) {
						int nd = k + l & 3;
						int ni = i + di[nd], nj = j + dj[nd];
						if (ni >= 0 && ni < h && nj >= 0 && nj < w)
							add(i * w * 4 + j * 4 + k, ni * w * 4 + nj * 4 + nd, l == s[i][j] ? 0 : c[l]);
					}

		dijkstra(h * w * 4, 1);

		printf("%d\n", min(d[(h - 1) * w * 4 + (w - 1) * 4 + 1], d[(h - 1) * w * 4 + (w - 1) * 4 + 2]));

		freeAll(h * w * 4);
	}

	return 0;
}

Measured memory_bytes: 1036
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split(' ');
        int N = int.Parse(s[0]);
        int X = int.Parse(s[1]);
        int[] m = new int[N];
        for (int i = 0; i < N; i++)
            m[i] = int.Parse(Console.ReadLine());

        int sum = m.Sum();
        int min = m.Min();
        Console.WriteLine(N + (X - sum) / min);
    }
}


Measured memory_bytes: 11220
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int x = Integer.parseInt(sc.next());
        Integer[] c = new Integer[n];
        Integer[][] a = new Integer[n][m];
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sc.next());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(sc.next());
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 1 << n; i++) {
            Integer[] s = new Integer[m];
            int p = 0;
            Arrays.fill(s, 0);
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) != 1) continue;
                p += c[j];
                for (int k = 0; k < m; k++) {
                    s[k] += a[j][k];
                }
            }
            boolean f = true;
            for (Integer t : s) {
                if (t < x) {
                    f = false;
                    break;
                }
            }
            if (f) {
                ans = Math.min(ans, p + 1);
            }
        }
        out.println(ans % Integer.MAX_VALUE - 1);
        out.flush();
    }
}

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

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

int main(){

  int K;
  std::cin >> K;

  int result = 0;

  for(int a=1; a<=K; a++){
    for(int b=1; b<=K; b++){
      for(int c=1;c<=K; c++){
        result += gcd(a, gcd(b, c));
      }
    }
  }

  std::cout << result << std::endl;




  return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b.at(i);
  vector<int> a(n);
  rep(i,n){
    if( i==0 ){
      a.at(i) = b.at(i);
      continue;
    }
    if( i==n-1 ){
      a.at(i) = b.at(i-1);
      continue;
    }
    a.at(i) = min( b.at(i-1),b.at(i) );
  }
  
  int sum=0;
  rep(i,n){
  	sum += a.at(i);
  }
  
  cout << sum << endl;
    
  return 0;
}


Measured memory_bytes: 256
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  r=I()
  return (r*2)*math.pi

# main()
print(main())


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

int main(){
	int W,H,N;
  cin>>W>>H>>N;
  vector<int> vec(3);
  int a1=0;
  int a2=W;
  int a3=0;
  int a4=H;
  
  for(int i=0;i<N;i++){
    cin>>vec.at(0)>>vec.at(1)>>vec.at(2);
  	if(vec.at(2)==1)
    	a1=max(a1,vec.at(0));
    else if(vec.at(2)==2)
    	a2=min(a2,vec.at(0));
    else if(vec.at(2)==3)
    	a3=max(a3,vec.at(1));
    else if(vec.at(2)==4)
    	a4=min(a4,vec.at(1));
  }
 if((a2-a1)>0&&(a4-a3)>0)
    cout<<(a2-a1)*(a4-a3)<<endl;
  else
    cout<<0<<endl;
}

Measured memory_bytes: 256