akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x) make_pair(x)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
 
int main() {

    int a,b;
    cin>>a>>b;
    int c=min(a,b);
    int d=max(a,b);
    rep(i,d) {
        cout<<c;
    }

 return 0;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    A,B,C,K=MI()
    if(K<=A):
        print(K)
    elif (K<=A+B):
        print(A)
    else:
        K-=A+B
        print(A-K)

if __name__ == '__main__':
    main()

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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

map<ll, ll> mp;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int a[5];
  for(int i=0;i<5;i++)cin>>a[i];
  int mx=100000;
  for(int i=0;i<5;i++){
    int t = 0;
    for(int j=0;j<5;j++){
      if(i==j || a[j]%10==0)t += a[j];
      else t += a[j] + (10-a[j]%10);
    }
    mx = min(t, mx);
  }
  cout<<mx<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
using namespace std;
#define inRange(x,a,b) (a <= x && x < b)

int main(){
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i = 0; i < n; i++)  cin >> a[i];
    priority_queue<pair<int,int>> l, r;
    int ans = 0, cur = 0;
    do{
        for(int j = 0; j < m; j++)  l.push({-a[cur%n], cur}), r.push({a[cur%n], cur}), cur++;
        while(!inRange(l.top().second, cur-m, cur)) l.pop();
        while(!inRange(r.top().second, cur-m, cur)) r.pop();
        ans += r.top().first+l.top().first;
    }while(cur%n);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 17888
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: x[0])
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)

Measured memory_bytes: 113588
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sort(a) sort(all(a))
using P = pair<int, int>;
using ll = long long;
using ld = long double;
int dx[4] = { 0, 1, 0,-1 };
int dy[4] = { 1, 0,-1, 0 };

int N;
int x[10], y[10];

double dist(int i, int j) {
  double dx = x[i] - x[j];
  double dy = y[i] - y[j];
  return pow(dx * dx + dy * dy, 0.5);
}

signed main() {
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> x[i] >> y[i];
  double sum = 0.0;
  vector<int> v(N);
  rep(i, N) v[i] = i+1;
  do {
    rep(i, N-1) sum += dist(v[i], v[i+1]);
  } while(next_permutation(v.begin(), v.end()));
  int Factorial = 1;
  for(int i=2; i<=N; i++) Factorial*=i;
  cout << fixed << setprecision(10) << sum / Factorial << endl;
  return 0;
}

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

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

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

    sort(w.begin(), w.end(), [&](int i, int j) {
        return v[i] < v[j];
    });

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (i&1)^(w[i]&1);
    }

    cout << ans/2 << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=17,mod=1e9+7;
int n,m,a[N],f[N][1<<N],fac[1<<N],ifac[1<<N];
int Pow(int x,int k){
	int ret=1;
	while(k){
		if(k&1)ret=(ll)ret*x%mod;
		k>>=1;x=(ll)x*x%mod;
	}
	return ret;
}
int C(int n,int m){
	if(n<m)return 0;
	return (ll)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d",&a[i]);
	fac[0]=1;
	for(int i=1;i<=(1<<n);i++)fac[i]=(ll)fac[i-1]*i%mod;
	for(int i=0;i<=(1<<n);i++)ifac[i]=Pow(fac[i],mod-2);
	sort(a+1,a+m+1,greater<int>());
	f[0][0]=1;
	for(int i=0;i<m;i++)
		for(int j=0;j<(1<<n);j++){
			if(!f[i][j])continue;
			f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
			int res=(1<<n)-j-a[i+1];
			for(int k=0;k<n;k++){
				if(j&(1<<k))continue;
				if(res<(1<<k)-1)break;
				f[i+1][j|(1<<k)]=(f[i+1][j|(1<<k)]-(ll)f[i][j]*C(res,(1<<k)-1)%mod*fac[1<<k])%mod;
			}
		}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		ans=(ans+(ll)f[m][i]*fac[(1<<n)-1-i])%mod;
	}
	ans=((ll)ans*(1<<n)%mod+mod)%mod;
	cout<<ans<<"\n";
}

