akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef long long       ll;
#define pb                emplace_back
#define mp                make_pair
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define F first
#define S second
#define fore(i, b, e)     for (ll i = b; i < e; i++)
#define forr(i, b, e)     for (ll i = b; i < e; i++)
ll faster_in(){ll r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -faster_in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
//using namespace __gnu_pbds;

typedef pair<ll, ll>  ii;
typedef vector<ll>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll INF = ll(1e9 + 7);
const ll MOD=INF;
const double EPS = 1e-9;
const double PI = acos(-1);
const ll tam =2100;


typedef long long LL;
ll dp[tam][tam];
ll vC[tam][tam],fact[tam];
ll pot(ll b,ll e)
{
    b%=MOD;
    ll res=1;
    while(e)
    {
        if (e&1)
            res*=b,res%=MOD;
        b*=b,b%=MOD;
        e/=2;
    }
    return res;
}
int
 main()
{
    //cout<<pot(2,3)<<' '<<pot(3,4)<<endl;
    std::ios::sync_with_stdio(false); cin.tie(0);
    vC[0][0]=fact[0]=1;
    forr(i,1,tam)
    {
        fact[i]=fact[i-1]*i;fact[i]%=MOD;
        vC[i][0]=vC[i][i]=1;
        forr(j,1,i)
        {
            vC[i][j]=vC[i-1][j]+vC[i-1][j-1];vC[i][j]%=MOD;
        }
    }
    ll n,A,B,C,D;
    cin>>n>>A>>B>>C>>D;
    memset(dp,0,sizeof dp);
    dp[0][A-1]=1;
    forr(X,A,B+1)
    {
        //dp[0][X]=1;
        forr(i,0,n+1)
        {
            ll K=X*C;
            ll ways=0,auxways;
            while(i>=K && K<=X*D)
            {
                auxways=(dp[i-K][X-1]*vC[n-(i-K)][K])%MOD;
                auxways*=fact[K];auxways%=MOD;
                auxways*=pot(pot(fact[X],K/X),MOD-2);auxways%=MOD;
                auxways*=pot(fact[K/X],MOD-2);auxways%=MOD;
                ways+=auxways;ways%=MOD;
                K+=X;
            }
            dp[i][X]=(ways+dp[i][X-1])%MOD;
        }

        /*cout<<X<<": ";
        forr(i,0,n+1)
        cout<<dp[i][X]<<' '<<i<<endl;
        cout<<endl;*/
    }
    cout<<dp[n][B]<<endl;
}
// PLUS ULTRA!

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

int main(){
	ll L;
	cin>>L;
	cout << fixed << setprecision(12)<<endl;
	cout<<(L/3.0)*(L/3.0)*(L/3.0);
return 0;}

/*compile
g++ code.cpp
./a.out
run*/

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
	char a[10][10];
	for(int i=1;i<=2;i++){
		for(int j=1;j<=3;j++){
	scanf(" %c",&a[i][j]);
	}
	}
	if(a[1][1]==a[2][3]&&a[1][2]==a[2][2]&&a[1][3]==a[2][1]){
		printf("YES\n");
	}
	else printf("NO\n");
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String first = a.substring(2,4);
        String second = a.substring(4,6);
         
        String first1 = first.substring(0,1);
        String first2 = first.substring(1,2);
        
        String second1 = second.substring(0,1);
        String second2 = second.substring(1,2);
        
        if(first1.equals(first2) && second1.equals(second2)) {
        	System.out.println("Yes");

        }else {
        	System.out.println("No");
        }
        
    }
}

Measured memory_bytes: 22612
import java.util.Scanner;
import java.util.Arrays;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int sCount = Integer.parseInt(scanner.nextLine());
        String[] s = scanner.nextLine().split(" ");
        
        int tCount = Integer.parseInt(scanner.nextLine());
        String[] t = scanner.nextLine().split(" ");
        
        int count = 0;
        
        for (int i = 0; i < tCount; i++) {
            for (int j = 0; j < sCount; j++) {
                if (t[i].equals(s[j])) {
                    count++;
                    break;
                }
            }
        }
        
        System.out.println(count);

    }
}



Measured memory_bytes: 30636
#include <stdio.h>

void matrixChainOrder(int,int*);
int min(int,int);

static const int N = 100;

int main()
{
  int n,p[N + 1],i;

  scanf("%d",&n);

  for(i=1;i<=n;i++) scanf("%d %d",&p[i-1],&p[i]);

  matrixChainOrder(n,p);

  return 0;
}

void matrixChainOrder(int n,int p[])
{
  int i,l,j,m[N + 1][N + 1],k;

  for(i=1;i<=n;i++) m[i][i] = 0;
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j = i + l - 1;
      m[i][j] = (1 << 21);
      for(k=i;k<=j-1;k++){
	m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] +p[i - 1] * p[k] * p[j]);
      }
    }
  }

  printf("%d\n",m[1][n]);

}

