akhauriyash/Code-Regression huggingface dataset:
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
 
using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << std::endl
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}

template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

ll pow_mod(ll a, ll b, ll mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }

  ll x = 1;

  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;

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

  ll n,m;
  std::cin>>n>>m;

  std::vector<ll> s(n),t(m);
  rep(i,0,n)std::cin>>s[i];
  rep(i,0,m)std::cin>>t[i];

  std::vector<std::vector<ll>> dp(n+1,std::vector<ll>(m+1,0)),sum(n+1,std::vector<ll>(m+1,0));

  dp[0][0]=1;

  rep(i,0,n+1)sum[i][0]=1;
  rep(i,0,m+1)sum[0][i]=1;

  rep(i,1,n+1){
    ll temp=0;
    rep(j,1,m+1){
      if(s[i-1]==t[j-1])dp[i][j]=sum[i-1][j-1];
      temp=(temp+dp[i][j])%MOD;
      sum[i][j]=(sum[i-1][j]+temp)%MOD;
    }
  }

  std::cout<<sum[n][m]<<"\n";

  return 0;
}

Measured memory_bytes: 62976
### constant

INF = 1 << 30

### main

loop do
  n = gets.to_i
  break if n == 0

  cmds = {}
  dlrs = {}
  ordrs = []

  n.times do
    dlr, type, cmd, pr = gets.strip.split
    pr = pr.to_i
    #p ["new order", dlr, type, cmd, pr]
    
    dlrs[dlr] = [0, 0] if dlrs[dlr].nil?
    
    case type
    when 'SELL'
      max_pr = 0
      max_i = nil

      for i in (0...ordrs.length)
        dlr0, type0, cmd0, pr0 = ordrs[i]
        if dlr0 != dlr && type0 != type && cmd0 == cmd && pr0 >= pr &&
           max_pr < pr0
          max_pr = pr0
          max_i = i
        end        
      end
      
      if ! max_i.nil?
        mpr = ((pr + max_pr) * 0.5).floor
        #p [max_i] + ordrs[max_i] + [mpr]
        cmds[cmd] = [0, INF, 0, 0] if cmds[cmd].nil?
        cmds[cmd][0] += 1
        cmds[cmd][1] = mpr if cmds[cmd][1] > mpr
        cmds[cmd][2] += mpr
        cmds[cmd][3] = mpr if cmds[cmd][3] < mpr

        dlrs[dlr][1] += mpr
        dlrs[ordrs[max_i][0]][0] += mpr

        ordrs.delete_at(max_i)
      else
        ordrs << [dlr, type, cmd, pr]
      end

    when 'BUY'
      min_pr = INF
      min_i = nil

      for i in (0...ordrs.length)
        dlr0, type0, cmd0, pr0 = ordrs[i]
        if dlr0 != dlr && type0 != type && cmd0 == cmd && pr0 <= pr &&
           min_pr > pr0
          min_pr = pr0
          min_i = i
        end        
      end
      
      if ! min_i.nil?
        mpr = ((pr + min_pr) * 0.5).floor
        #p [min_i] + ordrs[min_i] + [mpr]
        cmds[cmd] = [0, INF, 0, 0] if cmds[cmd].nil?
        cmds[cmd][0] += 1
        cmds[cmd][1] = mpr if cmds[cmd][1] > mpr
        cmds[cmd][2] += mpr
        cmds[cmd][3] = mpr if cmds[cmd][3] < mpr

        dlrs[dlr][0] += mpr
        dlrs[ordrs[min_i][0]][1] += mpr

        ordrs.delete_at(min_i)
      else
        ordrs << [dlr, type, cmd, pr]
      end
    end
  end
  #p cmds
  #p dlrs

  for cmd in cmds.keys.sort
    num, min, sum, max = cmds[cmd]
    ave = (sum.to_f / num).to_i
    puts [cmd, min, ave, max].join(' ')
  end
  puts '-' * 2

  for dlr in dlrs.keys.sort
    puts ([dlr] + dlrs[dlr]).join(' ')
  end
  puts '-' * 10
end

Measured memory_bytes: 6120
#include<stdio.h>
int main(void){
  int N,i,j,bcount=0,b2,bcheck=0;
  scanf("%d",&N);
  int a[N],ball[N];
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
  }
  for(i=(N/2)+1;i<=N;i++){
    ball[i-1]=a[i-1];
    if(a[i-1]==1){
      bcount++;
    }
  }
  for(i=(N/2);i>=1;i--){
    bcheck=0;
    for(j=i*2;j<=N;j=i+j){
      if(ball[j-1]==1){
        bcheck++;
      }
    }
    if((bcheck%2)==a[i-1]){
      ball[i-1]=0;
    }
    else{
      ball[i-1]=1;
      bcount++;
    }
  }
  printf("%d\n",bcount);
  for(i=0;i<N;i++){
    if(ball[i]==1){
      printf("%d ",i+1);
    }
  }
  return 0;
}

Measured memory_bytes: 2432
use std::io::prelude::*;

fn input<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn with_stdout_lock<F: FnOnce(std::io::BufWriter<std::io::StdoutLock>)>(f: F) {
    let out = std::io::stdout();
    let w = std::io::BufWriter::new(out.lock());
    f(w);
}

