akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct BinaryIndexedTree{
    int n;
    vector<T> dat;
    BinaryIndexedTree(int n):n(n),dat(n+1,0){}
    void add(int i,T x){
        if (i==0) return;
        for (;i<=dat.size();i+=(i&-i)) dat[i]+=x;
    }
    T sum(int i){ //[0,i]
        T res=0;
        for (;i>0;i-=(i&-i)) res+=dat[i];
        return res;
    }
    T query(int l,int r){ //[l,r)
        return sum(r-1)-sum(l-1);
    }
    int lower_bound(T x){
        if (x<=0) return 0;
        int lb=0,r=1;
        while(r<n) r<<=1;
        for (;r>0;r>>=1){
            if (lb+r<=n&&dat[lb+r]<x){
                x-=dat[lb+r]; lb+=r;
            }
        }
        return lb+1;
    }
    void add0(int i,T x){add(i+1,x);}
    T sum0(int i){return sum(i+1);}
    T query0(int l,int r){return sum(r)-sum(l);}
};

// https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_B

void DSL_2_B(){
    int n,q; cin >> n >> q;
    BinaryIndexedTree<int> BIT(n+1);

    for (;q--;){
        int c,x,y; cin >> c >> x >> y;
        if (!c) BIT.add(x,y);
        else cout << BIT.query(x,y+1) << '\n';
    }
}

// https://atcoder.jp/contests/practice2/tasks/practice2_b
void practice2_b(){
    int N,Q; cin >> N >> Q;
    vector<int> a(N);
    for (int i=0;i<N;++i) cin >> a[i];
    BinaryIndexedTree<long long> BIT(N);
    for (int i=0;i<N;++i) BIT.add0(i,a[i]);

    for (;Q--;){
        int t; cin >> t;
        if (!t){
            int p,x; cin >> p >> x;
            BIT.add0(p,x);
        } else {
            int l,r; cin >> l >> r;
            cout << BIT.query0(l,r) << '\n';
        }
    }
}

// https://atcoder.jp/contests/arc033/tasks/arc033_3

void ARC033_C(){
    int Q; cin >> Q;
    BinaryIndexedTree<int> BIT(200010);
    for (;Q--;){
        int T,X; cin >> T >> X;
        if (T==1) BIT.add(X,1);
        else {
            int pos=BIT.lower_bound(X);
            cout << pos << '\n';
            BIT.add(pos,-1);
        }
    }
}

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

Measured memory_bytes: 10212
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
main(){
  ll n;
  cin>>n;
  vector<ll> a(n);
  for(auto& x:a)cin>>x;
  auto b=a;
  sort(begin(b),end(b));
  if(a==b){
      cout<<0<<endl;
      return 0;
  }
  ll q;
  cin>>q;
  vector<ll> x(q),y(q);
  for(ll i=0;i<q;++i){
    cin>>x[i]>>y[i];
    x[i]--;y[i]--;
  }

  set<pair<ll,ll>> s;
  for(ll i=0;i<n;++i){
    if(a[i]!=b[i])s.emplace(i,a[i]);
  }
  for(ll i=0;i<q;++i){
    //cout<<s.size()<<endl;
    if(s.empty()){
      cout<<i<<endl;
      return 0;
    }
    ll xi=x[i],ax=a[x[i]],yi=y[i],ay=a[y[i]];
    auto xin=s.emplace(x[i],a[x[i]]);
    auto yin=s.emplace(y[i],a[y[i]]);
    auto xitr=xin.first;
    auto yitr=yin.first;
    ll xidx,xval,yidx,yval;
    tie(xidx,xval)=*xitr;
    tie(yidx,yval)=*yitr;
    //cout<<xidx<<","<<xval<<"  "<<yidx<<","<<yval<<endl;
    if(b[xidx]!=yval)s.emplace(xidx,yval);
    if(b[yidx]!=xval)s.emplace(yidx,xval);
    swap(a[x[i]],a[y[i]]);
    s.erase(make_pair(xi,ax));
    s.erase(make_pair(yi,ay));
  }
  if(s.empty())cout<<q<<endl;
  else cout<<-1<<endl;
}


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

public class Main {
	public static int calcMax(int max, int[] haiten) {
		if(max%10 != 0) {
			return max;
		}

		Arrays.sort(haiten);
		for(int i=0; i<haiten.length; i++) {
			if(haiten[i]%10 != 0) {
				return max - haiten[i];
			}
		}
		return 0;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] haiten = new int[n];
		int max = 0;
		for(int i=0; i<n; i++) {
			haiten[i] = sc.nextInt();
			max += haiten[i];
		}
		sc.close();

		System.out.println(calcMax(max, haiten));
	}
}