int min(int a,int b)
{
  return a < b ? a : b;
}
  
      
      
  
  



Measured memory_bytes: 2104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		
		int w, a, b, ans = 0;
		w = sc.nextInt();
		a = sc.nextInt();
		b = sc.nextInt();
		
		if(a + w < b)
		ans = b - a - w;
		else if(a > b + w)
			ans = a - b - w;
		
		System.out.println(ans);
		
		sc.close();
	}

}


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

int main() {
  int A, B, C, D;
  int left, right;
  cin >> A >> B >> C >> D;
  left = A + B;
  right = C + D;
  if (left > right) {
    cout << "Left" << endl;
  } else if (left < right) {
    cout << "Right" << endl;
  } else {
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

long gcd(long a, long b)
{
    long tmp;

    while (b) {
        tmp = b;
        b = a % b;
        a = tmp;
    }

    return a;
}

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

int main(void)
{
    long a, b;

    while (~scanf("%ld %ld", &a, &b)) {
        printf("%ld %ld\n", gcd(a, b), lcm(a, b));
    }

    return 0;
}

Measured memory_bytes: 596
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

signed main(void)
{
  int n;
  cin >> n;
  int ans = 0, idx = 1;
  FOR(i, 1, n+1) {
    int ret = 0, tmp = i;
    while(tmp%2 == 0) {
      tmp /= 2;
      ret++;
    }
    if(ret > ans) ans = ret, idx = i;
  }
  cout << idx << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3030;
int n,k;
bool st[N];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int d;
		cin>>d;
		for(int j=1;j<=d;j++)
		{
			int x;
			cin>>x;
			st[x]=1;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(st[i]==0)
			ans++;
	cout<<ans<<endl;
}


Measured memory_bytes: 3636
fun main(args:Array<String>) {
  val list = (1..3).map {
    readLine()!!.split(" ").map(String::toInt)
  }
  if( list[0][0]+list[1][1] == list[0][1]+list[1][0] &&
    list[0][1]+list[1][2] == list[0][2]+list[1][1] &&
    list[1][0]+list[2][1] == list[2][0]+list[1][1] &&
    list[1][1]+list[2][2] == list[1][2]+list[2][1] )
    println("Yes")
  else
    println("No")

}

Measured memory_bytes: 38028
import java.util.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Set;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int L=sc.nextInt();
        String[]s=new String[N];
        for(int i=0;i<N;i++){
            s[i]=sc.next();
        }
        Arrays.sort(s);
        for(int i=0;i<N;i++){
            System.out.print(s[i]);
        }

        
        
}
        
        
    }


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

int main() {
	int n;
	while (cin >> n, n) {
		vector<P>v;
		rep(i, n) {
			int c1, m1, s1, m2, s2, m3, s3, m4, s4;
			cin >> c1 >> m1 >> s1 >> m2 >> s2 >> m3 >> s3 >> m4 >> s4;
			v.push_back(P((m1 + m2 + m3 + m4) * 60 + s1 + s2 + s3 + s4, c1));
		}
		sort(v.begin(), v.end());
		cout << v[0].second << endl << v[1].second << endl << v[n - 2].second << endl;
	}
}

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

#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
bool dp[100100];

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

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

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


int main(){
    int A, B, C;
    cin >> A >>B>> C;

    if(A+B+C >= 22)cout << "bust" << endl;
    else cout <<"win" << endl;




}


Measured memory_bytes: 3632
import java.util.*;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans =0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i)=='+') ans++;
            else ans--;
        }
        System.out.println(ans);
    }
}


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


using namespace std;

typedef long long ll;

int main(){
    ll N,K,min;
    cin>>N>>K;
    //cout<<N<<endl;
    
    N=N%K;
    min=N;
    vector<ll> vc;
    
    vc.push_back(N);
    
    int M=1;
    bool flag=false;
    
    while(true){
       
        N=abs(N-K);
        min=(min>N)?N:min;
        vc.push_back(N);
        ++M;
        
        sort(vc.begin(),vc.end());
        for(int i=0;i!=M;++i){
            if(vc[i]==vc[i+1]){
                flag=true;
                break;
            }
        }
        if(flag) break;
    }
    
    cout<<min<<endl;

}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>

using namespace std;
typedef long long ll;
float pi=3.14159265;
int main()
{
    float r;
    cin>>r;
    printf("%.8f",r*2*pi);
    printf("\n");
    return 0;
}