Measured memory_bytes: 7680
#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int main() {
	int a,b,n;
	scanf("%d%d%d",&a,&b,&n);
	printf("%d",min(a*b,n));
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
  int n,k,max;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]>max)
      max=a[i];
  }
  int left=1,right=max,result;
  while(left<=right)
  {
    int mid=(left+right)/2;
    int x=0;
    for(int i=0;i<n;i++)
    {
      x+=a[i]/mid;
      if(a[i]%mid==0)
        x--;
    }
    if(x<=k)
    {
      result=mid;
      right=mid-1;
    }
    else
    {
      left=mid+1;
    }
  }

  cout<<result<<endl;
  return 0;
}


Measured memory_bytes: 3808
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx")
#include <bits/stdc++.h>

constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

// 5 4 9 8 9
// 5 5 9 9 9 
//   4 4 8 9
//
// 2 1 4 5 3
// 2 2 4 5 5
//   1 1 1 3

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)cin >> A[i];
	multiset<int> v;
	v.insert(A[0]);
	for (int i = 1; i < N; i++) {
		auto itr = v.lower_bound(A[i]);
		if (itr == v.begin()) {
			v.insert(A[i]);
		}
		else {
			itr--;
			v.erase(itr);
			v.insert(A[i]);
		}
	}
	cout << v.size() << endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mod 1000000007
const int N=200005;

ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }

int L;



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    cout<<fixed<<setprecision(15);
    
    int n;
    cin>>n>>L;

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

    sort(arr,arr+n);

    for(int i=0;i<n;i++) {
        cout<<arr[i];
    }


    return 0;
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; cin >> N;
    double res=0;
    rep(i, N){
        double x; string u;
        cin >> x >> u;
        if(u == "BTC"){
            res += x * 380000.0;
        }else{
            res += x;
        }
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
/* 
    Author : Jeff Ahn
    Sat 13 Jun 2020 12:57:43 AM PDT 
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,r) for(int i = 0; i < (r); i++)
#define pb push_back
#define ALL(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define uint unsigned long long
#define endl '\n'
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const map<T,T> &vec){ os<< "{"; for (auto p : vec) os << "(" << p.first << "," << p.second << "), "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_map<T,T>&vec){ os<< "{"; for (auto p : vec) os << "(" << p.first << "," << p.second << "), "; os << "}"; return os; }

template <unsigned Mod> struct Modular {
  using M = Modular;
  unsigned v;
  Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {}
  M operator-() const { return M() -= *this; }
  M& operator+=(M r) { if ((v += r.v) >= Mod) v -= Mod; return *this; }
  M& operator-=(M r) { if ((v += Mod - r.v) >= Mod) v -= Mod; return *this; }
  M& operator*=(M r) { v = (uint64_t)v * r.v % Mod; return *this; }
  M& operator/=(M r) { return *this *= mdpow(r, Mod - 2); }
  friend M operator+(M l, M r) { return l += r; }
  friend M operator-(M l, M r) { return l -= r; }
  friend M operator*(M l, M r) { return l *= r; }
  friend M operator/(M l, M r) { return l /= r; }
  friend bool operator==(M l, M r) { return l.v == r.v; }
  friend M mdpow(M b, unsigned exp) {
    Modular res(1);
    while(exp) {
      if (exp & 1) {
        res *= b;
        if ((res.v += Mod) >= Mod) res.v -= Mod;
      }
      b *= b;
      exp >>= 1;
    }
    return res;
  }
};

constexpr long long mod = 1e9 + 7;
using Mint = Modular<mod>;

const int mxn = 1e5 + 10;
Mint dp[mxn];

signed main() {
  fastio;
  unsigned n, k;
  cin >> n >> k;
  Mint res(0);
  for (int i = k; i >= 1; i--) {
    Mint b(k / i);
    b = mdpow(b, n);
    dp[i] = b;
    for (int j = 2*i; j <= k; j += i) {
      dp[i] -= dp[j];
    }
    res += (dp[i] * Mint(i));
  }
  cout << res.v << endl;
  
}


Measured memory_bytes: 4020
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500500;
int n,m;
int a[100][100],p[110];
int main()
{
	scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i][0]);
        for(int j=1;j<=a[i][0];j++)scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=m;i++)scanf("%d",&p[i]);
    int cnt=0;
    for(int i=0;i<=(1<<n)-1;i++)
    {
        int flag=1;
        for(int j=1;j<=m;j++)
        {
            int sum=0;
            for(int k=1;k<=a[j][0];k++)
            {
                if((i&(1<<(a[j][k]-1)))!=0)sum++;
            }
            if(sum%2!=p[j])flag=0;
        }
        //if(flag)cout<<i<<endl;
        cnt+=flag;
    }cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define PII pair<int,int>
#define X first
#define Y second
#define MP make_pair
#define PI acos(-1.0)
#define eps 1e-8
const int maxn=2e5+10;
const int mod=1e9+7;
using namespace std;

int na,nb,nc,x,y;
int a[maxn],b[maxn],c[maxn];

int main()
{
    scanf("%d%d%d%d%d",&x,&y,&na,&nb,&nc);
    for(int i=0;i<na;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<nb;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<nc;i++)
        scanf("%d",&c[i]);
    a[na]=inf,b[nb]=inf,c[nc]=inf;
    sort(a,a+na);
    sort(b,b+nb);
    sort(c,c+nc);
    ll ans=0,i,j,k;
    for(i=na-x,j=nb-y,k=nc-1;k>=0;k--)
    {
        if(a[i]<b[j])
        {
            if(c[k]>a[i])
            {
                ans+=c[k];
                i++;
            }
            else 
                break;
        }
        else
        {
            if(c[k]>b[j])
            {
                ans+=c[k];
                j++;
            }
            else 
                break;
        }
    }
    for(;i<na;i++)
        ans+=a[i];
    for(;j<nb;j++)
        ans+=b[j];
    printf("%lld\n",ans);
    // system("pause");
    return 0;
}


Measured memory_bytes: 1408
#!/usr/bin/env python3
acc = [0] * (10**5 + 1)
for i in range(10**5):
    acc[i + 1] = acc[i] + (i + 1)
n = int(input())
s = [input() for _ in range(n)]
dic = {}
for i in range(n):
    srt = ''.join(sorted(s[i]))
    dic[srt] = dic[srt] + 1 if srt in dic else 1
ans = 0
for v in dic.values():
    ans += acc[v - 1]
print(ans)


Measured memory_bytes: 29324
#include <iostream>



using namespace std;

typedef long long LL;
typedef unsigned int UI;

#define rSort(a) 		sort(a.rbegin(),a.rend())
#define Sort(a) 		sort(a.begin(),a.end())
#define Reverse(a) 		reverse(a.begin(),a.end())
#define Sum(a)  		accumulate(a.begin(), a.end(), 0)
#define REP(i, n) 		for(UI i = 0;i < n;i++)
#define REPR(i, n) 		for(UI i = n;i >= 0;i--)
#define FOR(i, m, n) 	for(UI i = m;i < n;i++)

#define MOD  			(LL)1e9 + 7;
#define INF  			(LL)1 << 62;

LL gcd(LL x, LL y) {

	LL a, b, mod;

	if (x > y) {
		a = x;
		b = y;
	}
	else {
		a = y;
		b = x;
	}

	do {
		mod = a % b;
        if(mod==0) break;
		a = b;
		b = mod;
	}
	while (1);

	return b;

}

int main(int argc, const char * argv[]) {

	cin.tie(0);
	ios::sync_with_stdio(false);

	LL X, Y;

	cin >> X >> Y;

	cout << gcd(X, Y) << endl;

	return 0;

}


Measured memory_bytes: 3164
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long h = scanner.nextLong();
        List<Long> alst = new ArrayList<>();
        List<Long> blst = new ArrayList<>();
        for(int i=0;i<n;i++){
            long w = scanner.nextLong();
            long t = scanner.nextLong();
            alst.add(w);
            blst.add(t);
        }
        alst.sort(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o2.compareTo(o1);
            }
        });
        blst.sort(new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o2.compareTo(o1);
            }
        });
        long count = 0;
        for(int i=0;i<n;i++){
            if(blst.get(i) > alst.get(0)){
                count++;
                h-=blst.get(i);
                if(h<=0) break;
            }
        }
        long dx;
        if(h<=0){
            dx=0;
        }else{
            dx = (long)Math.ceil((h*1.0)/alst.get(0));
        }
        System.out.println(count+dx);
    }
}

Measured memory_bytes: 97012
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	char x,y; cin>>x>>y;
	if (x>y) cout<<">";
	else if (x==y) cout<<"=";
	else if (x<y) cout<<"<"<<endl;
	return 0;
}


Measured memory_bytes: 256
from itertools import permutations
 
n = int(input())
n_ = 1
for i in range(n):
    n_ *= i+1
c = [tuple(map(int,input().split())) for _ in range(n)]
tot = 0
 
def dis(c,x,y):
  x1,y1 = c[x]
  x2,y2 = c[y]
  return ((x1-x2)**2 + (y1-y2)**2)**.5
 
for l in permutations(range(n)):
    d = 0
    cur = l[0]
    for x in l:
        d += dis(c,cur,x)
        cur = x
    tot += d/n_
print(tot)

Measured memory_bytes: 3064
#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>
#include <ctype.h>

using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

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

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

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

ll wazu = 76543217;

ll inv(ll x) {
    if (x == 1) { return 1; }
    if (x == 0) { return 0; }
    else {
        ll a = (wazu - inv(wazu % x) * (wazu / x)) % wazu;
        if (a >= 0) { return a; }
        else { return wazu + a; }
    }
}

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }

    if (a.second != b.second) {
        return a.second > b.second;
    }
    else {
        return true;
    }
}

int main()
{
    int W, H, N;
    cin >> W >> H >> N;

    vector<int> x(N);
    vector<int> y(N);
    vector<int> a(N);

    rep(i, N) cin >> x[i] >> y[i] >> a[i];

    vector<pair<int, int> > p(N);
    vector<pair<int, int> > q(N);

    rep(i, N) p[i] = make_pair(a[i], x[i]);
    rep(i, N) q[i] = make_pair(a[i], y[i]);

    int e = 0, f = W , g = 0 , h = H;

    rep(i, N) {
        if (a[i] == 1) { e = max(e,p[i].second); }
        if (a[i] == 2) { f = min(f,p[i].second); }
    }

    rep(i, N) {
        if (a[i] == 3) { g = max(g,q[i].second); }
        if (a[i] == 4) { h = min(h,q[i].second); }
    }

    if (e < f && g < h) {
        cout << (f - e) * (h - g) << endl;
    }
    else {
        cout << 0 << endl;
    }

}

Measured memory_bytes: 256
#https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	a,b = map(int,input().split())
	G[a-1].append(b-1)
	G[b-1].append(a-1)
visit=[False]*N
color=[-1]*N
que=deque()

def nibu():
	que.append(0)
	color[0]=True

	while que:
		p=que.pop()
		visit[p]=True
		for q in G[p]:
			if visit[q] and color[q]==color[p]:
				return False
			elif not visit[q]:
				que.append(q)
				color[q]=(color[p]+1)%2
	return True

if nibu():
	B=color.count(0)
	W=color.count(1)
	ans=B*W-M
else:
	ans = (N*(N-1))//2 -M
print(ans)

Measured memory_bytes: 91472
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        cout << "a > b" << endl;
    else if (a < b)
        cout << "a < b" << endl;
    else 
        cout << "a == b" << endl;

 

}


Measured memory_bytes: 3112
#include <iostream>

using namespace std;

int main() {
	int a,b,c,K;
	cin>>a>>b>>c>>K;
	if (a>=b && a>=c) {
		cout<<b+c+(1<<K)*a<<endl;
	}else if (b>=a && b>=c) {
		cout<<a+c+(1<<K)*b<<endl;
	}else
		cout<<a+b+(1<<K)*c<<endl;
	return 0;
}


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int std_in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};
const int MOD = 1000000007;

ll N, A[200010];

signed main(){
    cin >> N;
    REP(i, N) cin >> A[i];
    ll h = 0, t = 0, X = 0, S = 0, cnt = 0;
    while(h <= t){
        while(t < N && (X ^ A[t]) >= (S + A[t])){
            X ^= A[t]; S += A[t];
            t++;
        }
        cnt += t - h;
        X ^= A[h]; S -= A[h];
        h++;
    }
    PRINT(cnt);
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rd read()
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
int main() {
	int a=rd,b=rd,k=rd;
	int x=b-a+1;
	if(2*k>=x)
	{
		for(int i=a;i<=b;i++)
		{
			cout<<i;
			cout<<endl;
		}
	}
	else 
	{
		for(int i=a;i<=a+k-1;i++)
		{
			cout<<i;
			cout<<endl;
		}
		for(int i=b+1-k;i<=b;i++)
		{
			cout<<i;
			cout<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF=1<<29;
ll mod=1000000007;

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

	int N,M,Ans=0;
	cin>>N>>M;
	vector<vector<int>> arr(M+1);
	for(int i=0;i<N;i++){
		int a,b;
		cin>>a>>b;
		if(a>M) continue;
		arr[a].push_back(b);
	}

	priority_queue<int> pq;
	for(int i=1;i<=M;i++){
		if(!arr[i].empty()){
			for(int j=0;j<arr[i].size();j++) pq.push(arr[i][j]);
		}

		if(!pq.empty()){
			int tmp=pq.top();
			pq.pop();
			Ans+=tmp;
		}
	}
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 5632
#include <bits/stdc++.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 DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
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 namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    string in; cin >> in;
    cout << in.substr(0, in.size() - 8) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#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
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	ll D;
	cin >> D;
	vector<ll> c(27);
	vector<vector<ll>> s(D+1, vector<ll>(27));
	vector<ll> zenkai(27);

	for (ll name = 1; name <= 26; name++)cin >> c.at(name);
	for (ll day = 1;day <= D; day++)for (ll name = 1; name <= 26; name++)cin >> s.at(day).at(name);
	vector<ll> t(D+1); 

	for (ll day = 1; day <= D; day++) {
		cin >> t.at(day);
	}
	
	for (ll name = 1; name <= 26; name++) {
		zenkai.at(name) = 0;
	}

	ll an = 0;

	for (ll day = 1; day <= D; day++) {

		an += s.at(day).at(t.at(day));
		zenkai.at(t.at(day)) = day;

		for (ll name = 1; name <= 26; name++) {
			an -= c.at(name) * (day - zenkai.at(name));
		}
		cout << an << endl;

	}


}

Measured memory_bytes: 3716
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const double PI = 3.1415926535897932;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

int main()
{
	int H, W, K;
	cin >> H >> W >> K;
	vector<string> Cij(H);

	rep(i, H)
	{
		cin >> Cij.at(i);
	}

	int ans = 0;
	rep(maskR, pow(2,H))
	{
		rep(maskC, pow(2,W))
		{
			int bk = 0;
			rep(i, H)
			{
				rep(j, W)
				{
					if (((maskR & 1 << i) & 1 << i) == 0 and
						((maskC & 1 << j) & 1 << j) == 0 and
						Cij[i][j] == '#')
					{
						bk += 1;
					}
				}
			}

			if (bk == K)
			{
				ans += 1;
			}
		}
	}

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

Measured memory_bytes: 4096
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N, K = mis()
    A = lmis()
    for i in range(K, N):
        print(Yes if A[i-K]<A[i] else No)





main()



Measured memory_bytes: 32424
a,b=map(int,input().split())

if a<0 and b<0:
    if (b-a+1)%2==1:
        print("Negative")
    else:
        print("Positive")
elif a==0 or b==0:
    print("Zero")
elif a<0 and b>0:
    print("Zero")
else:
    print("Positive")

Measured memory_bytes: 3060
#include<stdio.h>

#define MAX 100000

int partition(int A[],int p,int r);

int main(void)
{
  int A[MAX],n;
  int i,par;

  scanf("%d",&n);
  for(i = 0;i < n;i++){
    scanf("%d",&A[i]);
  }

  par = partition(A,0,n-1);

  printf("%d",A[0]);
  for(i = 1;i < n;i++){
      printf(" ");
 
    if(i == par){
      printf("[");
    }
    printf("%d",A[i]);
    if(i == par){
      printf("]");
    }
  }
  puts("");

  return 0;
}




int partition(int A[],int p,int r){
  int x,i,j;
  int temp;
    
  x = A[r];
  i = p-1;
  for(j = p;j <= r-1;j++){
    if(A[j] <= x){
      i = i+1;
      
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  temp = 0;
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;

  return i+1;
}



Measured memory_bytes: 2104
def dfs(cursor, a, b, c):
    if cursor == N:
        return abs(A - a) + abs(B - b) + abs(C - c) - 30 if min(a, b, c) > 0 else float("inf")
    ret0 = dfs(cursor + 1, a, b, c)
    ret1 = dfs(cursor + 1, a + l[cursor], b, c) + 10
    ret2 = dfs(cursor + 1, a, b + l[cursor], c) + 10
    ret3 = dfs(cursor + 1, a, b, c + l[cursor]) + 10
    return min(ret0, ret1, ret2, ret3)


N, A, B, C = [int(i) for i in input().split()]
l = [int(input()) for _ in range(N)]
print(dfs(0, 0, 0, 0))


Measured memory_bytes: 3064
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        String[] arr = new String[n];
        for (int i=0; i<n; i++){
            arr[i] = sc.next();
        }
        
        for (int i=0; i<arr.length; i++){
            for (int j=i+1; j<arr.length; j++){
                if (arr[i].compareTo(arr[j])>0){
                    String temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (String word: arr) {
            System.out.print(word);
        }
        System.out.println();
    }
}

Measured memory_bytes: 21716
// https://atcoder.jp/contests/abc146/tasks/abc146_e

#include "algorithm"
#include "cmath"
#include "functional"
#include "iostream"
#include "map"
#include "numeric"
#include "queue"
#include "set"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll N, K;
  cin >> N >> K;

  VL as(N);
  rep(i, N) cin >> as[i];

  VL rems(N + 1);
  rep(i, N) rems[i + 1] = rems[i] + as[i];
  rep(i, N + 1) rems[i] = (rems[i] - i + K) % K;

  map<ll, ll> m;

  ll res = 0;

  // i を右端とするものの個数を足していく
  rep(i, N + 1) {
    res += m[rems[i]];

    m[rems[i]]++;

    if (i - K + 1 >= 0) {
      m[rems[i - K + 1]]--;
    }
  }

  cout << res << endl;
}

// A を 1 ずつ減らせば区間の和が K の倍数となるものの個数を数える問題となる
void solve2() {
  ll N, K;
  cin >> N >> K;

  VL as(N);
  rep(i, N) cin >> as[i];
  rep(i, N) as[i]--;

  VL rems(N + 1);
  rep(i, N) rems[i + 1] = (rems[i] + as[i]) % K;

  map<ll, ll> m;

  ll res = 0;

  // i を右端とするものの個数を足していく
  rep(i, N + 1) {
    res += m[rems[i]];

    m[rems[i]]++;

    if (i - K + 1 >= 0) {
      m[rems[i - K + 1]]--;
    }
  }

  cout << res << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve2();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 15872
module Main where
 
import Control.Applicative
import Text.Printf
import Numeric
 
main :: IO ()
main = do
  { _ <- getLine
  ; xs <- getInts
  ; let mx = maximum xs
  ; let mn = minimum xs
  ; let sm = sum xs
  ; putInts [mn, mx, sm]
  }
  
--
  
getInts :: IO[Int]
getInts = map read . words <$> getLine
 
putInts :: [Int] -> IO()
putInts = putStrLn . unwords. map show
 
getDoubles :: IO[Double]
getDoubles = map read. words <$> getLine
 
putDoubles :: [Double] -> IO ()
putDoubles = putStrLn . unwords . map showDouble
 
showDouble :: Double -> String
showDouble x = showFFloat Nothing x ""
 
getStrings :: IO [String]
getStrings = words <$> getLine
 
readInt' :: String -> Int
readInt' = read



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

if D ==0:
    if N != 100:
        print(N)
    else:
        print(101)
elif D == 1:
    if N != 100:
        print(N*100)
    else:
        print(10100)
else:
    if N != 100:
        print(N*10000)
    else:
        print(1010000)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;
template <typename T>
void vecin(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
}
template <typename T>
void vecout(vector<T> &v, int n = 0)
{
    if (n == 0)
        n = v.size();
    for (int i = 0; i < n - 1; ++i)
    {
        cout << v[i] << " ";
    }
    cout << v[n - 1] << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<set<int>> G(n);
    REP(i, m)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].emplace(b);
        G[b].emplace(a);
    }
    vint perm(n);
    REP(i,n){
        perm[i] = i;
    }
    int ans = 0;
    do
    {
        if (perm[0] != 0)
            continue;
        bool flag = true;
        REP(i, n - 1)
        {
            if (G[perm[i]].find(perm[i+1]) == G[perm[i]].end()){
                flag = false;
                break;
            }
        }
        if (flag)
            ++ans;
    } while (next_permutation(perm.begin(), perm.end()));
    cout << ans << endl;
}

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

using ll = long long;
const ll inf = 1e18;
ll dp[100001];
int arr[100001];
int n, k;

ll solve(int idx){
    if(idx > n)
        return inf;
    if(idx == n)
        return 0;
    ll& ans = dp[idx];
    if(ans != -1)
        return ans;
    ans = inf;
    for(int i = 1; i <= k and idx + i <= n; i++){
        ans = min(ans, abs(arr[idx] - arr[idx + i]) + solve(idx + i));
    }

    return ans;
}

int main(){
    cin >> n >> k;
    memset(dp, -1, sizeof dp);
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    cout << solve(1) << endl;

    return 0;
}


Measured memory_bytes: 12600
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#include <bitset>
#include <fstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

#define INF 1000000007ll
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )
#define err(x) cerr << #x << " = " << x << endl;
#define SIZE -1

vector<int> ans;
int N, K;

void one_before() {
   int n = ans.size();
   if (ans[n - 1] == 1) ans.pop_back();
   else {
      ans[n - 1]--;
      for (int i = n ; i < N ; ++i) ans.PB(K);
   }
}

void get_ans(int n, int k) {
   ans.PB(k / 2 + 1);
   if (n == 1) return;
   get_ans(n - 1, k);
   //for (int i = 0 ; i < ans.size() ; ++i) cout << ans[i] << " ";
   //cout << endl;
   if (n % 2 == 0) one_before();
}

int main() {
   scanf("%d %d", &K, &N);
   if (K % 2 == 0) {
      ans.PB(K / 2);
      for (int i = 1 ; i < N ; ++i) ans.PB(K);
   }
   else get_ans(N, K);
   for (int i = 0 ; i < ans.size() ; ++i) {
      printf("%d ", ans[i]);
   }
   printf("\n");
   
   return 0;
}


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

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

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

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

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

// --------------------------------------
int n;

void bfs(int p, vector<vector<P>> g, int ma) {
  vector<int> v(n);

  queue<tuple<int, int, int>> que;

  que.push(make_tuple(p, -1, 1));
  while(!que.empty()) {
    tuple<int, int, int> tp = que.front(); que.pop();
    int& now = get<0>(tp);
    int& from = get<1>(tp);
    int& count = get<2>(tp);
    REP(i, g[now].size()) {
      if(g[now][i].first != from) {
        v[g[now][i].second] = count++;
        if(count > ma) count = 1;
        que.push(make_tuple(g[now][i].first, now, count));
      }
    }
  }

  cout << ma << endl;
  FOR(i, 1, n) {
    cout << v[i] << endl;
  }
}

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

  cin >> n;
  vector<vector<P>> g(n + 1);
  vector<int> count(n + 1, 0);

  REP(i, n - 1) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(make_pair(b, i + 1));
    g[b].push_back(make_pair(a, i + 1));

    count[a]++;
    count[b]++;
  }

  int ma = 0, po;
  FOR(i, 1, n + 1) {
    if(ma < count[i]) {
      ma = count[i];
      po = i;
    }
  }

  bfs(po, g, ma);
}


Measured memory_bytes: 13312
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

char buf[100];

int main(void) {
  fgets(buf, 100, stdin);
  buf[5] = buf[13] = ' ';
  puts(buf);
  
  return 0;
}


Measured memory_bytes: 256
k,a,b = map(int,input().split())
if a>=b or k<a:
    print(1+k)
else:
    s = k - a + 1
    t = s//2
    if s%2==0:
        print(max(1+k, a + (b-a)*t))
    else:
        print(max(1+k, a + (b-a)*t+1))

Measured memory_bytes: 3060
/*
 * Author       : YangDavid
 * Created Time : 2019年07月12日 星期五 10时07分12秒
 */

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 111111;
int n, l[maxn];

int main() {
    scanf("%d", &n);
    n *= 2;
    rep(i, n) scanf("%d", &l[i]);
    sort(l + 1, l + n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; i += 2)
        ans += l[i];
    printf("%lld\n", ans);
    return 0;
}


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

// 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; }
 
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 998244353
using ll = long long;
using pint = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<int>>;

int main(){
    int N,W; cin>>N>>W;
    vector<ll> w(N),v(N);
    rep(i,N)cin>>w[i]>>v[i];
    vector<vector<ll>> dp(N+1,vector<ll>(W+10,0));//dp[i][w] = 0 to i-1 で w の重さ　価値の最大値
    rep(i,N){
        rep(j,W+1){
            if(j-w[i]>=0)dp[i+1][j] = max(dp[i+1][j],dp[i][j - w[i]] + v[i]);
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }
    }
    ll res = 0;
    rep(j,W+1) res = max(res,dp[N][j]);
    cout<<res<<endl;
}

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

int main(){
    string s;
    cin >> s;
    int ret = 700;
    for(size_t i = 0; i < 3; i++)
    {
        if(s[i]=='o')
            ret += 100;
    }
    cout << ret << endl;
    

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
	String s1 = s.substring(0,1);
    String s2 = s.substring(1,2);
    String s3 = s.substring(2,3);
    String s4 = s.substring(3,4);
    int a = 0;
    
    if(s1.equals(s2)) a = 1;
    if(s2.equals(s3)) a = 1;
    if(s3.equals(s4)) a = 1;
    
    if (a==1) {
	    System.out.println("Bad");
    } else {
      System.out.println("Good");
    }
    
  }
}