Measured memory_bytes: 23764
#include <iostream>
using namespace std;
int main()
{
  int N;
  cin >> N;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int l, r;
    cin >> l >> r;
    ans += (r-l)+1;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

const int INF=1000000;

int N;
int temp;
int ans;
vector<int> student;

int main() {
	while(true){
		//?????????
		ans=INF;
		while(student.size()>0)student.pop_back();


		cin>>N;
		if(N==0)break;

		for (int i = 0; i < N; i++) {
			cin>>temp;
			student.push_back(temp);
		}
		sort(student.begin(),student.end());
		for (int i = 0; i < N - 1; i++) {
			ans=min(ans,student[i+1]-student[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3140
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) a[i] = sc.nextInt();
        
        int res = gcd(a[0],a[1]);
        
        for(int i = 2; i < n; i++){
            res = gcd(res, a[i]);
        }
        System.out.println(res);
    }
    
    public static int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b,a%b);
    }

}


Measured memory_bytes: 50504
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

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

	int pos = -1;
	for(int i = 0; i < n-1; i++){
		if(a[i] + a[i+1] >= l) pos = i+1;
	}

	cout << (pos > 0?"Possible":"Impossible") << endl;
	if(pos > 0){
		for(int i = 1; i < pos; i++){
			if(i != pos) cout << i << endl;
		}
		for(int i = n-1; i >= pos; i--){
			cout << i << endl;
		}
	}

	return 0;
}

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

#define ll long long
#define ull unsigned long long

using namespace std;

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

	ll val1 = (X / 500) * 1000;
	ll val2 = (X - (X / 500) * 500) / 5 * 5;

	cout <<  val1 + val2 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef istringstream ISS;
typedef ostringstream OSS;
typedef vector<string> VS;
typedef short INT;
typedef vector<INT> VI;
typedef vector<VI> VVI;
typedef pair <INT, INT> II;
typedef vector <II> VII;

template<class T> ostream& operator << ( ostream& os, vector<T> v ) {
    for ( typename vector<T>::iterator it_i = v.begin(); it_i != v.end(); ++it_i ) {
        os << *it_i << ", ";
    }
    return os;
}


typedef long long LL;
const int SIZE = 16;
const int BIT_SIZE = 1 << SIZE;
typedef pair <double, VI> DATA;
const double INF = 999999999.0;

int n;
LL NO[SIZE], D[SIZE], K[SIZE]; 
LL W[BIT_SIZE]; 
DATA dp1[SIZE][BIT_SIZE];

void init() {
    for ( int i = 0; i < SIZE; ++ i ) {
        for ( int j = 0; j < BIT_SIZE; ++ j ) {
            dp1[i][j] = DATA( INF, VI() );
        }
    }
}

DATA solve( int k, int state, double weight ) {
    DATA res( 0, VI() );
    res.second.push_back( k );
    
    if ( state == (1<<n)-1 ) return res;
    if ( dp1[k][state].first != INF ) return dp1[k][state];

    res.first = INF;
    for ( int i = 0; i < n; ++ i ) {
        if ( ( state & ( 1 << i ) ) != 0 ) continue;
        DATA ret = solve( i, state | ( 1 << i ), weight + K[i] );
        ret.first += abs( D[k] - D[i] ) / ( 2000.0 / ( 70.0 + weight ) );
        if ( res.first > ret.first ) res = ret;
    }

    res.second.insert( res.second.begin(), k );
    return dp1[k][state] = res;
}

void output( DATA data ) {
    for ( int i = 0; i < n; ++ i ) {
        cout << NO[data.second[i]];
        if ( i + 1 < n ) cout << " ";
    }
    cout << endl;
}

int main() {
    cin >> n;
    for ( int i = 0; i < n; ++ i ) {
        cin >> NO[i] >> D[i] >> K[i];
        K[i] *= 20;
    }
    init();
    DATA res( INF, VI() );
    for ( int i = 0; i < n; ++ i ) {
        DATA ret = solve( i, 1 << i, K[i] );
        if ( res.first > ret.first ) res = ret;
    }
    output( res );
    return 0;
}

