akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>

using namespace std;
//DP用
template<class T> inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
const long long INF = 1LL << 60;

int count (int c,vector<int> &num) {
    int res = 0;
    for(int i: num) {
        if(i >= c-1) {
            res++;
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    // n!の素因数の個数
    vector<int> num(n+1,0);
    for(int i = 2; i < n+1; i++) {
        int a = i;
        for(int j = 2; j*j <= i; j++) {
            while(a % j == 0) {
                num[j]++;
                a /= j;
            }
        }
        if(a != 1) {
            num[a]++;
        }
    }
    cnt = count(75,num) + count(15,num) * (count(5,num)-1) + count(25,num) * (count(3,num)-1) + (count(3,num)-2) * count(5,num) * (count(5,num)-1)/2;
    cout << cnt;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int n;
  int a, b;
  cin >> n >> a >> b;
  int ca = 0;
  int cb = 0;
  int cc = 0;
  REP(i,n){
    int p;
    cin >> p;
    if(p <= a ) ++ca;
    else if(p > b) ++ cc;
    else ++ cb;
  }

  int ans = min({ca,cb,cc});
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3616
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
//priority_queue<int, vi, greater<int> > que;//昇順

using namespace std;

const int mod=1e9+7;

signed main(){
    SPEED;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << max(a*b,c*d) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll s, t, d;
    cin >> s >> t >> d;
    vector<ll> w(d);
    REP(i, d) cin >> w[i];

    ll sum = 0;
    REP(i, d) sum += w[i];

    auto check = [&](ll mid) {
        ll weight = s + (mid - 1) * sum; 
        REP(i, d) {
            weight += w[i];
            if(weight <= t) return true;
        }
        return false;
    };

    ll lb = 0, ub = 100100;
    while(ub-lb>1) {
        ll mid = (lb+ub)/2;
        if(check(mid)) ub = mid;
        else lb = mid;
    }

    {
        ll weight = s;
        REP(i, d) {
            weight += w[i];
            if(weight <= t) {
                cout << i+1 << endl;
                return 0;
            }
        }
    }

    if(ub == 100100) {
        cout << -1 << endl;
        return 0;
    }
    
    {
        ll weight = s + (ub - 1) * sum;
        REP(i, d) {
            weight += w[i];
            if(weight <= t) {
                cout << (ub-1)*d + i + 1 << endl;
                return 0;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 3636
from collections import defaultdict
N = int(input())
dic = defaultdict(int)
for i in range(N):
    s = input()
    dic[s] += 1
M = int(input())
for i in range(M):
    t = input()
    dic[t] -= 1
ans = max(dic.values())
print(max(0,ans))


Measured memory_bytes: 3316
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

int n,w,h;

inline int read(){
    int x=0,f=1; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

struct edge{
	int x,y,w; edge(){}
	edge(int _x,int _y,int _w){x=_x,y=_y,w=_w;}
	bool operator <(const edge &a)const{return w>a.w;}
}e[maxn];

struct union_find_set{
	int fa[maxn<<1]; bool bo[maxn<<1];
	void init(){for (int i=1;i<=h+w;i++) fa[i]=i;}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	bool merge(int x,int y){
		x=find(x),y=find(y);
		if (x==y){if (bo[x]) return 0; else return bo[x]=1,1;}
		if (bo[x]&&bo[y]) return 0; fa[x]=y,bo[y]|=bo[x]; return 1;
	}
}u;

int main(){
	n=read(),h=read(),w=read(); u.init();
	for (int i=1;i<=n;i++){
		int x=read(),y=read(),z=read();
		e[i]=edge(x,y+h,z);
	}
	ll ans=0; sort(e+1,e+n+1);
	for (int i=1;i<=n;i++){
		int x=e[i].x,y=e[i].y,w=e[i].w;
		if (u.merge(x,y)) ans+=w;
	}
	printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
#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; }
using ll = long long;
const ll MOD=1e9+7;
const long long INF = 1LL<<60;

int main() {
    bool is_reversed = false;
    string s;
    cin >> s;
    int q;
    cin >> q;
    rep(i,q){
        int t;
        cin >> t;
        int f;
        char c;
        if(t==2){
            cin >> f >> c;
        }

        // 処理
        if(t==1){
            is_reversed = !is_reversed;
        }else if(t==2){
            if(is_reversed==false){
            if (f==1){
                s.insert(s.begin(),c);
            }else if(f==2){
                s.push_back(c);
            }
            }
            if(is_reversed==true){
            if (f==1){
                s.push_back(c);
            }else if(f==2){
                s.insert(s.begin(),c);
            }
            }
        }
    }

    if (is_reversed==true){
        reverse(s.begin(),s.end());
    }

    cout << s << endl;
}

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

using namespace std;



int main()

{

    long long n,m, b = -2;
    cin>>n;
    if(n==0)
    {


        cout<<"0"<<endl;
        return 0;
    }
    m = n;
    stack<int> s;
    while(n!=0)
    {
         int temp = (n%b);
         if(temp<0)
         {
            temp = 2+temp;
            n = (n/b)+1;
         }
         else
         {
             n = n/b;
         }
         s.push( temp );

    }

    while(!s.empty())
    {
        cout<<s.top();
        s.pop();
    }
    cout<<endl;



    return 0;
}


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

int N;

int main() {
  while (1) {
    scanf("%d", &N);
    if (N == 0) break;
    int counter = 0;
    for (int i = 1; i <= N / 2; i++) {
      for (int j = i + 1;; j++) {
        int sum = j * (j + 1) / 2 - (i - 1) * i / 2;
        if (sum > N) break;
        if (sum == N) counter++;
      }
    }
    printf("%d\n", counter);
  }
}



Measured memory_bytes: 2584
# 入力
N=int(input())

# 集計用変数
ans=0

for i in range(1,N+1):
  # 約数の個数
  c=0

  # 奇数の場合のみ見る
  if i%2==1:
    for j in range(1,i+1):
      # 割り切れたら約数
      if i%j==0:
        c+=1

    # ちょうど8個の場合はカウント
    if c==8:
      ans+=1

# 出力
print(ans)

Measured memory_bytes: 2940
#include <stdio.h>

int main(void)
{
	int w,h,x,y,r;
	
	int up,dn,left,right;
	
	scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
	
	up = y+r;
	dn = y-r;
	left = x-r;
	right = x+r;
	
	if(up > h || dn < 0 || left < 0 || right > w)
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
	}
	
	return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define Data_Nerd ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define files freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

const int N = 21;

bool arr[N][N];

ll memo[1 << N];

int main() {
	Data_Nerd

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

	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			cin >> arr[i][j];

	int num_of_ways = 1 << n;

	memo[0] = 1;

	for(int i = 0; i < num_of_ways; ++i) {
		int num_of_people = __builtin_popcount(i) - 1;

		for(int j = 0; j < n; ++j) {
			if((1 << j & i) and arr[num_of_people][j]) {
				memo[i] = (memo[i] + memo[i ^ (1 << j)]) % MOD;
			}
		}
	}

	cout << memo[num_of_ways - 1];
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P = pair<int,int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

signed main(){
  cout << fixed << setprecision(10);
  double n,m,d;
  cin >> n >> m >> d;
  if(d == 0){
    cout << 1*(m-1)/n << endl;
  }
  else{
    cout << 2*(n-d)*(m-1)/n/n << endl;
  }
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {

	static long MOD = 1_000_000_007;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		//int N = Integer.parseInt(sc.next());
		//long L = Long.parseLong(sc.next());

		Scanner sc = new Scanner(System.in);
		//char[] c = sc.next().toCharArray();
		int N = Integer.parseInt(sc.next());
		int[][] task = new int [N][2];
		for(int i=0; i<N; i++){
			task[i][0] = Integer.parseInt(sc.next());
			task[i][1] = Integer.parseInt(sc.next());
		}
		
		int INF = Integer.MAX_VALUE;
		int INF_MIN = -1000;//Integer.MIN_VALUE;
		
		Arrays.sort(task,(a,b)->Integer.compare(a[1], b[1]));
		
		int sum = 0;
		int space = 0;
		boolean flag = true;
		for(int i=0;i<N;i++){
			sum += task[i][0];
			space = task[i][1] - sum;
			if(space < 0){
				flag = false;
				break;
			}
		}
		
		if(flag){
			System.out.println("Yes");
			
		}else{
			System.out.println("No");
			
		}
		

		
		
	
		
		
	}
	static long lcm (long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return (c/b);
	}
}



Measured memory_bytes: 75248
object Main extends App {
  import scala.io.StdIn._
  val n = readInt()
  val crypt = readLine.trim
  val coordinate = crypt.foldLeft(Coordinate(0, 0)){
    case (pos, c) if 'A' to 'M' contains c ⇒ pos.copy(y = pos.y - 1)
    case (pos, c) if 'N' to 'Z' contains c ⇒ pos.copy(y = pos.y + 1)
    case (pos, c) if 'a' to 'm' contains c ⇒ pos.copy(x = pos.x + 1)
    case (pos, c) if 'n' to 'z' contains c ⇒ pos.copy(x = pos.x - 1)
    case _ ⇒ ???
  }
  println(math.abs(coordinate.x) + math.abs(coordinate.y))
  println(encrypt(coordinate))

  case class Coordinate(x: Int, y: Int) {
    def +(that: Coordinate): Coordinate = Coordinate(x + that.x, y + that.y)
  }
  def encrypt(coordinate: Coordinate): String = {
    coordinate match {
      case Coordinate(x, y) if x >= 0 && y >= 0 ⇒ "N" * y + "a" * x
      case Coordinate(x, y) if x >= 0 ⇒ "A" * -y + "a" * x
      case Coordinate(x, y) if x < 0 && y < 0 ⇒ "A" * -y + "n" * -x
      case Coordinate(x, y) ⇒ "N" * y + "n" * -x
    }
  }
}


Measured memory_bytes: 92340
#include <iostream>
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pii pair<ll , ll>
#define mpi make_pair
#define F first
#define S second
#define pb push_back

bool comp1(pii a , pii b)
{
    return atan2(a.S , a.F) < atan2(b.S , b.F) ;
}

int main()
{   
    //fastio;
    int n;
    cin>>n;

    vector<pii> curr;

    for(int i = 0 ;i<n;i++)
    {
        int a , b ;
        cin>>a>>b;
        if(a == 0 && b== 0)continue;
        curr.pb(mpi(a , b));
    }

    sort(curr.begin() , curr.end() , comp1);

    ll ans =0;
    ll x =0, y = 0;
    int siz= curr.size();
    ll temp;
    // for(int i = 0 ;i<siz;i++)cout<<curr[i].F<<" "<<curr[i].S<<endl;
    for(int i = 0 ;i<siz;i++)
    {
        x = curr[i].F;
        y = curr[i].S;
        int j =(i+1)%siz;
        temp =x*x+y*y;
        ans = max(temp, ans);
        while(j != i)
        {   
            x = x+curr[j].F;
            y = y+curr[j].S;
            temp = x*x + y*y;
            ans = max(temp , ans);
            j = (j+1)%siz;
        }
    }

    long double ret = sqrtl(ans);
    
    cout<<setprecision(30)<<ret<<endl; 

    return 0;
}


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

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

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

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

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

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

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

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

#[allow(unused_mut)]
fn main() {
    input! (
        s: String,
    );
    let n: usize = s.len();

    let keyence = "keyence".to_string();
    let mut ans = false;

    for i in 0..8 {
        let mut l = s.chars().take(i).collect::<String>();
        let mut r = s.chars().skip(i+n-7).take(7-i).collect::<String>();
        if format!("{}{}",l,r) == keyence {
            ans = true;
            break;
        }
    }


    if ans {println!("YES")} else {println!("NO")};
}


Measured memory_bytes: 4352
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
p = list(map(int, input().split()))
p = [(1+i)/2 for i in p]
# 累積和の配列sを作成する
s = [0] * (n+1)
for i in range(1,n+1):
    s[i] = s[i-1] + p[i-1]
max = -1 * float("inf")
for i in range(n-k+1):
    sum = s[k+i] - s[i]
    if max <= sum:
        max = sum
print(max)

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

typedef long long ll;
typedef unsigned long long ull;
typedef string st;
typedef double db;
typedef vector<long long> vecll;
typedef vector<char> vechar;
typedef vector<string> vecst;

int main(){
    ll N, L;
    cin >> N >> L;
    vecst S(N);
    for(auto& i : S) cin >> i;
    sort(S.begin(), S.end());
    st ans;
    for(auto& i : S) ans += i;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    //S[i]:i-2までに含まれる2017に似た奇数の個数
    int S[100010];
    S[3]=S[1]=0;

    int i=3,N,M,root_N,root_M,k,l;
    bool prime_N,prime_M;
    while(i<=100000){
        N=i,M=(i+1)/2,root_N=sqrt(N)/1;root_M=sqrt(M)/1;
        
        k=3;prime_N=true;
        while(k<=root_N){
            if(N%k==0){
                prime_N=false;
                break;
            }
            k+=2;
        }

        l=2;prime_M=true;
        while(l<=root_M){
            if(M%l==0){
                prime_M=false;
                break;
            }
            l++;
        }

        if(prime_N && prime_M)S[i+2]=S[i]+1;
        else S[i+2]=S[i];
        i+=2;
    }

    int Q;cin>>Q;
    int s,t;
    for(int i=0;i<Q;i++){
        cin>>s>>t;
        cout<<S[t+2]-S[s]<<endl;
    }
    return 0;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define fi first
#define se second
#define setpre(x) cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ cout << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 200005;

/* ...o(^-^)o... */

int main(){
    int n; cin >> n;
    vector<string> vec;
    rep(i, n){
        string s; cin >> s; vec.push_back(s);
    }
    rep(i, n) vec.push_back(vec[i]);

    int ans = 0;
    rep(k, n){
        bool isok = true;
        rep(i, n) rep(j, n){
            if(i >= j) continue;
            if(vec[i+k][j] != vec[j+k][i]) isok = false;
        }
        if(!isok) continue;
        ans += n;
    }
    
    out(ans);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n=s.size(),k=1e8;
    for(int i=0;i<n-2;i++)
    {
        int ans=(s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0');
        if(abs(ans-753)<k) k=abs(ans-753);
    }
    printf("%d\n",k);
}


Measured memory_bytes: 256
N,*A = $<.read.split.map(&:to_i)
R = [0]*N
L = [0]*N
(0...N).each{|i|
	R[i+A[i]] += 1 if i+A[i] < N
	L[i-A[i]] += 1 if 0 <= i-A[i]
}
p (0...N).sum{|i| R[i]*L[i] }


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

int main() {
  int K, X;
  cin >> K >> X;
  for (int i = X - K + 1 ;i < X + K; i++){
    cout << i;
    if (i == X + K -1){
      cout << endl;
    }
    else {
      cout << ' ';
    }
  }
}


Measured memory_bytes: 256
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
#define endl "\n";
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 10010010010010;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

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

    int R,G,B,N;cin >> R >> G >> B >> N;
    int ans = 0;
    for(int i = 0;i<=3000;i++){
        for(int j = 0;j<=3000;j++){
            int sum = R*i+G*j;
            int remain = N-sum;
            if(remain < 0) continue;
            if(remain == 0){
                ans++;
                continue;
            }
            if(remain % B == 0) ans++;
            else{
                continue;
            }
            //cout << i << " " << j << " " << remain/B << endl;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <math.h>
#include <assert.h>
#include <set>
#include <map>
#include <bitset>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <cstdio>
#include <fstream>
#include <stack>
#include <ctype.h>
#include <numeric>
#include <sstream>
#include <unistd.h>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <random>
#include <chrono>
#include <iomanip>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define debug(name) DEBUG(#name, (name))
template<typename T>
void DEBUG(string label, T value) {
    cerr << "[" << label << " = " << value << "]\n";
}

void solve(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    ll ans = 0;
    map<int,int> mp, mp2;
    for(int i = 0; i < n; ++i){
        int cur = arr[i] - i - 1;
        int cur2 = arr[i] + i + 1;
        ans += mp[cur] + mp2[cur2];
        mp[-arr[i]-(i+1)]++;
        mp2[(i+1)-arr[i]]++;
    }
    cout << ans << endl;
}
int main(int argv, char **argc){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}


Measured memory_bytes: 37928
import static java.lang.System.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		A(sc);
	}
	
	public static void A(Scanner sc) {
		int left =  0;
		int right = 0;
		for(int i=0;i<2;i++) {
			left += sc.nextInt();
		}
		for(int i=0;i<2;i++) {
			right += sc.nextInt();
		}
		if(left==right) out.println("Balanced");
		else if(left>right) out.println("Left");
		else out.println("Right");
	}
}


Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>
 
typedef long long ll;
typedef struct ways{
    ll A;
    ll B;
}way;

int acmp(const void* left, const void* right){
    if (((way *)left)->A > ((way *)left)->A) return 1;
	else if (((way *)left)->A < ((way *)left)->A) return -1;
	else return 0;
}
 
int main(){
    ll N,M,count,ans;
    ans = 0;
    scanf("%lld %lld",&N,&M);
    ll H[N];
    char flag[N];
    for(ll i = 0;i<N;i++){
        scanf("%lld ",&H[i]);
        flag[i] = 1;
    }
    way w[M];
    for(ll i = 0;i<M;i++) scanf("%lld %lld",&(w[i].A),&(w[i].B));
    qsort(w,M,sizeof(way),acmp);
    for(ll i = 0;i<M;i++){
        if(H[w[i].A-1] < H[w[i].B-1]) flag[w[i].A-1] = 0;
        else if(H[w[i].A-1] > H[w[i].B-1]) flag[w[i].B-1] = 0;
        else {
            flag[w[i].A-1] = 0;
            flag[w[i].B-1] = 0;
        }
    }
    for(ll i = 0;i<N;i++) ans += flag[i];
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 4664
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,i,s=0,a,b;
    cin>>t;
    for(i=0;i<t;i++)
    {
        cin>>a>>b;
        n=abs(a-b);
        s+=n+1;
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
int a,b;
scanf("%d %d", &a, &b);
int d,r;
  d = a/b;
  r = a%b;
double f;
  f = 1.0*a/b;
printf("%d %d %.8f\n", d, r, f);
return 0;
}



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

using namespace std;

int main() {
  int n, m;
  while (cin >> n >> m, n) {
    vector<pair<int, int>> vec(m);

    for (int i = 0; i < m; ++i)
      vec[i] = make_pair(i + 1, 0);

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        int tmp;
        cin >> tmp;
        vec[j].second += tmp;
      }
    }

    sort(vec.begin(), vec.end(), [](auto &a, auto &b) {
      return (a.second != b.second) ? a.second > b.second : a.first < b.first;
    });

    cout << vec[0].first;
    for (int i = 1; i < m; ++i)
      cout << " " << vec[i].first;
    cout << endl;
  }
}


Measured memory_bytes: 3092
from bisect import bisect_right

A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]

INF = 10 ** 18
s = [-INF] + s + [INF]
t = [-INF] + t + [INF]

for i in range(Q):
    b = bisect_right(s, x[i])
    d = bisect_right(t, x[i])
    res = INF
    for n in [s[b - 1], s[b]]:
        for m in [t[d - 1], t[d]]:
            d1 = abs(n - x[i]) + abs(m - n)
            d2 = abs(m - x[i]) + abs(n - m)
            res = min(res, d1, d2)
    print(res)


Measured memory_bytes: 86872
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main()
{
	int n,x;
	long long ans=0;
	vector<int> v;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> x;
		v.push_back(x);
	}
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			ans+=v[i]*v[j];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
box = [0] * n
ans = []
cnt = 0
for i in reversed(range(1, n + 1)):
    for j in range(1, (n // i) + 1):
        if box[i * j - 1] == 1:
            cnt += 1
    if cnt % 2 != a[i - 1]:
        ans.append(i)
        box[i - 1] = 1
    cnt = 0

print(len(ans))
print(' '.join(map(str, ans)))


Measured memory_bytes: 81384
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    int N,K;
    cin >> N >> K;
    if(N/2+N%2>=K)cout<< "YES";else cout << "NO";
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;


class Main{
    public static void main(String[] args){
        double EPS = 1e-6;
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            double a = in.nextDouble();
            double b = in.nextDouble();
            double c = in.nextDouble();
            double d = in.nextDouble();
            double e = in.nextDouble();
            double f = in.nextDouble();
            double x = (e * c - b * f) / (a * e - b * d);
            double y = (- c * d + a * f) / (a * e - b * d);
            System.out.printf("%.3f %.3f\n", x+EPS, y+EPS);
        }
    }
}

Measured memory_bytes: 18736
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

string S;

signed main(){
	cin>>S;
	string T;
	REP(i,S.size()){
		if(i<S.size()-1&&S.substr(i,2)=="BC"){
			T+='D';
			i++;
		}
		else{
			T+=S[i];
		}
	}
	int N=T.size();
	bool flag=false;
	int p=0;
	int ans=0;
	DEB(T)END
	REP(i,N){
		if(flag==false&&T[i]=='A'){
			flag=true;
			p=i;
		}
		else if(flag==true&&T[i]=='D'){
			ans+=i-p;
			p++;
		}
		else if(flag==true&&T[i]=='A'){}
		else{
			flag=false;
		}
	}
	cout<<ans<<endl;
	return 0;
}
//ADAD
//DADA
//DDAA

//ADACCBADDAADB
//DAACCBDADADAB
//DAACCBDDADAAB
//DAACCBDDDAAAB

Measured memory_bytes: 776
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
struct Unionfind {
  vector<int> size;
  vector<int> par;

  Unionfind( int n ) :  size(n, 1), par(n) {
    iota( par.begin() , par.end() , 0 );
  }

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

  bool unite( int x , int y ) {
    x = find(x);
    y = find(y);
    if ( x == y ) return false;

    if ( size[y] < size[x] ) swap( x , y );

    par[x] = y;
    size[y] += size[x];

    return true;
  }

  bool same( int x , int y ) {
    return find(x) == find(y);
  }
};
double dist(pair<int,int> a,pair<int,int> b)
{
  int x=a.first-b.first,y=a.second-b.second;
  double answer=x*x+y*y;
  answer=sqrt(answer);
  return answer;
}
int main(void)
{
  int n,m;
  cin >> n >> m;
  vector<pair<int,int> > pos(n);
  REP(i,n) cin >> pos[i].first >> pos[i].second;
  Unionfind uf(n);
  vector<tuple<double,int,int> > fence(m);
  REP(i,m){
    int p,q;
    cin >> p >> q;
    --p,--q;
    fence[i]=make_tuple(-dist(pos[p],pos[q]),p,q);
  }
  SORT(fence);
  double answer=0.0;
  for(auto x:fence){
    double negc,a,b;
    tie(negc,a,b)=x;
    if(!uf.unite(a,b)) answer+=-negc;
  }
  cout << fixed << setprecision(10) << answer << endl;

}

Measured memory_bytes: 3372
#include<bits/stdc++.h>
using namespace std;
bool cmp(int k,int l){
	return k>l;
}
int main() {
	long long int n,m;
	cin>>n>>m;
	long long int a[n+1],sum=0;
	a[0]=1e9;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sort(a+1,a+n+1,cmp);
	double least=sum*(1.0/(4*m));
	if(a[m]>=least){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	return 0;
}


Measured memory_bytes: 256
fn main() {
    let mut len = 0;
    let mut count_s = 0;

    let mut input = String::new();
    std::io::stdin().read_line(&mut input).ok();

    for ch in input.trim_right().chars() {
        if ch == 'S' {
            len += 1;
            count_s += 1;
        } else {
            if count_s > 0 {
                len -= 1;
                count_s -= 1;
            } else {
                len += 1;
            }
        }
    }
    println!("{}", len);
}


Measured memory_bytes: 508
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        long K = sc.nextLong();
        if(A-K >= 0){
            System.out.println((A-K) + " " + B);
            return;
        }
        if(B-(K-A) >= 0){
            System.out.println("0 " + (B-(K-A)));
            return;
        }

        System.out.println("0 0");
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<algorithm>
using namespace std;
int n;string s;bool t[100010];
int main(){
	cin>>n>>s;
	bool ok=false;
	for(int r=0;r<4;r++){
		int x=r/2,y=r%2;//0が羊、1が狼
		for(int i=0;i<n;i++){
			t[i]=y;
			if(s[i]=='o'&&y)x=1-x;
			if(s[i]=='x'&&!y)x=1-x;
			swap(x,y);
		}
		if(x==r/2&&y==r%2){ok=true;break;}
	}
	if(ok)for(int i=0;i<n;i++)cout<<(t[i]?'W':'S');
	else cout<<"-1";cout<<endl;
	return 0;
}


Measured memory_bytes: 640
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

n, k = na()

ans = 1
while n // k != 0:
    n //= k
    ans += 1
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	int n, m;

	int tanri(int a, double per, int t) {
		int tmp = 0;
		for (int i = 0; i < n; i++) {
			int b = (int)(a * per);
			a -= t;
			tmp += b;
		}
		return a + tmp;
	}

	int fukuri(int a, double per, int t) {
		for (int i = 0; i < n; i++) {
			int b = (int)(a * per);
			a = a + b - t;
		}
		return a;
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		for (int T = sc.nextInt() - 1; 0 <= T; T--) {
			int ini = sc.nextInt();
			n = sc.nextInt();
			m = sc.nextInt();

			int max = 0;
			for (int i = 0; i < m; i++) {
				int flg = sc.nextInt();
				double per = sc.nextDouble();
				int t = sc.nextInt();
				if (flg == 0) {
					max = Math.max(max, tanri(ini, per, t));
				} else {
					max = Math.max(max, fukuri(ini, per, t));
				}
			}
			System.out.println(max);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 42872
/**
 * 
 */

import java.util.Scanner;

/**
 * @author kumar1
 * 
 */
public class Main {

	Main() {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int w = scanner.nextInt();
			int h = scanner.nextInt();
			if (w == 0 || h == 0)
				break;
			int[][] world = new int[h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					world[i][j] = scanner.nextInt();
				}
			}
			int c = 0;
			for (int j = 0; j < h; j++) {
				for (int k = 0; k < w; k++) {
					if (world[j][k] != 0) {
						c++;
						bfs(world, k, j);
					}
				}
			}
			System.out.println(c);
		}
	}

	/**
	 * @param world
	 * @return
	 */
	private boolean bfs(int[][] world, int x, int y) {
		// TODO 自動生成されたメソッド・スタブ
		world[y][x] = 0;
		int[] dx = { -1, 0, 1, 1, 1, 0, -1, -1 };
		int[] dy = { 1, 1, 1, 0, -1, -1, -1, 0 };
		int c = 0;
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || world[0].length <= nx || ny < 0 || world.length <= ny)
				continue;
			if (world[ny][nx] != 0) {
				bfs(world, nx, ny);
				c++;
			}
		}
		if(c == 0)
			return false;
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		new Main();
	}

}

Measured memory_bytes: 43060
#!/usr/bin/env python

A = [input() for i in range(5)]
m = 9
flag = True
for a in A:
    if int(a[-1]) == 0:
        pass
    elif int(a[-1]) <= m:
        flag = False
        m = int(a[-1])
        min_dish = a
B = [int(i) for i in A]
if flag:
    min_dish = str(min(B))
sum = int(min_dish)
A.remove(min_dish)
for a in A:
    if int(a[-1]) == 0:
        sum += int(a)
    else:
        sum += int(a) + int(10) - int(a[-1])
print(int(sum))

Measured memory_bytes: 3064
#include <iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;

typedef long long ll;

ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

int main(){
	ll x,y;
	cin>>x>>y;
	ll lcm=x*y/gcd(x,y);
	if(x%y==0){
		cout<<-1<<endl;
	}else{
		cout<<lcm+x<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int MAXN = 200228;



int n, k;
int a[MAXN];
int add[MAXN];
int a1[MAXN];


void process() {
	for (int i = 1; i <= n; i++) {
		add[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		add[max(i - a[i], 1)]++;
		add[min(i + a[i] + 1, n + 1)]--;
	}
	int bal = 0;
	for (int i = 1; i <= n; i++) {
		bal += add[i];
		a[i] = bal;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//read(FILENAME);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}	
	for (int t = 0; t < k; t++) {
		for (int i = 1; i <= n; i++) {
			a1[i] = a[i];		
		}
		process();
		bool bad = false;
		for (int i = 1; i <= n; i++) {
			if (a[i] != a1[i]) {
				bad = true;
				break;
			}
		}
		if (!bad) {
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';
	return 0;	 	
}


Measured memory_bytes: 5988
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

typedef long long ll;

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

  int n;
  cin >> n;
  ll a[n];
  for(int i = 0; i < n; i++) cin >> a[i];

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

  map< ll, ll > counts;
  for(int i = 0; i <= n; i++){
    if(counts.find(s[i]) != counts.end())
      counts[s[i]] = counts[s[i]] + 1;
    else counts[s[i]] = 1;
  }

  ll sum = 0;
  for(auto& c: counts){
    sum += c.second * (c.second - 1) / 2;
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 15872
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=LLONG_MAX;
const int inf=INT_MAX;
const int nmax=3e5+5;
const int mod=1e9+7;
using namespace std;
int n,i,j,nr,r;
ll ans;
pair<ll,int>p[nmax],a[nmax];
map<ll,int>viza,vizc;
int main()
{
    //freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>p[++j].fr,p[j].sc=1,viza[p[j].fr]++;
	for(i=1;i<=n;i++)cin>>p[++j].fr,p[j].sc=2;
	for(i=1;i<=n;i++)cin>>p[++j].fr,p[j].sc=3,vizc[p[j].fr]++;
	sort(p+1,p+3*n+1);
	for(i=1,r=n;i<=3*n;i++)
	{
		if(p[i].sc==1)nr++;
		else if(p[i].sc==2)ans+=1LL*(nr-viza[p[i].fr])*(r-vizc[p[i].fr]);
		else if(p[i].sc==3)r--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 30592
import java.io.*;
import java.util.*;
import java.math.*;

class Main
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static ArrayList<Integer>[] al;
	static boolean[] v;
	static Pair[] a;
	static List<Integer> list;
	
	static void dfs(int u)
	{
		list.add(u);v[u]=true;
		
		for(int x:al[u])
		{
			if(!v[x])
			{
				dfs(x);
			}
		}
	}
	
	@SuppressWarnings("unchecked")
    public static void main(String args[]) throws Exception
    {
		int n=sc.nextInt();long t=sc.nextLong();a=new Pair[n];al=new ArrayList[n];
		
		for(int i=0;i<n;i++)
		{	
			long num=sc.nextLong();
			
			a[i]=new Pair(num,num+t);
			
			al[i]=new ArrayList<Integer>();
		}
		
		long res=0;int last=0;
		
		for(int i=0;i<n;i++)
		{	
			if(i+1<n && a[i].r>=a[i+1].l)
			{
				al[i].add(i+1);
			}
		}
		
		v=new boolean[n];
		
		for(int i=0;i<n;i++)
		{
			if(!v[i])
			{
				list=new ArrayList<Integer>();
				
				dfs(i);
				
				res=res+a[list.get(list.size()-1)].r-a[list.get(0)].l;
			}
		}
		
		out.println(res);out.close();
    }
}

class Pair
{
	long l,r;
	
	public Pair(long l,long r)
	{
		this.l=l;this.r=r;
	}
}

class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

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

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

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

Measured memory_bytes: 129296
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
vector<int> adj[maxn];
ll d[maxn] , k[maxn];
void dfs(int v , int p = -1)
{
    d[v] = 1;
    for(auto u : adj[v])
    {
        if(u == p)
            continue;
        dfs(u , v);
        d[v] += d[u];
        if(d[u] & 1)
            k[v]++;
    }
}
int main()
{
    int n;
    cin >> n;
    if(n % 2)
    {
        cout << "First";
        return 0;
    }
    for(int i = 0; i < n - 1; i++)
    {
        int a , b;
        cin >> a >> b;
        adj[--a].pb(--b);
        adj[b].pb(a);
    }
    dfs(0);
    for(int i = 0; i < n; i++)
    {
        if(k[i] > 1 || (k[i] == 1 && (n - d[i]) % 2))
        {
            cout << "First";
            return 0;
        }
    }
    cout << "Second";
}


Measured memory_bytes: 7936
// Leftmost Ball
// * frank_c1
// * 2017 / 09 / 29

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL pow_mod(LL b, LL p, LL k) {
	LL ret = 1;
	for (; p; p >>= 1) {
		if (p & 1) ret = ret * b % k;
		b = b * b % k;
	} return ret;
}

const int maxn = 3005;
const int mo = (int)(1e9) + 7;
LL fac[maxn * maxn], ivf[maxn * maxn];
int f[maxn][maxn];

inline LL C(int n, int m) {
	if (m < 0 || n - m < 0) return 0;
	return (fac[n] * ivf[m] % mo) * ivf[n - m] % mo;
}

inline void add(int& x, int v) {
	x += v; if (x >= mo) x -= mo;
}

int main() {
	int n, K;
	scanf("%d%d", &n, &K);
	if (K == 1) return printf("1\n"), 0;
	int mx = n * (K + 1);
	fac[0] = ivf[0] = 1;
	for (int i = 1; i <= mx; ++i) fac[i] = fac[i - 1] * i % mo;
	ivf[mx] = pow_mod(fac[mx], mo - 2, mo);
	for (int i = mx - 1; i >= 1; --i) ivf[i] = ivf[i + 1] * (i + 1) % mo;
	f[0][0] = 1;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (i < j) add(f[i + 1][j], f[i][j]);
			if (j < n) add(f[i][j + 1], 1LL * f[i][j] * C(i + (j + 1) * (K - 1) - 1, K - 2) % mo);
		}
	} int ret = f[n][n];
	for (int i = 1; i <= n; ++i) ret = 1LL * ret * i % mo;
	return printf("%d\n", ret), 0;
}

Measured memory_bytes: 90368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXSTRING 200

int main(int argc,char const* argv[])
{
  int n,i,ans=0;
  string s;
  string forward,back;
  cin >> s;
  n=s.size();
      for(i=n-2;i;i-=2)
	{
	  if(s.substr(0,i/2)==s.substr(i/2,i/2)) 
	    {
	      ans=i;
	      break;
	    }
	}
  cout << ans << endl;
  return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define mod 1000000007
#define FT() int t; scanf("%d",&t); while(t--)
#define pb push_back
#define nl printf("\n")
#define fi(i,start,end) for(int i=start; i < (int)end ; ++i)
#define ip(n)   scanf("%d",&n)
#define mz(a)   memset(a,0,sizeof(a))
#define inpArr(A,n) fi(i,0,n)   ip(A[i]);
#define print(a)  for(auto i : a)   cout<<i<<" "; nl;
#define Fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
ll max(ll a,ll b) { return a>b?a:b;}
ll min(ll a,ll b) { return a<b?a:b;}
void solve()
{   
}
int main() {
   
    int n,m;
    cin>>n>>m;
    char a[n][m];
    ll dp[n][m];
    fi(i,0,n)
        fi(j,0,m)
            {cin>>a[i][j];
             if(a[i][j] == '#')
                dp[i][j] = 0;
         }
    
    dp[0][0]=1;
    int val = 1;
    fi(i,1,n)
        {   if(a[i][0]=='#')
                val=0;
            dp[i][0]=val;}
    val=1;
    fi(i,1,m)
        {if(a[0][i]=='#')
           val=0;
         dp[0][i]=val;}
    fi(i,1,n)
    {
        fi(j,1,m)
        {    if(a[i][j]=='.')
             dp[i][j] = dp[i-1][j] + dp[i][j-1];
             dp[i][j]%=mod;
        }
    }
    
    cout<<dp[n-1][m-1];
    
    return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (998244353)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t),weight(w){}
};
//using Graph = vector<vector<Edge>>;

int main(){
  int n; cin >> n;
  vi d(n); rep(i, n) cin >> d[i];

  vector<ll> C(n);
  rep(i, n) C[d[i]]++;
  //rep(i, n) printf("C[%d] = %ld\n",i, C[i] );
  if(d[0] != 0 || C[0] != 1){
    std::cout << 0 << '\n';
    return 0;
  }

  ll ans = 1;
  rep(i, n-1){
    rep(j, C[i+1]){
      ans *= C[i];
      ans %= MOD;
    }
    ans %= MOD;
  }

  std::cout << ans << '\n';
}


Measured memory_bytes: 1408
N, Y = map(int, input().split())

ans = [-1, -1, -1]

for i in range(0, N+1):
    for j in range(0, (N+1)-i):
        k = N - i - j
        if Y == (10000 * i + 5000 * j + 1000 * k):
            ans = [i, j, k]
    
print(' '.join(map(str, ans)))


Measured memory_bytes: 9108