Measured memory_bytes: 22996
import sys
 
a,b = map(int,input().split())
low = int(min(a//0.08,b//0.1))
high = int(max((a+1)//0.08,(b+1)//0.1))
for i in range(low,high+1):
  if int(i*0.08)==a and int(i*0.1)==b:
    print(i)
    sys.exit()
print(-1)

Measured memory_bytes: 3060
n=int(input())
l=list(map(int,input().split()))
from bisect import bisect_left
l.sort()
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    t=l[i]+l[j]
    idx=bisect_left(l,t)
    ans+=max(idx-j-1,0)
print(ans)


Measured memory_bytes: 9140
import java.util.*
fun main() {
    val n= readLine()!!.toInt()
    var tree= MutableList(n+1){ mutableListOf<Int>()}
    var memo= mutableMapOf<List<Int>, Int>()
    for (i in 1 until n){
        val (a,b)= readLine()!!.split(" ").map { it.toInt() }
        memo[listOf(a,b)]=i
        tree[a].add(b)
    }

    var que=ArrayDeque<List<Int>>()
    var visited=BooleanArray(n+1){i->i==0}
    que.addFirst(listOf(1,-1))
    visited[1]=true
    var ans=IntArray(n){0}
    while (que.isNotEmpty()){
        val now=que.removeFirst()
        var cnt=0
        for (i in tree[now[0]]){
            if (cnt==now[1]){cnt++}
            que.addFirst(listOf(i, cnt))
            visited[i]=true
            ans[memo[listOf(now[0], i)]!!]=cnt+1
            cnt++
        }
        ans[0]=Math.max(ans[0],cnt)
    }
    ans.forEach { println(it) }
}

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

bool foo(int a, int b){
	if (a > 8 || b > 8){
		cout << ":(" << endl;
	}
	else{
		cout << "Yay!";
	}
	return 0;
}
int main(){
	int a, b;
	cin >> a;
	cin >> b;
	foo(a, b);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const double PI = acos(-1);
#define rep(i, n) for (int i = 0; i < (int)(n); i++ )
using namespace std;
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main(){
  int m, f, b;
  cin >> m >> f >> b;
  if((m+f)< b) cout << "NA" << endl;
  else if(m > b) cout << 0 << endl;
  else cout << b-m << endl;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
#define MOD 1000000007
#define F first
#define S second

typedef long long ll;
using namespace std;

struct cmp2 {
    bool operator()(pair<int,int> const & lhs, pair<int,int> const & rhs) {
        return lhs.S > rhs.S;
    }
};
struct cmp1 {
    bool operator()(pair<int,int> const & lhs, pair<int,int> const & rhs) {
        return lhs.F > rhs.F;
    }
};

int n, m, lastCut, ans;
priority_queue< pair<int,int>, vector<pair<int,int>>, cmp1 > f;
priority_queue< pair<int,int>, vector<pair<int,int>>, cmp2 > s;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        f.push(make_pair(x, y));
    }
    for (int i = 1; i <= n; ++i) {
        while (s.size() && s.top().S == i) {
            if (s.top().F >= lastCut) {
                ++ans;
                lastCut = i;
            }
            s.pop();
        }
        while (f.size() && f.top().F == i) {
            s.push(f.top());
            f.pop();
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1908