Measured memory_bytes: 26000
#include<iostream>
#include<string>
using namespace std;
int main(){
  int ans=1;
  int n;
  cin>>n;
  string s;
  cin>>s;
  for(int i=0;i<n-1;i++){
    if(s[i]!=s[i+1]){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 512
import Control.Monad
import Data.List

bsearch :: Integral a => (a -> Bool) -> (a, a) -> a
bsearch p (ok, ng)
  | abs (ok - ng) <= 1 = ok
  | p mid = bsearch p (mid, ng)
  | otherwise = bsearch p (ok, mid)
  where
    mid = div (ok + ng) 2

triangle :: Int -> Maybe Int
triangle n = let k = bsearch (\x -> x*(x+1)<=2*n) (0, 10000000000) in k <$ guard (k*(k+1)==2*n) 

create :: Int -> [[Int]]
create 0 = [[]]
create k = let range = [1 + div (k * (k-1)) 2 .. div (k * (k+1)) 2] in range : zipWith (:) range (create (k-1))

f :: Maybe Int -> IO ()
f (Just k) = putStrLn "Yes" >> print (k+1) >> mapM_ (putStrLn . unwords . map show . (k:)) (create k)
f Nothing = putStrLn "No"

main = readLn >>= f . triangle

Measured memory_bytes: 7676
using System;

namespace ABC088C
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] c = new int[3,3];
            string[] target;
            for(int i=0; i<3;i++){
                target = Console.ReadLine().Split(' ');
                for(int j=0;j<3;j++){
                    c[i,j] = int.Parse(target[j]);
                }
            }
            Boolean f = true;
            while(f){
                f = (c[0,0]-c[0,1] == c[1,0]-c[1,1]);
                if(!f) break;
                f = (c[2,0]-c[2,1] == c[1,0]-c[1,1]);
                if(!f) break;
                f = (c[0,0]-c[0,2] == c[1,0]-c[1,2]);
                if(!f) break;
                f = (c[2,0]-c[2,2] == c[1,0]-c[1,2]);
                if(!f) break;
                f = (c[0,1]-c[0,2] == c[1,1]-c[1,2]);
                if(!f) break;
                f = (c[2,1]-c[2,2] == c[1,1]-c[1,2]);
                if(!f) break;

                f = (c[0,0]-c[1,0] == c[0,1]-c[1,1]);
                if(!f) break;
                f = (c[0,2]-c[1,2] == c[0,1]-c[1,1]);
                if(!f) break;
                f = (c[0,0]-c[2,0] == c[0,1]-c[2,1]);
                if(!f) break;
                f = (c[0,2]-c[2,2] == c[0,1]-c[2,1]);
                if(!f) break;
                f = (c[1,0]-c[2,0] == c[1,1]-c[2,1]);
                if(!f) break;
                f = (c[1,2]-c[2,2] == c[1,1]-c[2,1]);
                break;
            }
            if(f) Console.WriteLine("Yes");
            else  Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

int main()
{
    int n, M;
    cin >> n >> M;
    V key(M), cost(M);
    rep(i,M)
    {
        int a;
        cin >> cost[i] >> a;
        int k = 0;
        rep(j,a)
        {
            int b;
            cin >> b;
            --b;
            k |= (1 << b);
        }
        key[i] = k;
    }
    int N = (1 << n) - 1;
    auto dp = make_vec(N+1, INF);
    dp[0] = 0;
    rep(i,N) rep(j,M)
    {
        int ni = i | key[j];
        chmin(dp[ni], dp[i] + cost[j]);
    }
    int ans = dp[N];
    if(ans == INF) ans = -1;
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3676
N, M, D =map(int, input().split())

if D == 0:
  P = 1/N
elif N-2*D >= 0:
  P = ((N-2*D)*2 + 2*D)/(N**2)
else:
  P = 2*(N-D)/(N**2)

print(P*(M-1))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#pragma GCC_compile("Ofast")

using namespace std;
int N,MAX;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N;
    vector<vector<int>>a(N);

    for(int i=0;i<N;i++){
        a[i]=vector<int>(3);
        for(int &x:a[i])
            cin>>x;
    }

    
    //dp[i] - the total cost such that we did activity i on the last day.
    int dp[N][3];
    for(int i=0;i<N;i++){
        dp[i][0]=dp[i][1]=dp[i][2]=-1;
    }

    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];

    for(int i=1;i<N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j!=k){
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
                }
            }
        }
    }

    cout<<max({dp[N-1][0],dp[N-1][1],dp[N-1][2]});



    

    /*
    for(auto x:a){
        for(auto val:x){
            cout<<val<<" ";
        }
    }
    */


    return 0;

}