Measured memory_bytes: 3764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

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

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

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

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll n;
    cin >> n;
    vector<vector<vector<ll>>>x(4,vector<vector<ll>>(4,vector<ll>(4,1)));
    x[0][1][2] = 0;
    x[1][0][2] = 0;
    x[0][2][1] = 0;
    for (int is = 0; is < n; is++) {
        vector<vector<vector<ll>>>z(4, vector<vector<ll>>(4, vector<ll>(4)));
        ll zd = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    for (int h = 0; h < 4; h++) {
                        if(!((i==0&&j==1&&k==2)|| (i == 0 && j == 2 && k == 1)|| (i == 1 && j == 0 && k == 2)|| (h == 0 && j == 1 && k == 2)|| (h == 0 && i == 1 && k == 2)))z[i][j][k] += x[h][i][j];
                    }
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    x[i][j][k] = z[i][j][k];
                    x[i][j][k] %= 1000000007;
                }
            }
        }
    }
    cout << x[3][3][3] << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
typedef long long int LL;
typedef unsigned long long int ULL;
using namespace std;

// 插入此處

int main() {
    int n;
    cin >> n;
    map<int, vector<int>> m;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        m[x].push_back(y);
    }
    for (auto &e: m) {
        sort(e.second.begin(), e.second.end());
    }
    int f = false;
    LL top, bot;
    LL ans = 0;
    int lk;
    for (auto &e: m) {
        auto &v = e.second;
        if (f == false) {
            top = v[v.size() - 1];
            bot = v[0];
            ans = top - bot;
            lk = e.first;
            f = true;
        } else {
            LL ctop = v[v.size() - 1];
            LL cbot = v[0];
            int diff = e.first - lk;
            ans = max(ans, top - cbot + diff);
            ans = max(ans, ctop - bot + diff);
            top = max(top + diff, ctop);
            bot = min(bot - diff, cbot);
            lk = e.first;
        }
    }
    printf("%lld\n", ans);
}


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

#define int long long
#define ffor(i,n) for(int i = 0;i < (n); ++i)
#define all(v) v.begin(),v.end()
#define vi vector<int>
const int mod = 1e9 + 7;
vi fact(1e5 + 10);

void facto(){
    fact[0] = 1;
    fact[1] = 1;
    for(int i = 2;i <= 1e5 + 4;++i){
        fact[i] = fact[i - 1]*i;
        fact[i] %= mod;
    }
}

int binpow(int a,int b){
    int res = 1;
    while(b){
        if(b&1){
            res *= a;
            res %= mod;
        }
        b >>= 1;
        a = (a*a)%mod;
    }
    return res;
}

int nCr(int n,int r){
    if(n < r)return 0;
    r = min(n - r,r);
    int num = fact[n]%mod;
    int den = (fact[r]*fact[n - r])%mod;
    den = binpow(den,mod - 2);
    return (num*den)%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int n,k;
    cin >> n >> k;
    
    vi a(n);
    ffor(i,n) cin >> a[i];

    facto();
    
    sort(all(a));

    int mini = 0,maxi = 0;

    ffor(i,n){
        mini += (a[i]*(nCr(n - i - 1LL,k - 1)));
        mini %= mod;
        // cout << mini << ' ';
    }
    reverse(all(a));
    ffor(i,n){
        maxi += (a[i]*(nCr(n - i - 1LL,k - 1)));
        maxi %= mod;
        // cout << maxi << ' ';
    }
    int z = maxi - mini;
    while(z < 0){
        z += mod;
    }
    cout << z%mod;
}

Measured memory_bytes: 1792
def get_answer(a, start, end):
    return a[end] - a[start]

def create_answer_array(s):
    result = []
    result.append(0)

    for i in range(1, len(s)):
        if s[i - 1] == "A" and s[i] == "C":
            result.append(result[i - 1] + 1)
        else:
            result.append(result[i - 1])

    return result

n, q = map(int, input().split())
s = str(input())
questions = []
for _ in range(q):
    a, b = map(int, input().split())
    questions.append((a - 1, b - 1))

a = create_answer_array(s)

for question in questions:
    print(get_answer(a, question[0], question[1]))


Measured memory_bytes: 19996
H, W = gets.split.map(&:to_i)
A = H.times.map { gets.chomp }

dp = Array.new(H) { Array.new(W, 0) }
dp[0][0] = 1

WALL = '#'.freeze
MOD = 10**9 + 7

H.times do |h|
  W.times do |w|
    next if A[h][w] == WALL

    dp[h][w] += dp[h][w - 1] if w > 0
    dp[h][w] += dp[h-1][w] if h > 0
    dp[h][w] %= MOD
  end
end

puts dp[H-1][W-1]