fn main() {
    let n: usize = input();
    let xy: Vec<(i64, i64)> = (0..n).map(|_| (input(), input())).collect();

    let ok = xy.windows(2).all(|p| {
        let (p0, p1) = (p[0], p[1]);
        let p0 = p0.0.abs() + p0.1.abs();
        let p1 = p1.0.abs() + p1.1.abs();
        p0 % 2 == p1 % 2
    });
    if !ok {
        println!("-1");
        return;
    }

    let mx = xy.iter().map(|&(x, y)| x.abs() + y.abs()).max().unwrap();
    let mut k = 1;
    let mut a = vec![1];
    while k < mx {
        k *= 2;
        a.push(k);
    }
    if mx % 2 == 0 {
        a.push(1);
    }
    a.sort_by_key(|&a| -a);

    let mut ans = vec![];
    for &(x, y) in &xy {
        let mut temp = String::new();
        let goal = (x, y);
        let mut cur = (0, 0);
        for &a in &a {
            if i64::abs(goal.0 - cur.0) > i64::abs(goal.1 - cur.1) {
                if goal.0 > cur.0 {
                    temp.push('R');
                    cur.0 += a;
                } else {
                    temp.push('L');
                    cur.0 -= a;
                }
            } else {
                if goal.1 > cur.1 {
                    temp.push('U');
                    cur.1 += a;
                } else {
                    temp.push('D');
                    cur.1 -= a;
                }
            }
        }
        ans.push(temp);
    }

    with_stdout_lock(|mut w| {
        writeln!(w, "{}", a.len()).unwrap();
        for i in 0..a.len() {
            write!(w, "{}{}", a[i], if i == a.len() - 1 { '\n' } else { ' ' }).unwrap();
        }
        for ans in ans {
            writeln!(w, "{}", ans).unwrap();
        }
    });
}


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

int main(){
    int n;
    cin>>n;
    for(int i=n;i;i++){
        bool flag=false;
        for(int j=2;j<=(i/j);j++){
            if(i%j==0) {
                flag=true;
                break;
            }
        }
        if(flag==false){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
//=n(}*,4e@;;j|)IK&EYzf7BN%w+xK:///RAIYAN_MAHIN
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n; cin >> n; ll a[n + 10];
    set<ll >rm;
    for(ll i = 0; i < n; i++)
    {
        cin >> a[i];
        rm.insert(a[i]);
    }
       if(rm.size() == n)
       {
            cout << "YES";
           
       }
       else cout << "NO";
       
}

Measured memory_bytes: 11136
#include<cstdio>
 
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please
 
const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
 
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);
 
 
	int N = getint();
	
	int ikeru = 1;
	int h = -1;
	rep(i, N) {
		int H = getint();
		if (H > h) h = H - 1;
		else if (H < h) ikeru = 0;
	}
	
	if (ikeru) printf("Yes");
	else printf("No");
 
	Would you please return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

struct Result {
  int time, prob, No;
  Result () {
    time = prob = No = 0;
  }
  Result (int time, int prob, int No) : time(time), prob(prob), No(No) {}
};

bool comp(const Result &r1, const Result &r2) {
  
  if (r1.prob > r2.prob) {
    return true;
  } else if (r1.prob == r2.prob) {
    if (r1.time < r2.time) {
      return true;
    } else if (r1.time == r2.time) {
      return r1.No > r2.No;
    } else {
      return false;
    }
  } else {
    return false;
  }
  /*
  if (r1.prob == r2.prob) return r1.time < r2.time; 
  return r1.prob > r2.prob;
  */
}

int M, T, P, R, m, t, p, j, penalty[60][20];
Result r[60];

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

  while (cin >> M >> T >> P >> R, M | T | P | R) {
    memset(penalty, 0, sizeof(penalty));
    for (int i = 0; i < T; ++i) r[i] = Result(0, 0, i);
    for (int i = 0; i < R; ++i) {
      cin >> m >> t >> p >> j;

      if (j == 0) {
        r[t-1].prob++;
        r[t-1].time += m + penalty[t-1][p-1];
      }
      else {
        penalty[t-1][p-1] += 20;
      }
    }
    /*cerr << "==========" << endl;
    for (int i = 0; i < T; ++i) cout << r[i].No + 1<< " " << r[i].time << " " << r[i].prob << endl;
    */
    
    sort(r, r + T, comp);

    /*cerr << "==========" << endl;
      for (int i = 0; i < T; ++i) cout << r[i].No << " " << r[i].time << " " << r[i].prob << endl;*/
    /* */
    for (int i = 0; i < T; ++i) {
      if (i == 0) {
        cout << r[i].No+1;
      }
      else {
        if (r[i-1].time == r[i].time && r[i-1].prob == r[i].prob) {
          cout << "=";
        }
        else {
          cout << ",";
        }
        cout << r[i].No+1;
      }
    }
    cout << endl;
    /* */
  }

  return 0;
}

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

int main() {
string S,T,U;
int A,B;
cin >> S >> T>>A>>B>>U;
if(U==S) cout << A-1 << " " << B << endl;
if(U==T) cout << A << " " << B-1 << endl;
  return 0;
}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define allof(a) (a).begin(),(a).end()
template< typename T > using Vec = vector< T >;
template< typename T > void minUpdate(T& a, T b) { a = min(a, b); }