Measured memory_bytes: 6912
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
    cin.sync_with_stdio(false);
    int N;
    cin >> N;

    vector<int> locs(N + 1);
    REP(n, N) {
        int p;
        cin >> p;
        locs[p] = n + 1;
    }

    // 番兵を入れる
    multiset<int> seen;
    seen.insert(0);
    seen.insert(0);
    seen.insert(N + 1);
    seen.insert(N + 1);

    // 以下のように並んでいるとき、2番めに大きい値が4となる範囲を考える
    // inf inf 1 5 2 4 3 7 6 inf inf 
    //      w    x       y z
    // 

    ll ans = 0;
    for(int n = N; n >= 1; --n) {
        auto loc = locs[n];
        auto it = seen.lower_bound(loc);
        auto y = *it;
        ++it;
        auto z = *it;
        --it;
        --it;
        auto x = *it;
        --it;
        auto w = *it;
        // cout << "loc of " << n << ": " << loc << endl;
        // cout << "y = " << y << endl;
        // cout << "z = " << z << endl;
        // cout << "x = " << x << endl;
        // cout << "w = " << w << endl;

        ll combination = (x - w) * (y - loc);
        combination += (z - y) * (loc - x);
        ans += combination * n;

        // cout << "added: " << (x - w) * (y - loc) << endl;
        // cout << "added: " << (z - y) * (loc - x) << endl;

        seen.insert(loc);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5376
#include "bits/stdc++.h"

#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for (long i = (a); i <= (b); ++i)
#define per(i, a, b) for (long i = (a); i >= (b); --i)

using namespace std;

using I = int;
using L = long;
using F = float;
using S = string;
using SS = stringstream;
using C = char;
using LL = long long;
using VI = vector<int>;
using VL = vector<long>;
using VF = vector<float>;
using VS = vector<string>;
using VVI = vector<vector<int>>;
using VVL = vector<vector<long>>;
using PLL = pair<long, long>;
using PLF = pair<long, float>;
using PLS = pair<long, string>;
using PSL = pair<string, long>;
using PSF = pair<string, float>;
using PSS = pair<string, string>;
using MLL = map<long, long>;
using MLF = map<long, float>;
using MLS = map<long, string>;
using MSL = map<string, long>;
using MSF = map<string, float>;
using MSS = map<string, string>;

const long kMax2 = 109;
const long kMax3 = 1009;
const long kMax4 = 10009;
const long kMax5 = 100009;
const long kMax6 = 1000009;
const long kInfI = 0x3F3F3F3F;
const float kInfF = 1e15;

template <class T>
void Printnector(const vector<T> & v) {
  for (const auto & e: v) {
    cout << e << endl;
  }
}

template <class T>
void Printnector(const vector<T> & v, unsigned n) {
  rep(i, 0, n - 1) {
    cout << v[i] << endl;
  }
}


int main(int argc, char const *argv[]) {
  I N;
  cin >> N;
  I l = 0, r = N - 1, prev = 0;
  S gnow;
  S opt;
  cout << 0 << endl;
  cin >> opt;
  gnow = opt;
  while (opt != "Vacant") {
    I mid = l + (r - l) / 2;
    cout << mid << endl;
    cin >> opt;
    if (opt == "Vacant") { break; }
    switch ((mid - prev) % 2) {
      case 0:
        if (gnow == opt) {
          l = mid + 1;
          prev = mid;
          gnow = opt;
        }
        else r = mid - 1;
        break;
      case 1:
        if (gnow != opt) {
          l = mid + 1;
          prev = mid;
          gnow = opt;
        }
        else r = mid - 1;
        break;
    }
  }

  return 0;
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(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;}
 
int main() {
    cout<<fixed<<setprecision(10);
    int n; cin >> n;
    int x = ceil((double)n/2.0);
    cout << double(x)/ double(n) << endl;
}

Measured memory_bytes: 256
<?php
list($K) = ints();
$sum = 0;
for($i = 1; $i <= $K; $i++)
for($j = 1; $j <= $K; $j++)
for($k = 1; $k <= $K; $k++)
$sum+=gcdMemo(gcdMemo($i, $j), $k);

echo $sum;

function gcdMemo($i, $j){
    static $map;
    if($i < $j)list($i,$j)=[$j,$i];
    if(!isset($map[$i][$j])){
        $map[$i][$j] = gcd($i, $j);
    }
    return $map[$i][$j];
}

function str(){return trim(fgets(STDIN));}
function ints(){return array_map('intval',explode(' ',trim(fgets(STDIN))));}
function int(){return intval(trim(fgets(STDIN)));}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}
function popcount($x){$c=0;while($x){$x&=$x-1;++$c;}return$c;}
function o(...$val){
    if(count($val)==1)$val=array_shift($val);
    echo debug_backtrace()[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0)echo "empty array";
        elseif(!is_array(current($val)))echo "array: ",implode(" ", addIndex($val)),"\n";
        else{
            echo "array:array\n";
            if(isCleanArray($val))foreach($val as $row)echo implode(" ", addIndex($row)),"\n";
            else foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row)),"\n";
        }
    }else echo $val."\n";
}
function addIndex($val){if(!isCleanArray($val)){$val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);}return $val;}
function isCleanArray($array){$clean=true;$i = 0;foreach($array as $k=>$v){if($k != $i++)$clean = false;}return $clean;}
// 座圧対象の配列 -> [圧縮された配列,復元用のMap,圧縮用のMap]
function atsu($array){$a = array_flip($array);$fuku=array_flip($a);sort($fuku);$atsu = array_flip($fuku);foreach($array as $i=>$val)$array[$i]=$atsu[$val];return [$array, $fuku, $atsu];}
function gcdAll($array){$gcd=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$gcd=gcd($gcd,$array[$i]);}return $gcd;}
function gcd($m, $n){if(!$n)return $m;return gcd($n, $m % $n);}
function lcmAll($array){$lcm=$array[0];for($i=1,$I=count($array);$i<$I;++$i){$lcm=lcm($lcm,$array[$i]);}return $lcm;}
function lcm($a, $b) {return $a / gcd($a, $b) * $b;}

function dfs($current, $from = -1, $d = 0){
  global $G, $distance;
  $distance[$current] = $d;
  foreach($G[$current] as $to){
    if($from != $to){
      dfs($to, $current, $d + 1);
    }
  }
}

function loadTree($N = false){
  if($N === false)$N = $GLOBALS['N'];
  return loadGraph($N, $N-1);
}
function loadGraph($N = false, $M = false, $both = true){
  if($N === false)$N = $GLOBALS['N'];
  if($M === false)$N = $GLOBALS['M'];
  $G = array_fill(1, $N, []);
  for($i = 0; $i < $M; $i++){
    $values = ints();
    if(count($values) == 2){
      list($a, $b) = $values;
      $G[$a][] = $b;
      if($both)$G[$b][] = $a;
    }else{
      list($a, $b, $d) = $values;
      $G[$a][] = [$b, $d];
      if($both)$G[$b][] = [$a, $d];
    }
  }
  return $G;
}


Measured memory_bytes: 17624
n, k = gets.chomp.split.map(&:to_i)
nums = Array.new(n+1, 0)
boals = gets.chomp.split(' ').map(&:to_i)
boals.each do |boal|
    nums[boal] += 1
end
nums.sort!
cnt = -1
ans = 0
nums.each do |num|
    if num == 0
        cnt+=1 
        next
    end
    if n-cnt > k
        ans+=num
        cnt+=1
    else
        break
    end
end
puts ans

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