Measured memory_bytes: 11900
#include <stdio.h>
int main(void)
{
  int a,b,c;
  int flag=1;
  scanf("%d %d %d",&a,&b,&c);
  
  if(a==b&&a!=c)
    flag=0;
  if(a==c&&b!=c)
    flag=0;
  if(b==c&&a!=b)
    flag=0;
  
  if(flag==1)
    puts("No");
  else
    puts("Yes");
  return 0;
}

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

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

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    ll A[N]; rep(i, N) cin >> A[i];
    sort(A, A+N);
    map<ll, int> mp;
    vector<ll> kouho;
    for(int i = N-1; i >= 0; i--){
        if(!mp.count(A[i])) mp[A[i]] = 1;
        else if(mp[A[i]] == 0) mp[A[i]] = 1;
        else{
            mp[A[i]] = 0;
            kouho.push_back(A[i]);
        }
    }
    sort(kouho.rbegin(), kouho.rend());
    if(kouho.size() < 2) cout << 0 << endl;
    else cout << kouho[0]*kouho[1] << endl;
    return 0;
}

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


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()


using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll  = long long;

using point = complex<double>;


void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}


const double EPS = 1e-8;
const long long mod = 1e9+7;

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

const int N = 3e5 + 5;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n , a;
    vector<int>v;
    cin >> n;

    bool can = 0;
    int ans = INT_MAX;
    for(int i = 0; i < n; ++i){
        cin >> a;
        if(a & 1 == 1)can = 1;
        int cnt = 0;
        while(a % 2 == 0){
            cnt++;
            a /= 2;
        }

        ans = min(ans,cnt);
    }
    if(can)cout << 0 << '\n';
    else cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
n = int(input())
data = []
ans = 0
for i in range(n):
    data.append(list(map(int, input().split())))
    ans += data[i][1]
data.sort(key=lambda x: x[0] - x[1])
k = 10**10
if sum([abs(data[i][1] - data[i][0]) for i in range(n)]):
    for i in range(n):
        if data[i][0] > data[i][1]:
            k = min(k, data[i][1])
    print(ans-k)
else:
    print(0)