int main() {
	int N, M;
	cin >> N >> M;
	
	struct Edge { int to, c, id; };
	Vec< Vec< Edge > > edges(N, Vec< Edge >());
	
	Vec< Vec< int > > dst(N, Vec< int >(N, 1L << 28));
	for_(i,0,N) dst[i][i] = 0;
	
	for_(i,0,M) {
		int u, v, c;
		cin >> u >> v >> c;
		--u; --v;
		
		edges[u].push_back(Edge{v, c, i});
		edges[v].push_back(Edge{u, c, i});
		dst[u][v] = dst[v][u] = c;
	}
	
	for_(k,0,N) for_(i,0,N) for_(j,0,N) minUpdate(dst[i][j], dst[i][k] + dst[k][j]);
	
	Vec< int > used(M, 0);
	for_(s,0,N) for_(i,0,N) for (const Edge& e : edges[i]) if (dst[s][i] + e.c == dst[s][e.to]) used[e.id] |= 1;
	cout << M - accumulate(allof(used), int()) << endl;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

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

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

static const int INF = 1e9+7;

int main() {
  int N;
  cin >> N;
  vector<int> B(N+1);
  rep(i, 1, N) {
    cin >> B[i];
  }
  B[0] = B[N] = INF;
  vector<int> A(N);
  rep(i, 0, N) {
    A[i] = min(B[i], B[i+1]);
  }

  int ans = 0;
  rep(i, 0, N) {
    ans += A[i];
  }

  cout << ans << endl;


};


Measured memory_bytes: 256
#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 <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

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

#include <iostream>

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

	if (D == 22) { cout << "Christmas Eve Eve Eve" << endl; }
	else if (D == 23) { cout << "Christmas Eve Eve" << endl; }
	else if (D == 24) { cout << "Christmas Eve" << endl; }
	else if (D == 25) { cout << "Christmas" << endl; }
}

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

int main() {

  int K,A,B;
  cin >> K >> A >> B;
  bool flag = 0;

  for (int i = A; i < B+1 ; i++) {
    if (i%K==0) flag = 1;
  }
  if(flag)cout << "OK" << endl;
  else cout  << "NG" << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

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

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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	int N, M, Asum = 0, A; cin >> N >> M;
	REP(i, M){
		cin >> A; Asum += A;
	}
	N -= Asum;
	cout << ((N < 0) ? -1 : N) << ln;
}

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

using namespace std;