int main(){
  ll n;
  cin>>n;
  n--;
  ll ans=0;
  for(int i=1;i<=floor(sqrt(n));i++){
    ans+=floor(n/i);
  }
  ans*=2;
  ans-=floor(sqrt(n))*floor(sqrt(n));
  cout<<ans<<endl;
}


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

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define sz(s) (int)s.size()

int main() {
    int n;
    cin >> n;
    vector<int> b(n - 1);
    for (auto &v : b) cin >> v;
    int sum = b[0] + b.back();
    for (int i = 1; i < (int)b.size(); ++i) sum += min(b[i - 1], b[i]);
    cout << sum << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#ifndef ONLINE_JUDGE
#include <custom/prettyprint.hpp>
#endif
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<db,db> pd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rb(i,x) for (auto& i : x)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define UNIQUE(x) (x).resize(unique(all(x)) - begin(x))
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pow10(n) stoll("1"+string(n,'0'))
#define dbg(x) cout << ">>> " << #x << ": " << x << '\n'

const int MOD = 1e9+7; //998244353
const int inf = 1e9+3;
const ll INF = ll(3e18)+3;
const ld PI = acos((ld)-1);
const int dx[8] = {1,0,-1,0,1,1,-1,-1}, dy[8] = {0,1,0,-1,-1,1,1,-1};
mt19937_64 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll n) { return uniform_int_distribution<ll>(0, n)(rng); }
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; }
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 

void setIO(const string& s) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
#ifndef ONLINE_JUDGE
	freopen((s+".in").c_str(),"r",stdin);
//	freopen((s+".out").c_str(),"w",stdout);
#endif
}

int main() {
    
    setIO("input");
    int n; cin >> n;
    str s; cin >> s;
    int red = 0;
    for(auto& i : s) {
        if(i == 'R')
            red++;
    }
    int inplace = 0;
    for(int i=0; i<red; ++i) {
        if(s[i] == 'R')
            inplace++;
    }
    cout << red - inplace << '\n';
    
}

/*  ! CHECK THIS IF YOU GET IT WRONG !
	* int overflow, array bounds, NO VLAs
	* uninitialized local variables, rounding errors
	* intermediate result type, scientific
	* special cases (n = 0 or 1?)
	* reset your variables in scope
	* INF not large enough for ans, adding value to _MAX
	* using wrong variables, sorting extra 0s in global array
	* comment out input from file
	* operator precedence
*/

Measured memory_bytes: 3776
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef pair<int,int> pii;
 
int main(){
  int n;
  string s;
 
  cin >> n;
 
  vector<pii> v1,v2;
  rep(i,n){
    cin >> s;
 
    pii p = pii(0,0);
    rep(j,s.size()){
      if(s[j]=='('){
	p.first++;
      }else{
	if(p.first)p.first--;
	else p.second++;
      }
    }
    if(p.first>p.second)v1.push_back(p);
    else v2.push_back(p);
  }
 
  int num1 = 0;
  rep(i,v1.size()){
    if(num1>=v1[i].second){
      num1 += v1[i].first - v1[i].second;
      v1.erase(v1.begin()+i);
      i=-1;
    }
  }
  if(v1.size()){
    cout << "No" << endl;
    return 0;
  }
 
  int num2 = 0;
  rep(i,v2.size()){
    if(num2>=v2[i].first){
      num2 += v2[i].second - v2[i].first;
      v2.erase(v2.begin()+i);
      i=-1;
    }
  }
  if(v2.size()){
    cout << "No" << endl;
    return 0;
  }
  
  if(num1==num2)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int bit[N], p[N], ans[N], a[N];
pair<int, pair<int, int>> pr[N];
 
void update(int idx, int val)
{
    while (idx < N)
    {
        bit[idx] += val;
        idx += (idx & -idx);
    }
}
 
int read(int idx)
{
    int sum = 0;
    while (idx > 0)
    {
        sum += bit[idx];
        idx -= (idx & -idx);
    }
    return sum;
}
 
int main()
{
    int n, q, x;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 0; i < q; ++i)
    {
        cin >> pr[i].second.first >> pr[i].first;
        pr[i].second.second = i;
    }
    sort(pr, pr + q);
    memset(p, -1, sizeof(p));
    memset(bit, 0, sizeof(bit));
    x = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (p[a[i]] != -1)
            update(p[a[i]], -1);
        p[a[i]] = i;
        update(i, 1);
        while (x < q and pr[x].first == i)
        {
            ans[pr[x].second.second] = read(pr[x].first) - read(pr[x].second.first - 1);
            x++;
        }
    }
    for (int i = 0; i < q; ++i)
        cout << ans[i] << "\n";
    return 0;
}

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