Measured memory_bytes: 8820
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

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

    vector<int> dp(X+1,0),P{100,101,102,103,104,105};
    dp.at(0)=1;

    rep(x,0,X){
        if(dp.at(x)){
            for(auto p:P){
                if(x+p<X+1) dp.at(x+p)=1;
            }
        }
    }

    cout<<dp.at(X)<<endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
    ll n,W; cin >> n >> W;
    vl v(n),w(n);
    rep(i,n) cin >> v[i] >> w[i];
    vvl dp(n+1,vl(10005,inf));
    dp[0][0] = 0;
    rep(i,n){
        rep(j,10000){
            if(dp[i][j] == inf) continue;
            chmin(dp[i+1][j],dp[i][j]);
            chmin(dp[i+1][j+v[i]],dp[i][j]+w[i]);
        }
    }
    for(int i=10000; i>=0; i--){
        if(dp[n][i] <= W){
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 10796
#include<bits/stdc++.h>
using namespace std;
int main (){
    int x,y;cin>>x>>y;
    for(int i=0;i<=x;i++){
        int j = x - i;
        if(i*2 + j*4 == y){
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P; //ペア　タイプでふ
int main()
{
    array<char, 3> ar;
    char s;
    REP(i, 3)
    {
        cin >> s;
        ar[i] = s;
    }
    if (ar[0] != ar[1] && ar[1] != ar[2] && ar[2] != ar[0])
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	string s;
	cin>>s;
	int n = s.length();
	int ki = 0,ka = n-1;
	int ans = 0;
	while(ki<ka){
		if(s[ki]!=s[ka]) ans++;
		ki++;
		ka--;
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

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

//prototype declaration
int getint();
long long getllint();
double getdint();
char getch();
void setstring(char *s);
void showint(int i);
void showllint(long long i);
void showdouble(double i);
void showchar(char c);
void showstring(char *s);

int myPower(int a, int n) { // aのn乗の計算
	int x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int min(int a, int b) {
	return a < b ? a : b;
}

int gdc(int a, int b) {
	if (a == 0 || b == 0) {
		return a + b;
	}
	if (a > b) {
		return gdc(a%b, b);
	} else {
		return gdc(a, b%a);
	}
}

int main(void) {
	int n, i, j;
	int X;
	n = getint();
	X = getint();
	int x[n];
	int diff[n];
	ROOP(i, n) {
		x[i] = getint();
		diff[i] = abs(x[i] - X);
	}

	int a, b;
	a = diff[0];
	for(i = 1; i < n; i++) {
		b = diff[i];
		a = gdc(a, b);
	}
	showint(a);
	return 0;
}

int getint() {
	int i;
	scanf("%d", &i);
	return i;
}

long long getllint() {
	long long i;
	scanf("%lld", &i);
	return i;
}

double getdint() {
	double i;
	scanf("%lf", &i);
	return i;
}

char getch() {
	char c;
	scanf("%c", &c);
	return c;
}

void setstring(char *s) {
	scanf("%s", s);
}

void showint(int i) {
	printf("%d\n", i);
}

void showllint(long long i) {
	printf("%lld\n", i);
}

void showdouble(double i) {
	printf("%lf\n", i);
}

void showchar(char c) {
	printf("%c\n", c);
}

void showstring(char *s) {
	printf("%s\n", s);
}


Measured memory_bytes: 896
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n, m;
vector<int> g[100005];
struct edge {
  int now, from, cost;
};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a; b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> h(n + 1, -1);

  queue<edge> que;
  que.push(edge {1, -1, 1});

  while(!que.empty()) {
    edge e = que.front(); que.pop();
    REP(i, g[e.now].size()) {
      if(g[e.now][i] == e.from) continue;
      if(h[g[e.now][i]] == -1) {
        h[g[e.now][i]] = e.now;
        que.push(edge {g[e.now][i], e.now, e.cost + 1});
      }
    }
  }

  cout << "Yes" << endl;
  FOR(i, 2, n + 1) cout << h[i] << endl;
}


Measured memory_bytes: 10808
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long ;

struct unionfind{
    vi r;

    unionfind(int n){
       r = vi(n,-1); 
    }

    int root(int x){
        if(r.at(x) == -1) return x;
        return r.at(x) = root(r.at(x));
    }

    bool unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y) return false;
        r.at(y) = x;
        //if(r.at(x)>r.at(y)) swap(x,y);
        //r.at(x) += r.at(y);
        //r.at(y) = x;
        return true;
    }
};

int main(){
    int n,m,cnt; cin >> n >> m;
    cnt = n;
    unionfind uf(n);
    for(int ix=0;ix<m;ix++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        //uf.unite(a,b);
        if(uf.unite(a,b) == true){
            cnt--;
        }
    }
    cout << max(0,cnt-1) << endl;
}

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

int main()
{
  	vector<pair<int,int> > locations;
  	int n,m;
  	cin>>n>>m;
  	int x,y;
  	for(int i=0 ; i<n ; ++i)
    {
    	cin>>x>>y;
      	locations.push_back({x,y});
    }
  	vector<pair<int,int> > current_loc(n,{INT_MAX,INT_MAX});
  	for(int i=0 ; i<m ; ++i)
    {
    	cin>>x>>y;
    	for(int j=0 ; j<n ; ++j)
        {
          	int distance=abs(x-locations[j].first)+abs(y-locations[j].second);
        	if(distance<current_loc[j].first)
            {
            	current_loc[j].first=distance;
              	current_loc[j].second=i;
            }
        }
    }
  	for(auto i:current_loc)
    {
    	cout<<i.second+1<<endl;
    }
	return 0;
}

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

//#define lp_i(k,n)  for(int i = (k); i < (n); i++)
//#define lp_j(k,n)  for(int j = (k); j < (n); j++)
#define lp_ui(k,n) for(uint32_t i = (k); i < (n); i++)
//#define lp_uj(k,n) for(uint32_t j = (k); j < (n); j++)
//
//typedef uintmax_t    ull;
//typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
//typedef uint8_t      uc;

using namespace std;

int main(void)
{
	ui N{ 0 };
	cin >> N;

	vector<ul> arrayA(N);
	ul sum{ 0 };
	ul halfSum{ 0 };

	lp_ui(0, N)
	{
		cin >> arrayA[i];

		sum += arrayA[i];
		if (i % 2 == 0)
		{
			halfSum += arrayA[i];
		}
	}

	// X_0の導出
	ul ans = halfSum * 2 - sum;
	cout << ans << " ";

	lp_ui(0, N - 1)
	{
		// X_i = A_i * 2 - X_(i-1)
		ans = arrayA[i] * 2 - ans;
		cout << ans;

		if (i != N - 2)
		{
			cout << " ";
		}
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 2048
/* title: Card Game
	 source: JOI 2009-2010 Yosen No.3
	 hint: Just do it
*/



#include <iostream>
#include <algorithm> // sort, binary_search and upper_bound
#include <vector>
using namespace std;


int main()
{
	for(int N; cin >> N && N; ) {
		vector<int> v(N);
		for(int i = 0; i < N; i++) cin >> v[i];

		sort(v.begin(), v.end());
		
		vector<int> A, B;
		for(int i = 1; i <= 2 * N; i++) {
			(binary_search(v.begin(), v.end(), i) ? A : B).push_back(i);
		}

		int top = 0, turn = true;
		while(!A.empty() && !B.empty()) {
			auto p = (turn ? &A : &B);
			auto it = upper_bound(p->begin(), p->end(), top);

			if(it == p->end()) top = 0;
			else {
				top = *it;
				p->erase(it);
			}

			turn = !turn;
		}

		cout << B.size() << endl << A.size() << endl;
	}
}
			 

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int N, T;
    cin >> N >> T;
    int t;

    cin >> t;
    int res = 0;
    for(int i = 1; i < N; ++i) {
        int a;
        cin >> a;
        res += min(a - t, T);
        t = a;
    }
    cout << res + T << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define outy printf("Yes\n")
#define outn printf("No\n")
#define outf printf("First\n")
#define outs printf("Second\n")
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define FORD(a,b,c) for(int a=b;a>=c;a--)
#define FORL(a,b) for(int a=head[b];a;a=nxt[a])
#define in(a)  a=read()
#define in2(a,b)  a=read(),b=read()
#define in3(a,b,c)  a=read(),b=read(),c=read()
#define in4(a,b,c,d)  a=read(),b=read(),c=read(),d=read()
#define inl(a)  a=readl()
#define inl2(a,b)  a=readl(),b=readl()
#define inl3(a,b,c)  a=readl(),b=readl(),c=readl()
#define inl4(a,b,c,d)  a=readl(),b=readl(),c=readl(),d=readl()
#define out(a) printf("%d\n",a)
#define out2(a,b) printf("%d %d\n",a,b)
#define out3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out4(a,b,c,d) printf("%d %d %d %d\n",a,b,c,d)
#define outl(a) printf("%lld\n",a)
#define outl2(a,b) printf("%lld %lld\n",a,b)
#define outl3(a,b,c) printf("%lld %lld %lld\n",a,b,c)
#define outl4(a,b,c,d) printf("%lld %lld %lld %lld\n",a,b,c,d)
#define clr(x,y) memset(x,y,sizeof(x))
inline int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
inline ll readl(){
    char c;ll s=0;int t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
#define mod 1000000007
#define maxn 100010
#define inf 0x7fffffff
/*------------------------------------------------------------*/
//int f[maxn];
int main(){
	int x,y;
	in2(x,y);
	y/=1000;
	FOR(i,0,x)
		FOR(j,0,x){
			if(i+j>x)continue;
			if(10*i+5*j>y)continue;
			if(y-10*i-5*j==x-i-j){
				out3(i,j,x-i-j);
				return 0;
			}
		}	
	out3(-1,-1,-1);
}

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

int main() {
	int n;
	cin>>n;
	vector<int> v;
	for(int i=0;i<n;i++){
	    int x;
	    cin>>x;
	    v.push_back(x);
	}
	sort(v.begin(),v.end());
	int ans=0;
	for(int i=0;i<n;i++){
	    for(int j=i+1;j<n;j++){
	        for(int k=j+1;k<n;k++){
	            if(v[i]+v[j]>v[k] && v[i]!=v[j] && v[j]!=v[k]){
	                ans+=1;
	            }
	        }
	    }
	}
	cout<<ans;
	return 0;
}

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

using namespace std;

int main(){
    long long l,r;
    cin>>l>>r;
    if(r-l+1>=2019){
        cout<<0<<endl;
    }
    else{
        long long ans=2019;
        for (long long i = l; i < r; ++i) {
            for (long long j = i+1; j <= r; ++j) {
                if((i%2019)*(j%2019)%2019<ans)ans=(i%2019)*(j%2019)%2019;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

int main(){
  int i,j,cnt=0;
  string s;
  int w;
  cin>>s;
  cin>>w;
  string t="";
  for(i=0;w*i<s.size();i++)t+=s[w*i];
  cout<<t;
}

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

using ll = long long;
#define mod 1000000007
#define init ios::sync_with_stdio(0), cin.tie(0);
typedef vector<int> vi;
typedef pair<int, int> pi;
#define MS(x, y) memset(x, y, sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair

vector<ll> fact((ll)2e6);
void facto()
{
    fact[0] = 1;
    for (int i = 1; i <= (ll)1e6 + 5; i++)
    {
        fact[i] = fact[i - 1];
        fact[i] *= i;
        fact[i] %= mod;
    }
}

ll power(ll n, ll b)
{

    ll res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
        {
            res *= n;
            res %= mod;
        }
        n *= n;
        n %= mod;
        b >>= 1;
    }

    return res;
}

int main()
{
    init;
    facto();
    ll n;
    cin >> n;
    ll ans = (power(10, n) - 2 * power(9, n) + power(8, n)) % mod;
    if (ans < 0)
        ans += mod;
    cout << ans;
    //    ll ans = ((comb(n, 2) % mod) * (power(10, n - 2) % mod)) % mod;
    //  cout << ans;
}

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

using namespace std;

/*  テンプレここから */
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define repi(i, start, end) for(int i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define INF (1e9)
#define INFL (1e18)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define out(x) cout << (x) << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outYes(bool_val) cout << (bool_val ? "Yes" : "No") << endl;
#define outYES(bool_val) cout << (bool_val ? "YES" : "NO") << endl;
#define outPossible(bool_val) cout << (bool_val ? "Possible" : "Impossible") << endl;
#define outPOSSIBLE(bool_val) cout << (bool_val ? "POSSIBLE" : "IMPOSSIBLE") << endl;

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

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

    string s;
    cin >> s;

    s.erase(unique(all(s)), s.end());
    cout << s.size() - 1 << endl;
}

Measured memory_bytes: 512
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
using namespace std;

const long long INF = 4000000000000000001;
const int inf = 1001001001;
const int MOD = 1000000007;
typedef pair<long long,long long> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //When end-of-a-lin bit is 1, times simple N.
    if (M & 1) res = (res * N) % MOD;
    return res %= MOD;
}
long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

int parent[214514];
long long connectSize[214514];
int tall[214514];
 
int searchRoot(int V){
    //頂点Vの親==頂点Vということは頂点Vはその木の根である。
    if(parent[V] == V){
        return V;
    }
    else{
        //一回ごとにparent[V]を更新する。辺の縮約
        return parent[V] = searchRoot(parent[V]);
    }
}
 
bool same(int X,int Y){
    if(searchRoot(X) == searchRoot(Y)) return true;
    else return false;
}
 
void unite(int X,int Y){
    //X,Yの高さが高い方の木の「高さ0の根」に高さが低い方の根を付ける
    int Xroot = searchRoot(X);
    int Yroot = searchRoot(Y);
    //同じ根を持つ木を併合することはしなくてよい
    if(Xroot == Yroot) return;
    if(tall[Xroot] > tall[Yroot]){
        parent[Yroot] = Xroot;
        connectSize[Xroot] += connectSize[Yroot];
        connectSize[Yroot] = connectSize[Yroot];
    }
    else if(tall[Xroot] == tall[Yroot]){
        parent[Yroot] = Xroot;
        //高さが同じとき、YがXの根の下に入るのでYの深さはXより1深くなる
        tall[Yroot]++;
        connectSize[Xroot] += connectSize[Yroot];
    }
    else {
        parent[Xroot] = Yroot;
        connectSize[Yroot] += connectSize[Xroot];
        connectSize[Xroot] = connectSize[Yroot];
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int N;cin >> N;
    int M;cin >> M;
    for(int i = 0;i<N;i++){
        parent[i] = i;
        connectSize[i] = 1;
        tall[i] = 0;
    }
    for(int i = 0;i<M;i++){
        int a,b;cin >> a >> b;a--;b--;
        unite(a,b);
    }
    long long ans = 0;
    for(int i = 0;i<N;i++){
        ans = max(connectSize[i],ans);
    }
    /*for(int i = 0;i<N;i++){
        ans = max(ans,parentCount.at(i));
    }*/
    cout << ans << endl;
}

Measured memory_bytes: 6740
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <iomanip>
#include <queue>
using ll =long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
ll gcd(ll A, ll B){
    if(B == 0){
        return A;
    }
    return gcd(B, A%B);
}
int main() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    ll cd = (C*D)/gcd(C,D);

    ll Bsum = B - (B/C + B/D - B/cd);
    ll Asum = A-1 - ((A-1)/C + (A-1)/D - (A-1)/cd);

    cout << Bsum-Asum<< endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bool flag = true;

int main(){
    cin >> n;
    if(n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) s = "pon";
    else if(n % 10 == 3) s = "bon";
    else s = "hon";

    cout << s << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
using namespace std;
 
int Fairfield(int y, int m, int d)
{
    if(m <= 2) y--,m += 12;
    return 365*y+y/4-y/100+y/400+153*(m+1)/5+d-428;
}
 
int main()
{
    int y1, m1, d1, y2, m2, d2;
 
    while (1) {
	cin >> y1 >> m1 >> d1 >> y2 >> m2 >> d2;
 
	if (y1 == -1 && m1 == -1 && d1 == -1 && 
            y2 == -1 && m2 == -1 && d2 == -1) break;
	
	cout << Fairfield(y2, m2, d2) - Fairfield(y1, m1, d1) << endl;
    }
    return 0;
}

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

namespace ConsoleApp18
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());

            Console.WriteLine(Math.Pow(N, 3).ToString());
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    ll n;cin>>n;
    ll a[n+1],b[n+1],c[n+1];
    rep(i,1,n)cin>>a[i]>>b[i]>>c[i];
    ll dp[n+1][3];
    dp[1][0]=a[1];
    dp[1][1]=b[1];
    dp[1][2]=c[1];
    rep(i,2,n){
        dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][2]+a[i]);
        dp[i][1]=max(dp[i-1][0]+b[i],dp[i-1][2]+b[i]);
        dp[i][2]=max(dp[i-1][1]+c[i],dp[i-1][0]+c[i]);
    }
    ll ans=max(dp[n][2],max(dp[n][0],dp[n][1]));
    cout<<ans<<endl;
    
    
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse
// struct Edge {
//   int to, id;
//   Edge(int a, int b): to(a), id(b) {}
// };

double p[3010];

double dp[3010][3010];

int main () {

	int n;cin>>n;

	rep(i,n) cin>>p[i];

	dp[0][0]=1;

	rep(i,n) {
		rep(j,n) {
			dp[i+1][j]+=dp[i][j]*(1-p[i]);
			dp[i+1][j+1]+=dp[i][j]*p[i];
		}
	}

	double ans =0;

	rep(i,n+1) {
		if (i>=n/2+1) ans+=dp[n][i];
	}

	cout << fixed << setprecision(10) << ans << endl;

}

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

// 入力
int W, n;
int v[1001], w[1001];

int dp[1001][1001];
int ans_weight;

void solve(){
    // 価値の最大値を求める
    for(int i=0 ; i < n ; i++ ){
        for(int j=0 ; j <= W ; j++ ){
            if( j < w[i] ){
                dp[i+1][j] = dp[i][j];
            }else{
                dp[i+1][j] = max( dp[i][j] , dp[i][j-w[i]] + v[i] );
            }
        }
    }
    // 価値の最大値dp[n][W]となる最小の重さの総和を求める
    for(int j=0 ; j <= W ; j++ ){
        if( dp[n][j] == dp[n][W] ){
            ans_weight = j;
            break;
        }
    }
}

int main(){
    for(int t=1 ; scanf("%d", &W) , W ; t++ ){
        // 配列の初期化
        for(int i=0 ; i < 1001 ; i++ ){
            for(int j=0 ; j < 1001 ; j++ ){
                dp[i][j] = 0;
            }
        }
        
        scanf("%d", &n);
        for(int i=0 ; i < n ; i++ ){
            scanf("%d,%d", &v[i], &w[i]);
        }
        solve();
        printf("Case %d:\n", t);
        printf("%d\n%d\n", dp[n][W], ans_weight );
    }
}

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

typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 100010;

int n;
ll f[N][2];
// f[i][0/1]表示将该节点涂成黑色/白色的方案数
int cnt, head[N];
struct edge { int to, nxt; } e[N << 1];

void ins(int u, int v) {
	e[++cnt] = (edge) { v, head[u] };
	head[u] = cnt;
}

void dfs(int u, int fa) {
	f[u][0] = f[u][1] = 1;
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		(f[u][0] *= f[v][1]) %= mod;
		(f[u][1] *= (f[v][0] + f[v][1]) % mod) %= mod;
	}
}

int main() {
	scanf("%d", &n);
	for(int u, v, i = 1; i < n; ++i) {
		scanf("%d%d", &u, &v);
		ins(u, v), ins(v, u);
	}
	dfs(1, 0);
	printf("%lld\n", (f[1][0] + f[1][1]) % mod);
}

Measured memory_bytes: 9344
#include<stdio.h>

int main(void)
{
    int n;
    int a[200];
    int i;
    int ans=0;
    int ct=0;
    int vl=0;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]%2==0){
            ct++;//printf("1:ct[i%d]=%d\n",i,ct);
        }
    }

    while(ct==n){
        ct=0;
        for(i=0;i<n;i++){
            if(a[i]%2==0){
            ct++;//printf("2:ct[i%d]=%d\n",i,ct);
            }
            a[i]=a[i]/2;//printf("a[%d]=%d\n",i,a[i]);
        } 
        if(n==ct){ 
        ans++;//printf("ans=%d\n",ans);
        }
        vl=0;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;

int main(){
    ll a,b;
    cin >> a >> b;
    ll r = a + b - 1;
    cout << a * b - r << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().rstrip().split())
INF = int(1e18)

abc = []
for _ in range(M):
    a, b = map(int, input().rstrip().split())
    c = list(map(int, input().rstrip().split()))
    abc.append([a, b, c])
    
#dp = [[-1] * 2 ** (N + 1) for _ in range(M + 1)]
dp = [[INF] * 2 ** (N + 1) for _ in range(2)]

for i in range(M):
    mask = 0
    for c in abc[i][2]:
        mask += 2 ** (c - 1)

    for j in range(2 ** (N + 1)):
        dp[i%2][j] = dp[(i+1)%2][j]

    dp[i%2][mask] = min(dp[i%2][mask], abc[i][0])
        
    for j in range(2 ** (N + 1)):
        if dp[(i+1)%2][j] != INF:
            dp[i%2][j|mask] = min(dp[i%2][j|mask], dp[(i+1)%2][j] + abc[i][0])
    
if dp[i%2][2**N-1] == INF:
    print(-1)
else:
    print(dp[i%2][2**N-1])
                

Measured memory_bytes: 47980