#define LOG(...) fprintf(stderr,__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main() {
    int n;
    cin >> n;
    REP(i, n) {
        int y, m, d;
        cin>>y>>m>>d;

        int cnt;
        if (m % 2 == 0) {
            if (y % 3 == 0) {
                cnt = 21 - d;
            } else {
                cnt = 20 - d;
            }
        } else {
            cnt = 21 - d;
        }
        m++;
        while (1) {
            if (m == 11) {
                m = 1;
                y++;
            }
            if (y == 1000 && m == 1) break;
            if (y % 3 == 0) {
                cnt += 20;
            } else {
                if (m % 2 == 0) {
                    cnt += 19;
                } else {
                    cnt += 20;
                }
            }
            m++;
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 1160
#include <iostream>

int main() {

    char input;
    scanf("%c", &input);
    if (input == 'a' || input == 'i' || input == 'u' || input == 'e' || input == 'o') {
        std::cout << "vowel" << std::endl;

    } else {
        std::cout << "consonant" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
ll n,a[N][5],b[N][5],c[N][5],ji,cheng[N];
string s;
int main()
{
	cin>>s;
	s=' '+s;
	cheng[0]=1;
	for(int i=1;i<=1e5;i++)
	{
		cheng[i]=cheng[i-1];
		cheng[i]=cheng[i]*3%mod;
	}
	for(int i=0;i<s.size();i++)if(s[i]=='?')ji++;
	for(int i=1;i<s.size();i++)
	{
		for(int j=0;j<=3;j++)
		{
			a[i][j]=a[i-1][j];
			b[i][j]=b[i-1][j];
			c[i][j]=c[i-1][j];
		}
		if(s[i]=='A')a[i][0]++;
		if(s[i]=='B')b[i][0]+=a[i-1][0],b[i][1]+=a[i-1][1];
		if(s[i]=='C')
		{
			c[i][0]+=b[i-1][0]*cheng[ji]%mod;
			if(ji>=1&&b[i-1][1])c[i][1]+=b[i-1][1]*cheng[ji-1]%mod;
			if(ji>=2&&b[i-1][2])c[i][2]+=b[i-1][2]*cheng[ji-2]%mod;
		}
		if(s[i]=='?')
		{
			a[i][1]++;
			b[i][1]+=a[i-1][0];
			b[i][2]+=a[i-1][1];
			c[i][1]+=b[i-1][0]*cheng[max(ji-1,(ll)0)]%mod;
			c[i][2]+=b[i-1][1]*cheng[max(ji-2,(ll)0)]%mod;
			c[i][3]+=b[i-1][2]*cheng[max(ji-3,(ll)0)]%mod;
		}
		for(int j=0;j<=3;j++)
		{
			a[i][j]%=mod;
			b[i][j]%=mod;
			c[i][j]%=mod;
		}
	}
	int len=s.size()-1;
	ll ans=c[len][0]+c[len][1]+c[len][2]+c[len][3];
	ans%=mod; 
	cout<<ans<<endl;
	return 0;
}
/*
*/

Measured memory_bytes: 12924
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;
long long add_mod(long long a,long long b){
	long long re = (a%mod)+(b%mod);
	return re%mod;
}
long long mul_mod(long long a,long long b){
	long long re = (a%mod)*(b%mod);
	return re%mod;
}

//return = a - b;
long long sub_mod(long long a,long long b){
	long long re;
	if(a%mod < b%mod){
		re = (a%mod)+mod - (b%mod);
	}
	else{
		re = (a%mod) - (b%mod);
	}
	return re;
}

int main(void){
    int n;
    cin>>n;
    long long a[n+1];
    long long b[n+1];
    for(int i = 1; i < n+1; i++) b[i] = 0;
    b[0] = 0;
    long long all = 0;
    for(int i = 1; i < n+1; i++){
        cin>>a[i];
        b[i] = add_mod(a[i], b[i-1]);
        all = add_mod(a[i],all);
    }
    long long ans,w;
    ans = 0;
    w = 0;
    long long sa;
    for(int i = 1; i < n; i++){
        sa = sub_mod(all,b[i]);
        w = mul_mod(sa,a[i]);
        ans = add_mod(w,ans);
    }

    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6764
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll t1,t2,a1,a2,b1,b2;cin>>t1>>t2>>a1>>a2>>b1>>b2;
    if(a1>b1){
        swap(a1,b1);
        swap(a2,b2);
    }
    ll a=a1*t1+a2*t2,b=b1*t1+b2*t2;
    if(a==b){
        cout<<"infinity"<<endl;
        return 0;
    }
    if(a>b){
        ll res=((b1-a1)*t1)/(a-b);
        res*=2;
        if(((b1-a1)*t1)%(a-b)!=0)res++;
        cout<<res<<endl;
    }else{
        cout<<0<<endl;
    }
}


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

using namespace std;
struct poz
{
    int val, reducere=1e9;
} a[100005];
int mini,ans,nrf,nrm,m,i,x,y,c;
int b[100005];
int main()
{
    cin>>nrf>>nrm>>m;
    for(i=1;i<=nrf;i++)
        cin>>a[i].val;

    mini=1e9;
    for(i=1;i<=nrm;i++)
    {
        cin>>b[i];
        mini=min(mini, b[i]);
    }


    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        a[x].reducere=min(a[x].reducere, b[y]-c);
    }

    ans=1e9;
    for(i=1;i<=nrf;i++)
        ans=min(ans, a[i].val + min(mini, a[i].reducere));
    cout<<ans;
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  string S;
  cin >> N>>K>>S;
  if(S.at(K-1)=='A')
    S.at(K-1)='a';
  if(S.at(K-1)=='B')
    S.at(K-1)='b';
  if(S.at(K-1)=='C')
    S.at(K-1)='c';
 
  cout << S << endl;
}


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

int main() {
  int N;
  cin >> N;
  int num =0;

  for (int i=0; i<N; i++) {
      int l,r;
      cin >> l >> r;

      num += r-l+1;
   }

   cout << num << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define f first
#define s second
#define int long long
int c[222222],s[222222];
signed main(){
	ic(n)
	rep(0,i,n){
		cin>>s[i];
		cin>>c[i];
	}
	int ans=0;
	rep(0,i,n){
		ans+=c[i];
	}
	int disu=0;
	rep(0,i,n){
		disu+=c[i]*s[i];
	}
	ans+=(disu-1)/9;
	c(ans-1)			
}	

Measured memory_bytes: 3328
//Think simple yet elegant
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
const ll maxn=2e6+10;
const ll mod=1e9+7;

int main(){
	fast;
	ll a,b,n;
	cin>>a>>b>>n;
	ll k1=min(b-1,n);
	ll k2=a%b;
	ll k3=(k2*k1)%b;
	ll k4=(a*k1-k3)/b;
	cout<<k4;
	
}

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

int top = 0, S[1000];

void push(int x) {
  S[++top] = x;
}

int pop(void) {
  top--;
  return S[top+1];
}

int main(void) {
  int a, b;
  top = 0;
  char s[100];
  while(scanf("%s",s) != EOF) {
    if(s[0] == '+') {
      a = pop();
      b = pop();
      push(a + b);
    } else if(s[0] == '-') {
      b = pop();
      a = pop();
      push(a - b);
    } else if(s[0] == '*') {
      a = pop();
      b = pop();
      push(a * b);
    } else {
      push(atoi(s));
    }
  }
  printf("%d\n",pop());

  return 0;
}


Measured memory_bytes: 2036
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF_MAX = 1e9, MOD = 1000000007;

const ll INF = 1e18;

bitset <10000> u;

ll d[26], n, ans;

string s;

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

	for (int i = 0; i < n; i++)
	{
		d[s[i] - 'a']++;
	}

	ans = 1;

	for (int i = 0; i < 26; i++)
	{
		ans = ans * (d[i] + 1) % MOD;
	}

	cout << (ans + MOD - 1) % MOD << endl;
}

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

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

const int MAXN = 200010;

int n;

int v[MAXN];

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

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

	int x = 0;

	for(int i = 1 ; i <= n ; i++)
		x ^= v[i];

	for(int i = 1 ; i <= n ; i++)
		printf("%d ",x^v[i]);
}

Measured memory_bytes: 4596
a, b, c, d = list(input())

import itertools

for ops in itertools.product(["+", "-"], repeat=3):
    eq = a + ops[0] + b + ops[1] + c + ops[2] + d
    sol = eval(eq)
    if sol == 7:
        break

ans = eq + "=7"
print(ans)


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

int a,b,c,d;
int main() {
  cin >> a >> b >> c >> d;
  if((a+b)>(c+d)){
    cout << "Left" << endl;
  }
  else if((a+b)<(c+d)){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
  }

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

const pid_t pid = getpid();
// Problem Specific Parameter:
using edge = struct{int to,cost;};
vector<edge> graph[30];

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

	int head = 0;
	while(((L + 1) >> head)) head++;
	//cout << head << endl;

	const int n = head;
	rep(i,n-1){
		graph[i].push_back({i+1,0});
		graph[i].push_back({i+1,(1<<i)});
	}

	vector<int> vertex(n,0);
	rep(i,n) vertex[i] = (1 << i) - 1;

	int lft = (1 << (n-1)), rht = L;

	rrep(i,n-1){
		const int val = (1 << i);
		const int len = rht - lft;
		if(len >= vertex[i]){
			graph[i].push_back({n-1,lft});
			lft += vertex[i] + 1;
		}
	}

	int m = 0;
	rep(i,n) m += graph[i].size();
	cout << n << " " << m << endl;
	rep(i,n) for(auto &e:graph[i]) cout << i + 1 << " " << e.to + 1 << " " << e.cost << endl;

	return 0;
}

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

int main() {
    ll N, X;
    cin >> N >> X;
    vector<ll> L(N);
    rep(i, N) cin >> L[i];
    ll ans = 1, prev = 0;
    for (ll l : L) {
        if (prev + l <= X) ans++;
        prev += l;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def hoge():
    X = int(input())
    for a in range(0,int(X**(1/5))+1):
        for b in range(0,a+1):
            if a**5+b**5 == X:
                return (a,-b)
    for a in range(int(X**(1/5)),10**9):
        for b in range(0,a+1):
            if a**5-b**5 == X:
                return (a,b)


result = hoge()
print(result[0], result[1])       


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

int main(){
    ll N;
    cin >> N;
    ll zero = 0, two = 0, odd = 0;
    rep(i, 0, N){
        ll a;
        cin >> a;
        if(a % 4 == 0) zero++;
        if(a % 4 == 2) two++;
        if(a % 2 == 1) odd++;
    }
    two = min(1LL, two);
    if(two + odd > zero + 1){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll long long
#define double long double
#define MAX (int)(2*pow(10,5) + 10)
#define N 100000
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,18);
ll modulo = inf;
double eps = 1e-10;
ifstream in;
ofstream out;

void deal(){
	ll n ;
	cin>>n;
	vector<ll> to[2];
	vector<ll> arr(n);
	fori(n){
		ll ed;
		cin>>ed;
		arr[i] = ed;
		to[(ed>=0)].pb(ed);
	}
	swap(to[0], to[1]);
	fori(2)
		sort(to[i].begin(), to[i].end());
	reverse(to[1].begin(),to[1].end());
	if(to[0].size() && to[1].size()){
		ll s = 0;
		for(auto& el: arr)
			s+=fabs(el);
		cout<<s<<'\n';
		while(to[0].size() > 1){
			ll lst = to[0][to[0].size()-1];
			cout<<to[1][0]<<' '<<lst<<'\n';
			to[1][0]-=lst;
			to[0].erase(to[0].end()-1);
		}
		while(to[1].size()){
			ll lst = to[1][to[1].size()-1];
			cout<<to[0][0]<<' '<<lst<<'\n';
			to[0][0]-=lst;
			to[1].erase(to[1].end()-1);
		}
	}
	else if(to[0].size()){
		ll s = -to[0][0];
		for(ll i =1 ;i<to[0].size(); i++)
			s+=to[0][i];
		cout<<s<<'\n';
		for(ll i = 2; i<to[0].size(); i++){
			cout<<to[0][0]<<' '<<to[0][i]<<'\n';
			to[0][0] -= to[0][i];
		}
		cout<<to[0][1]<<' '<<to[0][0]<<'\n';
	}
	else{
		ll s = to[1][0];
		for(ll i =1 ;i<to[1].size(); i++)
			s-=to[1][i];
		cout<<s<<'\n';
		for(ll i = 2; i<to[1].size(); i++){
			cout<<to[1][0]<<' '<<to[1][i]<<'\n';
			to[1][0] -= to[1][i];
		}
		cout<<to[1][0]<<' '<<to[1][1]<<'\n';
	}
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

/*

5
-3 -2 -6 -1 -5

*/

Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <list>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <iomanip>
#include <queue>
#include <map>
int main()
{

	double A, B;

	std::cin >> A >> B;

	double K;

	K = (A + B) / 2;

	if (ceil(K) != floor(K)) {
		std::cout << "IMPOSSIBLE";
	}
	else {
		std::cout << int(K);

	}



}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <deque>
#include <utility>
#include <set>
#include <climits>
#include <cstring>
#include <map>
using namespace std;

#define fi(i, a, b) for(int i = a; i < b; i++)
#define pb(x) push_back(x)
#define ll long long
#define ii pair<int, int>
#define pii pair< pair<int, int>, int>



int main()
{

	vector<int> terms, divisors;
	int n, a, b;
	ll res = 0;
	cin >> n;
	fi(i, 0, n)
	{
		cin >> a >> b;
		terms.push_back(a);
		divisors.push_back(b);
	}

	for (int i = n - 1; i >= 0; i--)
	{
		if ((terms[i] + res) % divisors[i] != 0)
		{
			ll tmp = (terms[i]+res)/divisors[i];
			if (tmp*divisors[i] != terms[i] + res)
				tmp++;
			/*while (terms[i] + res > tmp)
				tmp += divisors[i];*/
			ll incr = tmp*divisors[i] - terms[i] - res;
			res += incr;
		}
	}

	cout << res;
	return 0;
}

Measured memory_bytes: 1276
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <map>
using namespace std;
const int maxn = 100007;
int n,sum;
int a,b,c;
int main()
{
	cin>>n>>sum;
	sum = sum/1000;
	int ok = 0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n-i;j++)
		{
			int k = n-i-j;
			int now =10*i+5*j+k;
			if(now==sum)
			{
				ok = 1;
				cout<<i<<" "<<j<<" "<<k<<endl;
				break;
			}
		}
		if(ok)break;
	}
	if(ok==0)cout<<-1<<" "<<-1<<" "<<-1<<endl;
}

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


int main(){
  #define int long long


  int n;
  cin >> n;
  
  int m= n/2;
  
  vector <int> a(n);
  
  rep(i,n)
    cin >> a.at(i);
  
  vector <int> b(n);
    b=a;
  sort(b.begin(),b.end());

  
  rep(i,n){
    if(a.at(i)<=b.at(m-1))
      cout << b.at(m) << endl;
    else
      cout << b.at(m-1) << endl;
  }
  
}

Measured memory_bytes: 6280
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MAX 130
using namespace std;

bool dp[MAX][MAX][2];
 
int main()
{
  int T;
  while(cin >> T)
    {
      while(T--)
	{
	  rep(i,MAX)rep(j,MAX)rep(l,2)dp[i][j][l] = false;
	  int N;
	  cin >> N;
	  int input[N];
	  rep(i,N) cin >> input[i];
       
	  if(N <= 2)
	    {
	      cout << input[N-1] << endl;
	      continue;
	    }
       
	  int ans = input[N-1];
 
	  REP(cur,1,N-1)
	    {
	      dp[input[cur-1]][input[cur]][cur&1] = true;
	      int R = input[cur+1];
	      rep(L,MAX)
		{
		  rep(M,MAX)
		    {
		      if(!dp[L][M][cur&1])continue;
		      //cout << cur << " cur(" << L << "," << M << "," << R << ")\n";
		      if(M == 0)
			{
			  if(cur+2 < N)
			    {
			      dp[M][R][(cur+1)&1] = true;
			      //cout << cur << " next ( " << M << "," << R << "," << input[cur+2] << ")\n";
			    }
			  else       ans = max(ans,R);
			}
		      else
			{
			  if(cur+2 < N)
			    {
			      dp[M][R][(cur+1)&1] = true;
			      //cout << cur << " next ( " << M << "," << R << "," << input[cur+2] << ")\n";
			      dp[M-1][R+L][(cur+1)&1] = true;
			      //cout << cur << " next ( " << M-1 << "," << R+L << "," << input[cur+2] << ")\n";
			    }
			  else 
			    {
			      ans = max(ans,R+L);
			      //cout << cur << " ans : " << R << "+" << L << "=" << R+L <<  " (" << L << "," << M << "," << R << ")" <<  endl;
			    }
			}
		    }
		}
	      rep(i,MAX)rep(j,MAX)dp[i][j][cur&1] = false;
	    }
	  
	  cout << ans << endl;      
	}
    }
  return 0;
}

Measured memory_bytes: 1192
import sys
readline = sys.stdin.buffer.readline
# ord('.') == 46

def main():
    H, W = map(int, readline().split())
    a = readline()
    k = a.find(b'#')
    if k == -1:
        k = W
    v = [1] * k + [0] * (W - k)

    for m in range(1, H):
        a = readline()
        v[0] = t = v[0] if a[0] == 46 else 0
        if m % 80 == 0:
            for j, u, aa in zip(range(1, W), v[1:], a[1:W]):
                v[j] = t = (u + t) % 1000000007 if aa == 46 else 0
        else:
            for j, u, aa in zip(range(1, W), v[1:], a[1:W]):
                v[j] = t = (u + t) if aa == 46 else 0
    print(v[-1] % 1000000007)


main()


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

ll GCD(ll x, ll y) {
    if (x % y == 0) return y;
    else return GCD(y, x % y);
}

ll LCM(ll x, ll y) {
    return x * y / GCD(x, y);
}

int main() {
    ll a, b, c, d; cin >> a >> b >> c >> d;
    ll c_num = b/c - (a-1)/c;
    ll d_num = b/d - (a-1)/d;
    ll cd_num = b/LCM(c, d) - (a-1)/LCM(c, d);
    cout << b - a + 1 - c_num - d_num + cd_num << endl;
}


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

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORTASC(c) sort((c).begin(),(c).end())
#define SORTDESC(c,t) sort((c).begin(),(c).end(), std::greater<t>());
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define VMAX(a) *max_element(ALL(a))
#define VMIN(a) *min_element(ALL(a))
#define OUT(a) cout << (a) << endl;
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double PI  = acos(-1.0);

template <class T, class S>
using umap = std::unordered_map<T, S>;
using ll = long long;
using namespace std;

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

  	cout << setprecision(10) << 2*PI*n << endl;

    return 0;
}

Measured memory_bytes: 3800
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
int MOD=1000000007;

int main(){
	int x,y,ans=MOD; cin >> x >> y;
    if(-x<=y) ans=min(ans,y-(-x)+1);
    if(x<=y) ans=min(ans,y-x);
    if(x<=-y) ans=min(ans,-y-x+1);
    if(-x<=-y) ans=min(ans,-y+x+2);
	cout << ans << endl;
	}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int N, Q;
Graph G;

void dfs(int v, int p, vector<ll> &res) {
    if (p != -1) res[v] += res[p];
    for (auto e : G[v]) {
        if (e == p) continue;
        dfs(e, v, res);
    }
}

int main() {
    cin >> N >> Q;
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<ll> val(N, 0);
    for (int i = 0; i < Q; ++i) {
        int p, x;
        cin >> p >> x;
        --p;
        val[p] += x;
    }
    dfs(0, -1, val);
    for (auto v : val) cout << v << " ";
    cout << endl;
}

Measured memory_bytes: 25060
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	m := getNextInt(scanner)
	fw := makeGrid(n, n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i == j {
				continue
			}
			fw[i][j] = math.MaxInt32
		}
	}
	aa := make([]int, m)
	bb := make([]int, m)
	cc := make([]int, m)
	for i := 0; i < m; i++ {
		aa[i] = getNextInt(scanner) - 1
		bb[i] = getNextInt(scanner) - 1
		cc[i] = getNextInt(scanner)
		fw[aa[i]][bb[i]] = cc[i]
		fw[bb[i]][aa[i]] = cc[i]
	}
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if fw[i][j]-fw[i][k] > fw[k][j] {
					fw[i][j] = fw[i][k] + fw[k][j]
				}
			}
		}
	}
	var ans int
	for k := 0; k < m; k++ {
		if fw[aa[k]][bb[k]] < cc[k] {
			ans++
		}
	}
	fmt.Fprintln(writer, ans)
}