int main()
{
    int n, x[200010] = {}, t[200010] = {};
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
        t[i] = x[i];
    }
    sort(t, t + n);

    for (int i = 0; i < n; i++) {
        if (x[i] < t[n / 2]) cout << t[n / 2] << endl;
        else cout << t[n / 2 - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 3712
use std::collections::HashSet;

#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let s = get!(i32);
    let mut v = vec![0; 100000];
    v[1] = s;
    for i in 2..v.len() {
        if v[i - 1] % 2 == 0 {
            v[i] = v[i - 1] / 2;
        } else {
            v[i] = v[i - 1] * 3 + 1;
        }
    }
    //eprintln!("{:?}", v);
    let mut set = HashSet::new();
    let mut ans = 0;
    for i in 0..v.len() {
        if !set.contains(&v[i]) {
            set.insert(v[i]);
        } else {
            ans = i;
            break;
        }
    }
    println!("{}", ans);
}


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

int main() {
  int N, X, Y; cin >> N >> X >> Y;
  int D[N]; for (int d = 0; d < N; d++) D[d] = 0;
  // d == j - i
  /* range1: 1 <= i <  X,
     range2: X <= i <= Y,
     range3: Y <  i <= N */
  // i, j in range1
  for (int d = 1; d <= X - 2; d++)
    D[d] += X - 1 - d;
  // i, j in range2
  for (int d = 1; d <= Y - X; d++)
    D[min(d, Y - X + 1 - d)] += Y - X + 1 - d;
  // i, j in range3
  for (int d = 1; d <= N - Y - 1; d++)
    D[d] += N - Y - d;
  // i in range1, j in range3
  for (int i = 1; i < X; i++)
    for (int j = Y+1; j <= N; j++)
      D[X - i + j - Y + 1]++;
  // j in range2
  for (int j = X; j <= Y; j++) {
    // i in range1
    int dist_left = min(j - X, Y + 1 - j);
    for (int i = 1; i < X; i++)
      D[X - i + dist_left]++;
    // i in range3 (j < i)
    int dist_right = min(Y - j, j - X + 1);
    for (int i = Y+1; i <= N; i++)
      D[i - Y + dist_right]++;
  }
  // output
  for (int k = 1; k < N; k++) cout << D[k] << endl;
}


Measured memory_bytes: 256
import static java.util.Arrays.deepToString;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	public void run() {
		for (;sc.hasNext();) {
			String s = sc.next();
			int[] a = new int[14];
			for (int i = 0; i < s.length(); i++) {
				a[i] = (int)(s.charAt(i) - '0');
			}
			
			List<Integer> ans = new ArrayList<Integer>();
			for (int t = 1; t <= 9; t++) {
				a[13] = t;
				if (check(a.clone())) {
					ans.add(t);
				}
			}
			if (ans.size() == 0) 
				System.out.println(0);
			else {
				System.out.print(ans.get(0));
				for (int i = 1; i < ans.size(); i++)
					System.out.print(" " + ans.get(i));
				System.out.println();
			}
		}
	}
	
	boolean ok;
	boolean check(int[] a) {
		int[] b = new int[10];
		int sum = 0;
		for (int x: a) {
			b[x]++;
			sum++;
		}
		for (int i = 1; i <= 9; i++) if (b[i] > 4) return false;
		ok = false;
		rec(b, sum);
		return ok;
	}
	void rec(int[] b, int sum) {
		if (ok) return;
		if (sum == 0) {
			ok = true;
			return;
		}
		if (sum == 2) {
			for (int i = 1; i <= 9; i++) {
				if (b[i] == 2) {
					b[i] -= 2;
					rec(b, sum - 2);
					b[i] += 2;
				}
			}
		} 
		else 
		{
			for (int i = 1; i <= 9; i++) {
				if (b[i] >= 3) {
					b[i] -= 3;
					rec(b, sum - 3);
					b[i] += 3;
				}
			}
			for (int i = 1; i + 2 <= 9; i++) {
				if (b[i] >= 1 && b[i+1] >= 1 && b[i+2] >= 1) {
					b[i]--; b[i+1]--; b[i+2]--;
					rec(b, sum - 3);
					b[i]++; b[i+1]++; b[i+2]++;
				}
			}
		}
	}
}

Measured memory_bytes: 21176
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
#define dcml(n) fixed<<setprecision(n)
//CONST
//------------------------------------------
const ll INF=1010000000000000017LL;
const ll MOD=1000000007LL;
const ld EPS=1e-12;
const ld PI=3.14159265358979323846;
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define  FORS(i,m,n) for(ll (i)=(m);   (i)<=(n); (i)++)
#define  RFOR(i,m,n) for(ll (i)=(n)-1; (i)>=(n); (i)--)
#define RFORS(i,m,n) for(ll (i)=(n);   (i)>(n);  (i)--)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
#define WREPS(i,in,j,jn) REPS(i,in)REPS(j,jn)
//-----------------------------------------
//namespace
using namespace std;
//ライブラリはここに
//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

//-----------------------------------------
int main(void){
    ll a,b;cin>>a>>b;
    cout<<(a*b);
}

Measured memory_bytes: 3648
/*#include <stdio.h>
#include <stdlib.h>
int main(){
int a;
char s[100];
scanf("%s",s);

    int ans=0;
    int count=0;
    int final=100000;

    for (int ch = 0; ch < 2; ch++) {
      ans=0;
      count=0;
      while (s[count]!='\0') {
        if(ch==0){
          if(s[count]=='0' && count%2==0){ans+=1;}
          else if(s[count]=='1' && count%2==1){ans+=1;}
        }
        else if(ch==1){
          if(s[count]=='1' && count%2==0){ans+=1;}
          else if(s[count]=='0' && count%2==1){ans+=1;}
        }
        count++;
      }
      if(final>ans)final=ans;
    }

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

  return 0;
}
*/

#include <stdio.h>
#include <stdlib.h>
int main(){
int a;
char s[100000];
scanf("%s",s);

    int ans=0;
    int count=0;
    int final=100000;
    for (int ch = 0; ch < 2; ch++) {
      ans=0;
      while (s[count]!='\0') {
        if(ch==0){
          if(s[count]=='0' && count%2==0){ans+=1;}
          else if(s[count]=='1' && count%2==1){ans+=1;}
        }
        else{
          if(s[count]=='1' && count%2==0){ans+=1;}
          else if(s[count]=='0' && count%2==1){ans+=1;;}

        }
        count++;
      }
      if(final>=ans)final=ans;
      count=0;
    }

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


  return 0;
}


Measured memory_bytes: 256
from math import sqrt
def main():
    n = int(input().rstrip())
    sqrt_n = int(sqrt(n))

    total = 0
    for number in range(1,sqrt_n + 1):
        if n % number > 0:
            continue
        remain = n - number
        x, y = divmod(remain, number)
        #print(x, y, remain, number)
        if y == 0 and x > number:
            #print("○",number)
            total += x
        #elif y == 0:
        #    print("×",number)

    print(total)

if __name__ == "__main__":
  main()


Measured memory_bytes: 3068
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

cnt = Counter(A)
rect = []

for i,j in zip(cnt.keys(),cnt.values()):
    if j >= 2:
        rect.append([i,j])

rect.sort(reverse=True)
##print(rect)
ans = 0
flag = False
finished = False
for i,j in rect:
    if flag:
        ans *= i
        finished = True
        break
    elif j < 4:
        ans = i
        flag = True
    else:
        ans = i**2
        finished = True
        break

print(0 if not finished else ans)

Measured memory_bytes: 18600
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int m;
  string s;
  cin >> s;
  m=(s.at(5)-'0')*10+(s.at(6)-'0');
  if (m<=4) cout << "Heisei" << endl;
  else cout << "TBD" << endl;
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 62;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  ll a, b, x;
  cin >> a >> b >> x;
  if(a != 0) cout << b/x - (a-1)/x << endl;
  else cout << b/x + 1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
int n;
pair<int, int> a[200000];
int main() {
  cin >> n;
  for(int i = 0; i < n; ++i)
    cin >> a[i].second >> a[i].first;
  sort(a, a + n);
  int tv = 0, f = 0;
  for(int i = 0; i < n; ++i) {
    tv += a[i].second;
    if(a[i].first < tv) {
      f = 1;
      break;
    }
  }
  cout << (!f ? "Yes" : "No") << endl;
}

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

int main() {
	long long T, A[300], B[300], C[300], D[300];
	cin >> T;
	repeat(i, T) {
		cin >> A[i];
		cin >> B[i];
		cin >> C[i];
		cin >> D[i];
	}
	repeat(i, T) {

		int OK = 1;
		if (A[i] < B[i]) { cout << "No" << endl; continue; }
		if (B[i] > D[i]) { cout << "No" << endl; continue; }
		if (B[i] <= C[i]) { cout << "Yes" << endl; continue; }
		long long saisho = A[i] % B[i] - B[i];

		long long r1 = D[i], r2 = B[i], r3, r4;
		while (r2 != 0) {
			r3 = r1;
			r4 = r2;
			r2 = r1 % r2;
			r1 = r4;
		}
		long long mendoi = (B[i] - saisho) / r4;
		if ((B[i] - saisho) % r4 == 0) { mendoi--; }

		if (mendoi != (C[i] - saisho) / r4) { cout << "No" << endl; continue; }
		else { cout << "Yes" << endl; continue; }
	}
	return 0;
}


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