func makeGrid(h, w int) [][]int {
	index := make([][]int, h, h)
	data := make([]int, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}


Measured memory_bytes: 1944
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn check(w: Vec<u32>, n: usize, k: usize, p: u32) -> bool {
    let mut idx: usize = 0;

    for _i in 0..k {
        let mut sum: u32 = 0;
        while w[idx] + sum <= p {
            sum += w[idx];
            idx += 1;
            if idx == n {
                return true;
            }
        }
    }
    false
}

fn main() {
    let n: usize = read();
    let k: usize = read();

    let w: Vec<u32> = (0..n).map(|_| read::<u32>()).collect();

    let mut left: usize = 0;
    let mut right: usize = 100000 * 10000;
    while right - left > 1 {
        let mid: usize = (left + right) / 2;
        if check(w.clone(), n, k, mid as u32) {
            right = mid;
        } else {
            left = mid;
        }
    }

    println!("{}", right)
}



Measured memory_bytes: 5052
#include<cstdio>

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

using namespace std;

void rot(char &a,char &b,char &c,char &d){
	char t;
	t=a;
	a=b;
	b=c;
	c=d;
	d=t;
}

int main(){
	char net[6][9]={
		"..rr....",
		"..rr....",
		"ggyybbww",
		"ggyybbww",
		"..oo....",
		"..oo...."
	};

	for(char c;~(c=getchar());){
		switch(c){
			case 'U':
				rot(net[0][2],net[1][2],net[1][3],net[0][3]);
				rot(net[2][0],net[2][2],net[2][4],net[2][6]);
				rot(net[2][1],net[2][3],net[2][5],net[2][7]);
				break;
			case 'F':
				rot(net[2][2],net[3][2],net[3][3],net[2][3]);
				rot(net[2][4],net[1][2],net[3][1],net[4][3]);
				rot(net[3][4],net[1][3],net[2][1],net[4][2]);
				break;
			case 'R':
				rot(net[2][4],net[3][4],net[3][5],net[2][5]);
				rot(net[3][3],net[5][3],net[2][6],net[1][3]);
				rot(net[2][3],net[4][3],net[3][6],net[0][3]);
				break;
			case 'D':
				rot(net[4][2],net[5][2],net[5][3],net[4][3]);
				rot(net[3][6],net[3][4],net[3][2],net[3][0]);
				rot(net[3][7],net[3][5],net[3][3],net[3][1]);
				break;
			case 'B':
				rot(net[2][6],net[3][6],net[3][7],net[2][7]);
				rot(net[2][5],net[5][3],net[3][0],net[0][2]);
				rot(net[3][5],net[5][2],net[2][0],net[0][3]);
				break;
			case 'L':
				rot(net[2][0],net[3][0],net[3][1],net[2][1]);
				rot(net[2][2],net[0][2],net[3][7],net[4][2]);
				rot(net[3][2],net[1][2],net[2][7],net[5][2]);
				break;
		}
	}

	rep(i,6) puts(net[i]);

	return 0;
}

Measured memory_bytes: 916
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

cnt = 0
history = []

for h in range(H-1):
    for w in range(W):
        if A[h][w] == 0:
            continue
        if A[h][w] % 2 == 0:
            continue
        A[h][w] -= 1
        A[h+1][w] += 1
        cnt += 1
        history.append([h, w, h+1, w])

for w in range(W-1):
    if A[H-1][w] == 0:
        continue
    if A[H-1][w] % 2 == 0:
        continue
    A[H-1][w] -= 1
    A[H-1][w+1] += 1
    cnt += 1
    history.append([H-1, w, H-1, w+1])

print(cnt)
for fy, fx, ty, tx in history:
    print(fy+1, fx+1, ty+1, tx+1)


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

int main(void)
{
        int n,c,oomoji;
        int i;
        char s[12];

        scanf("%s",s);

        n = strlen(s);

        i=0;
        oomoji = 0;
        while(s[i]!='\0'){
                if(s[i]>='A' && s[i]<='Z')
                        oomoji++;
                i++;
        }
        if(oomoji!=2){
                printf("WA\n");
                return 0;
        }
        if(s[0]!='A'){
                printf("WA\n");
                return 0;
        }
       c = 0;
        i = 2;
        while(i<n-1){
                if(s[i]=='C')
                        c++;
                i++;
        }
        if(c==0 || c>1){
                printf("WA\n");
                return 0;
        }
        printf("AC\n");
        return 0;
}


Measured memory_bytes: 128
class DisjointSets

  def initialize(n)
    @p = Array.new(n)
    @rank = Array.new(n)
    n.times do |i|
      make_set(i)
    end
  end

  def make_set(x)
    @p[x] = x
    @rank[x] = 0
  end

  def same?(x, y)
    find_set(x) == find_set(y)
  end

  def find_set(x) 
    if x != @p[x]
      @p[x] = find_set(@p[x])
    end
    @p[x]
  end

  def unite(x, y)
    link(find_set(x), find_set(y))
  end

  def link(x, y) 
    if @rank[x] > @rank[y]
      @p[y] = x
    else
      @p[x] = y
      if (@rank[x] == @rank[y])
        @rank[y] += 1
      end
    end
  end
end

n, q = gets.split.map(&:to_i)
ds = DisjointSets.new(n)
q.times do
  com, x, y = gets.split.map(&:to_i)
  case com
  when 0
    ds.unite(x, y)
  when 1
    puts ds.same?(x, y) ? 1 : 0
  end
end




Measured memory_bytes: 8904
from collections import Counter

s = input()

c = Counter(s)

if len(c.values()) == 1:
    if len(s) == 1:
        ans = "YES"
    else:
        ans = "NO"

elif len(c.values()) == 2:
    if len(s) == 2:
        ans = "YES"
    else:
        ans = "NO"

else:
    cnt = sorted(c.values())
    bl1 = cnt[0] == cnt[1] == cnt[2]
    bl2 = cnt[0] == cnt[1] == cnt[2] - 1
    bl3 = cnt[0] == cnt[1] - 1 == cnt[2] - 1
    if bl1 or bl2 or bl3:
        ans = "YES"
    else:
        ans = "NO"

print(ans)


Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}
///////////////////////////


ll H, W, K;

ll c(ll a) {
	if (a <= 0) { return 1; }
	if (a <= 1) { return 2; }
	if (a == 2) { return 3; }
	if (a == 3) { return 5; }
	if (a == 4) { return 8; }
	if (a == 5) { return 13; }
	if (a == 6) { return 21; }
}

ll kuji(ll a, ll b) {
	if (abs(a - b) > 1) { return 0; }

	if (a == b) { return c(a - 2)*c(W - 1 - a); }

	if (b == a + 1) { return c(a - 2)*c(W - 1 - b); }

	if (a == b + 1) { return c(b - 2)*c(W - 1 - a); }

}


int main() {

	
	cin >> H >> W >> K;

	ll dp[200][10] = {};

	dp[0][1] = 1;

	repn(i, H) {
		repn(j, W) {
			repn(k, W) {
				dp[i][j] += dp[i-1][k] * kuji(k, j);
				
			}
			dp[i][j] %= MOD;
		}
	}

	cout << dp[H][K];
	

	system("PAUSE");
}

Measured memory_bytes: 504