int main(){
	int h,w;
	int mas[11][10001];
	while(cin >> h >> w && h && w){
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin >> mas[i][j];
			}
		}
		int ans = 0;
		for(int i=0;i<(1<<h);i++){
			int sum = 0;
			for(int j=0;j<w;j++){
				int cou=0;
				for(int k=0;k<h;k++){
					cou += mas[k][j]^(i>>k&1);
				}
				sum += max(h-cou,cou);
			}
			ans = max(ans,sum);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1556
#include <iostream>
#include <set>
#include <map>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stack>
#include <queue>
#include <cmath>
#include <string>

using namespace std;

#if defined(_WIN32) || defined(__WIN32__) || defined(WIN32)
    #define _CRT_SECURE_NO_WARNINGS
    #pragma warning(disable:4996)
#endif

#define ll long long
#define vi vector<ll>
#define ull unsigned long long
#define vull vector<ull>
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>

#define ld long double

int INF = 1e9 + 7;



int main()
{
    int n, sz;
    cin >> n >> sz;
    vi v(n), w(n);
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    vector<vi> dp(n + 1, vi(sz + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= sz; j++)
            dp[i][j] = max(dp[i - 1][j], j - w[i - 1] >= 0 ? dp[i - 1][j - w[i - 1]] + v[i - 1] : 0);
    cout << dp[n][sz];
}

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

const long N=51000;

int main(){
	bool pp[N];
	int ct=0;
	long prime[10000];
	
	for(long i=0; i<N; ++i) pp[i]=true;
	pp[0]=pp[1]=false;
	for(long i=2; i<N; ++i){
		if(pp[i]) for(long j=2; i*j<N; ++j) pp[i*j]=false;
	}
	
	for(long i=2; i<N; ++i)
		if(pp[i]) prime[ct++]=i;	
		
	//printf("%d\n", ct);
	
	while(1){
		long m;
		int a, b;
		
		scanf(" %ld %d %d", &m, &a, &b);
		if(m==0) break;
		
		long max=0, ansp, ansq;
		
		for(int i=0; prime[i]*2<=m; ++i){
			long p=prime[i];
			//printf("i=%d\n", i);
			
			for(int j=i; p*prime[j]<=m; ++j){
				long q=prime[j];
				if(a*q>b*p) break;
				else{
					long t=p*q;
					if(t>max){
						max=t;
						ansp=p;
						ansq=q;	
					}
				}
			}
			
		}
		
		printf("%ld %ld\n", ansp, ansq);
	}
}

Measured memory_bytes: 1284
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    ans = ['Odd', 'Even']
    print(ans[(a*b)%2-1])
    return

#B
def B():
    a, b = map(str,input().split())
    a = a + b
    if math.sqrt(int(a)).is_integer():
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n = II()
    pre = (0, 0, 0)
    for _ in range(n):
        t,x,y = LI()
        dist = abs(pre[0] - x) + abs(pre[1] - y)
        if dist <= t - pre[2] and dist % 2 == (t - pre[2]) % 2:
            continue
        print("No")
        return
    print("Yes")
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()


Measured memory_bytes: 42988
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>A[i];

    bool res = true;

    for(int i=1;i<=n;i++){
        if(mx>A[i]+1){
            res = false; break;
        }
        mx = max(mx,A[i]);
    }

    if(res)cout<<"Yes\n";
    else cout<<"No\n";

    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

int solve (vector<pair<int, int> > A, int N, int W) {
  // 注意动态数组 A 需要再存放输入数据前，先 push_back 一个占位
  // 因为是从下标 1 开始
  int C[101][10001];

  for (int i = 1; i <= N; i++)
    C[i][0] = 0;
  for (int i = 0; i <= W; i++)
    C[0][i] = 0;
  
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= W; j++) {
      C[i][j] = C[i - 1][j];
      if (A[i].second <= j)
        C[i][j] = max(A[i].first + C[i - 1][j - A[i].second], C[i - 1][j]);
    }
  }

  return C[N][W];
}

int main () {
  int n, w, value, weight;
  vector<pair<int, int> > A;

  cin >> n >> w;
  
  A.push_back(make_pair(0, 0));

  for (int i = 0; i < n; i++) {
    cin >> value >> weight;
    A.push_back(make_pair(value, weight));
  }

  cout << solve(A, n, w) << endl;

  return 0;
}


Measured memory_bytes: 7040
#include <cstdio>

int main (){
    int N;
    scanf("%d",&N);
    int p[N];
    int max=0;
    int sum=0;
    for (int i = 0; i < N; i++){
        scanf("%d",&p[i]);
        sum+=p[i];
        if(max<p[i]) max=p[i];
    }
    sum-=max/2;
    printf("%d",sum);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define MMOD(i) ((i%MOD)+MOD)%MOD;
#define all(v) v.begin() , v.end()
#define vec(i,j) vector<vector<ll>>(i,vector<ll>(j,0))
#define input(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
const ll MAX_N=100010;
ll a,b,c,d,e,f,x,y,z,k,m,n,l,h,w,t,p,q,ans=0;
string s;
vl v1,v2;
ll dp[13][200000];

ll solve(){
    rep(i,s.length()){
        if(i==0){
            if(s[i]=='?'){
                rep(j,10){
                    dp[j][i]=1;
                }
                for(ll j=10;j<13;j++){
                    dp[j][i]=0;
                }
            }
            else{
                rep(j,13){
                    dp[j][i]=0;
                }
                dp[s[i]-'0'][i]++;
            }
        }
        else{
            rep(j,13){
                dp[j][i]=0;
            }
            if(s[i]=='?'){
                rep(j,13){
                    rep(k,10){
                        dp[(j*10+k)%13][i]+=dp[j][i-1];
                    }
                }
            }
            else{
                rep(j,13){
                    dp[(j*10+s[i]-'0')%13][i]+=dp[j][i-1];
                }
            }
            rep(j,13){
                dp[j][i]=dp[j][i]%MOD;
            }
        }
    }

    return dp[5][s.length()-1];
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>s;
    
    
    cout<<solve()<<endl;
}

Measured memory_bytes: 18896
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
print(-n % 1000)


Measured memory_bytes: 65288
iipt=lambda:int(input())
miipt=lambda:map(int,input().split(" "))
N=iipt()
l=[];
x0,y0,h0=0,0,0
for i in range(N):
    l.append(list(miipt()))
    if l[i][2]:
        x0,y0,h0=l[i]
for cx in range(0,101):
    for cy in range(0,101):
        H=h0+abs(x0-cx)+abs(y0-cy)
        f=False
        for x,y,h in l:
            if h!=max(H-abs(x-cx)-abs(y-cy),0):
                f=True
                break
        if not f:
            print(cx,cy,H)


Measured memory_bytes: 3064