akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

//階乗を求める関数
int fac( int num ){
    int x = 1;
    for(int i = 1; i <= num; ++i){
        x *= i;
    }
    return x;
}

//順番を求める関数
int ord(int X[], int N){
    int ord = 1;
    int r = 0;

    //左から1桁ずつ増やして計算
    for(int i = 1; i < N; ++i){
        r = X[i - 1] - 1;
            for(int j = 0; j < i; ++j){
                //以左に利用済の数は除く
                if(X[j] < X[i - 1]) r--;
            }
        ord += r * fac(N - i);
    }
    return ord;
}

int main() {
    int N;
    cin >> N;
    int P[N], Q[N];
    for(int i = 0; i < N; ++i) cin >> P[i];
    for(int i = 0; i < N; ++i) cin >> Q[i];

    //それぞれの順位
    int a, b;
    a = ord(P, N);
    b = ord(Q, N);
    
    if(b>a) cout << b - a << endl;
    else cout << a - b << endl;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> llVEC;
typedef vector<P> PVEC;
typedef priority_queue<P,PVEC,greater<P> > PPQ;
typedef priority_queue<ll, llVEC, greater<ll> > llPQ;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n-1; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> vec){ return (ll)vec.size(); }
ll sz(string s){ return (ll)s.size(); }

ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }


int main(){
    ll n;
    cin >> n;
    ll a[n] = {};
    ll memo[200000] = {};
    fill(memo,memo+200000,LINF);
    ll index = 0;

    rep(i,0,n){
        ll a;
        cin >> a;

        ll ok = index+1, ng = -1;
        while(abs(ok-ng) > 1){
            ll mid = (ok+ng)/2;
            if(memo[mid] < a) ok = mid;
            else ng = mid;
        }

        if(ok == index+1) memo[index++] = a;
        else memo[ok] = a;
    }
    
    cout << index << endl;
    return 0;
}

Measured memory_bytes: 5956
/*
AtCoderBeginnerContest168
Problem B - ... (Triple Dots) / Triple Dots
Time Limit: 2 sec / Memory Limit: 1024 MB
Score:
200
points
*/

#include <iostream>

int main()
{
    int K;
    std::string S;
    std::cin >> K >> S;
    if (S.length()<=K)
    {
        std::cout << S << "\n";
    }
    else
    {
        std::cout << S.substr(0,K) << "...\n";
    }
}


Measured memory_bytes: 3624
dict = {'AC':0, 'WA':0, 'TLE':0, 'RE':0}
n = int(input())
for i in range(n):
  dict[input()] += 1
print('AC x {}\nWA x {}\nTLE x {}\nRE x {}'.format(dict['AC'],dict['WA'],dict['TLE'],dict['RE']))

Measured memory_bytes: 69928
#include<bits/stdc++.h>
using namespace std;
int main(){
 string s,t;
  int ct=0,i,j,n;
  cin>>s>>t;
  n=s.length();
  for(i=0;i<n;i++){
    if(s[i]!=t[i])
      ct++;
  }
  cout<<ct<<endl;
}


Measured memory_bytes: 3912
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(12), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
const Int MOD = 1000000007;
Int POW(Int x, Int y) {
    if (y == 0) return 1;
    if (y % 2 == 0) return POW(x*x%MOD, y/2);
    return x*POW(x, y-1)%MOD;
}
int main() {
    int N; cin >> N;
    cout << (POW(10, N) + 2*MOD - POW(9, N) - POW(9, N) + POW(8, N)) % MOD << endl;
    return 0;
}

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

const ll inf = 1e6;

int main() {
	ll n;
	cin >> n;
	map<ll, ll> m;
	for (ll i = 0; i < n; ++i) {
		ll p;
		cin >> p;
		if (m[p - 1] > 0) {
			m[p] = m[p - 1] + 1;
		}
		else {
			m[p] = 1;
		}
	}
	ll ans = 0;
	for (auto p : m)ans = max(ans, p.second);
	cout << n - ans << endl;
}


Measured memory_bytes: 12800
open Printf

let scan fmt f =
  Scanf.sscanf (read_line ()) fmt f

let id a = a

let (s, t) = scan "%s %s" @@ fun s t -> (s,t)
let (a, b) = scan "%d %d" @@ fun a b -> (a,b)
let u = scan "%s" id

let () =
  if u = s then
    printf "%d %d\n" (a - 1) b
  else
    printf "%d %d\n" a (b -1)


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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

typedef long long i64;
typedef pair<i64, i64> pii;

const int INF = 0x3f3f3f3f;
const i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  i64 n;
  i64 pipe[65010], joint[65010] = {};
  while (cin >> n, n) {
    i64 maxj = 0;
    i64 sum = 0;
    rep(i, n) { cin >> pipe[i]; sum += pipe[i]; }
    rep(i, n - 1) { cin >> joint[i]; }

    sort(joint, joint + n - 1, greater<i64>());

    i64 ans = 0;
    i64 addjoint = 0;
    rep(i, n) {
      ans = max(ans, (sum + addjoint) * (n - i));
      addjoint += joint[i];
    }

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

  return 0;
}



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

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)

const int INF = 1<<29;

int W, H, sx, sy, gx, gy;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector <vector <int>> maze;

bool inrange(int x, int y) {
	return 0 <= x && x < W && 0 <= y && y < H;
}

int dfs(int x, int y, int cnt) {
	if (x == gx && y == gy) return cnt;
	if (cnt == 10) return INF;
	int res = INF;
	rep(4, i) {
		int nx = x + dx[i], ny = y + dy[i];
		if (inrange(nx, ny) && maze[ny][nx] == 3) {
			res = min(cnt+1, res);
			continue;
		}
		if (inrange(nx, ny) && maze[ny][nx] != 1) {
			while (inrange(nx+dx[i], ny+dy[i]) && maze[ny+dy[i]][nx+dx[i]] != 1 && maze[ny+dy[i]][nx+dx[i]] != 3) {
				nx += dx[i];
				ny += dy[i];
			}
			if (inrange(nx+dx[i], ny+dy[i]) && maze[ny+dy[i]][nx+dx[i]] == 3) {
				res = min(cnt+1, res);
				continue;
			}
			if (!inrange(nx+dx[i], ny+dy[i])) continue;
			if (maze[ny+dy[i]][nx+dx[i]] == 1) maze[ny+dy[i]][nx+dx[i]] = 0;
			res = min(res, dfs(nx, ny, cnt+1));
			if (maze[ny+dy[i]][nx+dx[i]] == 0) maze[ny+dy[i]][nx+dx[i]] = 1;
			//cout << cnt << ' ' << nx << ' ' << ny << endl;
		}
	}
	return res;
}

void solve(void){
	while (1) {
		cin >> W >> H;
		if (W == 0 && H == 0) break;
		vector <vector <int>> m(H, vector <int> (W, -1));
		maze = m;
		rep(H, i) rep(W, j) {
			cin >> maze[i][j];
			if (maze[i][j] == 2) {
				sx = j, sy = i;
			}
			if (maze[i][j] == 3) {
				gx = j, gy = i;
			}
		}
		int ans = dfs(sx, sy, 0);
		//cout << sx << ' ' << sy << ' ' << gx << ' ' << gy << endl;
		cout << (ans == INF ? -1 : ans) << endl;
	}
}

int main(void){
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}



Measured memory_bytes: 3052
#include<stdio.h>

int main(void)
{
  int X,Y,Z;
  int tmp;
  
  scanf("%d %d %d", &X, &Y, &Z);
  
  tmp = X;
  X = Y;
  Y = tmp;
  
  tmp = X;
  X = Z;
  Z = tmp;
  
  printf("%d %d %d\n", X, Y, Z);
  
  return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;


int main(){

  string s;
  cin >> s;

  vector<ll> inp;
  REP(i, 0, s.size()){
    if (s.substr(i, 1) == "<")
      inp.push_back(1);
    if (s.substr(i, 1) == ">")
      inp.push_back(-1);
  }
  if (s.substr(s.size()-1, 1) == "<")
    inp.push_back(1);
  if (s.substr(s.size()-1, 1) == ">")
    inp.push_back(-1);

  ll count=0;
  vector<ll> v;
  REP(i, 0, s.size()+1){
    if (inp[i] != inp[i+1]) {
      if (inp[i] == 1)
        v.push_back(count+1);
      else
        v.push_back(-1 * (count+1));
      count = 0;
    }
    else
      count++;
  }

  if(v[v.size()-1] > 0)
    v[v.size()-1]--;
  if(v[v.size()-1] < 0)
    v[v.size()-1]++;

  // for(auto itr=v.begin(); itr!=v.end(); ++itr)
  //   cout << (*itr) << " ";
  // cout << endl;

  ll ans = 0;
  ll index = 0;
  ll last_index = 0;
  ll before = 0;
  ll before_before = 0;
  for(auto itr=v.begin(); itr!=v.end(); ++itr){
    if ( (before < 0) and (*itr) > 0 ) {
      last_index = index;
      ll m = max(abs(before), abs(before_before));
      ans += (m) * (m+1) / 2;
      // cout << m << endl;
      ll other = abs(before) + abs(before_before) - m - 1;
      ans += max((ll)0, other * (other+1) / 2);
    }
    before_before = before;
    before = (*itr);
    index ++;
  }

  // cout << "last_index: " << last_index << endl;
  if ( (v.size() - 1) == last_index ) {
    ans += abs(v[last_index]) * (abs(v[last_index]) + 1) / 2;
  }
  else if ( (v.size() - 2) == last_index ) {
    ll m = max(abs(v[last_index]), abs(v[last_index+1]));
    ans += m * (m+1) / 2;
    ll other = abs(v[last_index]) + abs(v[last_index+1]) - m - 1;
    ans += other * (other+1) / 2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8692
#include <bits/stdc++.h>
using namespace std;
#define mt make_tuple
#define mp make_pair
#define int long long

int X, Y, A, B, C, T, tx = 1, ty = 1, P[100005], Q[100005], R[100005], SP[100005], SQ[100005];
pair<int, int> O[300005];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> X >> Y >> A >> B >> C;
	for (int i = 1; i <= A; i++) cin >> P[i];
	for (int i = 1; i <= B; i++) cin >> Q[i];
	for (int i = 1; i <= C; i++) cin >> R[i];
	sort(P + 1, P + 1 + A, greater<int>());
	sort(Q + 1, Q + 1 + B, greater<int>());
	for (int i = 1; i <= A; i++) SP[i] = P[i] + SP[i - 1];
	for (int i = 1; i <= B; i++) SQ[i] = P[i] + SQ[i - 1];
	for (int i = 1; i <= A; i++) O[i] = mp(P[i], 0);
	for (int i = 1; i <= B; i++) O[i + A] = mp(Q[i], 1);
	for (int i = 1; i <= C; i++) O[i + A + B] = mp(R[i], 2);
	sort(O + 1, O + 1 + A + B + C, greater<pair<int, int> >());
	for (int i = 1; i <= A + B + C; i++) {
		if (O[i].second == 0) {
			if (X) T += O[i].first, X--, tx++;
		} else if (O[i].second == 1) {
			if (Y) T += O[i].first, Y--, ty++;
		} else {
			if (P[min(A, tx + X - 1)] <= Q[min(B, ty + Y - 1)] && X) T += O[i].first, X--;
			else if (Y) T += O[i].first, Y--;
			else if (X) T += O[i].first, X--;
		}
	}
	cout << T << '\n';
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int h1,s1,h2,s2;
    cin>>h1>>s1>>h2>>s2;
    while(h1!=0 || h2!=0){
    h2=h2-s1;
    if(h2<=0){cout<<"Yes"<<endl;return 0;}
    else{
    h1=h1-s2;
    if(h1<=0){cout<<"No"<<endl;return 0;}
   } }


}


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

int n;
int a[100000];
int cnt[100001];

int main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	for (i = 0; i < n; i++) cnt[a[i]]++;
	
	int type = 0;
	int mod = 0;
	for (i = 0; i <= 100000; i++) {
		if (cnt[i] == 0) continue;
		mod += (cnt[i] - 1);
		type++;
	}
	if (mod % 2) type--;
	
	cout << type << endl;
	return 0;
}

Measured memory_bytes: 1024
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


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

	cin >> N >> K;
	vector<int>p(N);
	for (auto &i : p) {
		cin >> i;
		i--;
	}
	vector<long long int>score(N);
	vector<long long int>loop(N);
	for (auto &i : score) {
		cin >> i;
	}
	vector<vector<long long int>>dp(N, vector<long long int>(N + 1));
	for (int i = 0; i < N; i++) {
		int cn = i;
		for (int j = 1; j <= N; j++) {
			cn = p[cn];
			dp[i][j] = dp[i][j - 1] + score[cn];
			if (cn == i) {
				loop[i] = j;
			//	cout << i << " " << j << endl;
				break;
			}
		}
	}
	long long int ans = -MOD;
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= min(loop[i],K); j++) {
			if (dp[i][loop[i]] > 0) {
				ans = max(ans, dp[i][j] + (K - j) / loop[i] * dp[i][loop[i]]);
			}
			else {
				ans = max(ans, dp[i][j]);
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 198816
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
ll gcd (ll a,ll b){
    return b ? gcd(b,a%b) : a;
}
main(){
    int N;
    cin >> N;
    vector<int> V(N+1);
    rep(i,0,N+1)cin >> V[i];
    sort(V.begin(), V.end());
    int dif = V[1] - V[0];
    rep(i,0,N)dif = gcd(dif, V[i+1] - V[i]);
    cout << dif << endl;
}

Measured memory_bytes: 640
min' :: Int -> Int -> Int
min' l m = if l <= m then l else m

solve :: Int -> Int -> Int
solve n k | modulo == 0 = 0
          | otherwise   = min' modulo (abs (modulo - k))
    where modulo = n `mod` k

main = do
    s <- getLine
    let (n : k : _) = map read $ words s :: [Int]
    print $ solve n k


Measured memory_bytes: 508
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

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


lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	lli N, M;
	string s, t;
	cin >> N >> M >> s >> t;

	lli x, y;
	lli L = N * (M / extgcd(N, M, x, y));

	for (int i = 0; i < N; i++) {
		lli pos = (L / N) * i;
		if (pos % (L / M) == 0) {
			lli j = pos / (L / M);
			if (s[i] != t[j]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}

	cout << L << endl;
	return 0;
}

Measured memory_bytes: 512
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int a = in.ni();
        int b = in.ni();
        int c = in.ni();
        out.println((c>=a&&c<=b)?"Yes":"No");
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 21332
from collections import deque
n, m = map(int, input().split())
Edge = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
looked = [1 for i in range(n)]
counter = 0
for i in range(n):
    if looked[i]:
        looked[i] = 0
        counter += 1
        queue = deque([i])
        while queue:
            now = deque.popleft(queue)
            for j in Edge[now]:
                if looked[j]:
                    deque.append(queue, j)
                    looked[j] = 0
print(counter-1)

Measured memory_bytes: 26456
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class Read>void in(Read &x){
    x=0;
    int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        f|=(ch=='-');
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x=f?-x:x;
    return;
}
int n,a[100005],f[100005];
int main(){
    in(n);
    for(int i=1;i<=n;i++)in(a[i]);
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    f[2]=abs(a[1]-a[2]);
    for(int i=3;i<=n;i++)f[i]=min(f[i-1]+abs(a[i]-a[i-1]),f[i-2]+abs(a[i]-a[i-2]));
    printf("%d\n",f[n]);
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cmath>

#define maxn 1005
using namespace std;

int main()
{
	int a;
	int n;
	cin>>n>>a;
	int ans=min(a,n);
	int c=a+n-ans;
	for(int i=1;i<=c;i++)
		cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while(getline(ss,x,c)) v.emplace_back(x); return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
const ll MOD=1e9+7;
inline ll f(ll x){return x*(x-1ll)/2;}
int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int k,s;
  cin>>k>>s; ++k;
  ll re=f(s+2);
  if(k<=s) re-=3*f(s-k+2);
  if(2*k<=s) re+=3*f(s-2*k+2);
  cout<<re<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
	int a[5][30];
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 13; j++){
			a[i][j] = 0;
		}
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int x;
		char o;

		cin >> o >> x;
		x--;
		if (o == 'S'){
			a[0][x] = 1;
		}
		if (o == 'H'){
			a[1][x] = 1;
		}
		if (o == 'C'){
			a[2][x] = 1;
		}
			if (o == 'D'){
				a[3][x]=1;
			}
	}
	
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 13; j++){
			if (a[i][j]==0){
				if (i == 0)cout << 'S' << ' ' << j + 1 << endl;
				if (i == 1)cout << 'H' << ' ' << j + 1 << endl;
				if (i == 2)cout << 'C' << ' ' << j + 1 << endl;
				if (i == 3)cout << 'D' << ' ' << j + 1 << endl;

			}
		}
	}















	return 0;
}

Measured memory_bytes: 3004
#include<bits/stdc++.h>
#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 fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
bool isSquare(ll n) {
	ll d = (ll)sqrt(n) - 1;
	while (d * d < n) ++d;
	return d * d == n;
}

/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/














int N; ll A[101010];
ll X[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];

	X[0] = 0;
	rep(i, 0, N) {
		if (i % 2 == 0) X[0] += A[i];
		else X[0] -= A[i];
	}

	rep(i, 1, N) X[i] = 2 * A[i - 1] - X[i - 1];

	rep(i, 0, N) {
		if (i) printf(" ");
		printf("%lld", X[i]);
	}
	printf("\n");
}







Measured memory_bytes: 2944
#include <stdio.h>
int main()
{
	int n, x, i, j, k, c=0;
	while(1){
		scanf("%d %d", &n, &x);
		if(n==0 && x==0){
			break;
		}
		for(i=1; i<n-1; i++){
			for(j=i+1; j<n; j++){
				for(k=j+1; k<n+1; k++){
					if(i+j+k==x){
						c+=1;
					}
				}
			}
		}
		printf("%d\n", c);
		c=0;
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int main() {
    int N;
    cin >> N;
    map<string, vector<P>> ma;
    for (int i = 0; i < N; i++) {
        string s;
        int p;
        cin >> s >> p;
        ma[s].emplace_back(P(p, i + 1));
    }
    for (auto m : ma) {
        sort(m.second.begin(), m.second.end(), greater<P>());
        for (int i = 0; i < m.second.size(); i++) {
            cout << m.second[i].second << endl;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<math.h>
#include<utility>
#include<queue>
#include<map>

using namespace std;
const int MAX = 1000000;

struct process {
    string name;
    int time;
};

class Queue {
    private:
        process q[MAX];
        int head = 0;
        int tail = 0;

    public:
        void init();
        void enqueue(process x);
        process dequeue();
        bool isFull();
        bool isEmpty();
};

void Queue::init(){
    head = tail = 0;
}

void Queue::enqueue(process x){
    if(isFull()){
        cout << "入れられません" << endl;
        return;
    } else {
        q[tail] = x;
        if(tail == MAX - 1) tail = 0;
        else tail++;
    }
}

process Queue::dequeue(){
    if(isEmpty()){
        process error;
        error.name = "error";
        error.time = NULL;
        cout << "キューは空です" << endl;
        return error;
    } else {
        process retval = q[head];
        if(head == MAX-1) head = 0;
        else  head++;
        
        return retval;
    }
}

bool Queue::isFull(){
    return head == (tail+1)%MAX;
}

bool Queue::isEmpty() {
    return head == tail;
}



int main(){
    int n, q;
    cin >> n >> q;
    int sum_time = 0;

    Queue queue;
    process tmp;
    vector<process> p(n);
    for(int i=0;i<n;i++) {
        cin >> p[i].name >> p[i].time;
        queue.enqueue(p[i]);
    }

    while(!queue.isEmpty()){
        tmp = queue.dequeue();

        if(tmp.time > q){
            sum_time += q;
            tmp.time -= q;
            queue.enqueue(tmp);
        } else {
            sum_time += tmp.time;
            cout << tmp.name << " " << sum_time << endl;
        }
    }
}


Measured memory_bytes: 21452
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#ifdef STOPIT
#define debug(...) 0
#else
#define debug(...)\
do {\
  std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;\
} while (false)
#endif

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  rep(i, 1, 10) rep(j, 1, 10) {
    if (i * j == n) {
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include <stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
typedef long long ll;

int w, h,cn[1000];
bool field[51][51];

void dfs(int i,int k) {
	field[i][k] = 0;
	FOR(x, -1, 2) {
		FOR(y, -1, 2) {
			int nx = k + x, ny = i + y;
			if (nx < w&&nx >= 0 && ny < h&&ny >= 0 && field[ny][nx] == 1)dfs(ny, nx);
		}
	}
	return;
}

int main(void)
{
	int c = 0;
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0)break;
		FOR(i, 0, h)FOR(k, 0, w)cin >> field[i][k];

		FOR(i, 0, h)FOR(k, 0, w) {
			if (field[i][k] == 1) {
				dfs(i, k);
				cn[c]++;
			}
		}
		ct(cn[c]);
		c++;
	}

	return 0;
}



Measured memory_bytes: 3236
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <stdlib.h>
#include <string>
#include <vector>

#define el endl
#define fd fixed
#define INF INT_MAX/2-1

using namespace std;

int main() {
  int x, y, s, max_sum;
  while (cin >> x >> y >> s, x|y|s) {
    max_sum = 0;
    for (int i = 1; i < s; i++)
      for (int j = i; j < s; j++)
        if (i*(100+x)/100 + j*(100+x)/100 == s && i*(100+y)/100 + j*(100+y)/100 > max_sum)
          max_sum = i*(100+y)/100 + j*(100+y)/100;
    cout << max_sum << el;
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
int main()
{
    int N, x;
    cin >> N >> x;
    vector<int> a(N);
    rep(i, N)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int i = 0, count = 0;
    while (i < N)
    {
        x -= a[i];
        count++;
        if (x == 0)
        {
            cout << count << endl;
            return 0;
        }
        else if (x < 0)
        {
            cout << count - 1 << endl;
            return 0;
        }
        else if (i == N - 1 && x > 0)
        {
            cout << count - 1 << endl;
            return 0;
        }
        i++;
    }
}

Measured memory_bytes: 256
# Connect Cities
# Union Findデータ構造（素集合データ構造）
 
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
 
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
 
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n
 
	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]
 
	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)
 
		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x
 

		self.parents[y]=x

n,m=input2()
AB=[input_array() for _ in range(m)]
 
uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1

print(ans-1)

Measured memory_bytes: 28896
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    string s1,s2;cin>>s1>>s2;
    if(s1.at(0)==s2.at(2) && s1.at(1)==s2.at(1) && s1.at(2)==s2.at(0)){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const double inf = 1e9;
const int mod = 1e5;
const int MAX = 5005;

struct data {P l, r;};

int main() {
    while (true) {
        int n, w, d; cin >> n >> w >> d;
        if (n == 0 && w == 0 && d == 0) break;
        deque<data> q;
        q.push_back(data{P(0,0),P(d,w)});
        rep(i,n) {
            int p, s; cin >> p >> s;
            data cood;
            int sz = q.size();
            rep(i,sz) {
                data x = q.front(); q.pop_front();
                if (i+1 == p) cood = x;
                else q.push_back(x);
            }
            int s_w = cood.r.second - cood.l.second;
            int s_d = cood.r.first - cood.l.first;
            s %= 2*(s_w + s_d);
            // cout << "A" << s_w << " " << s_d << endl;
            if (s < s_w || (s_w+s_d < s && s < 2*s_w+s_d)) {
                if (s > s_w) s = 2*s_w+s_d-s;
                data q1 = {cood.l,P(cood.r.first,cood.l.second+s)};
                data q2 = {P(cood.l.first,cood.l.second+s),cood.r};
                if (2*s > s_w) swap(q1,q2);
                q.push_back(q1); q.push_back(q2);
            }
            if ((s_w < s && s < s_w+s_d) || 2*s_w+s_d < s) {
                if (s > s_w+s_d) s = 2*(s_w+s_d)-s;
                else s -= s_w;
                data q1 = {cood.l,P(cood.l.first+s,cood.r.second)};
                data q2 = {P(cood.l.first+s,cood.l.second),cood.r};
                if (2*s > s_d) swap(q1,q2);
                q.push_back(q1); q.push_back(q2);
            }
            // rep(i,q.size()) {
            //     data x = q.front(); q.pop_front();
            //     cout << x.l.first << x.l.second<< " " << x.r.first << x.r.second << endl;
            //     q.push_back(x);
            // }
            // cout << endl;
        }
        vector<int> area;
        while (!q.empty()) {
            data x = q.front(); q.pop_front();
            // cout << x.l.first << x.l.second << " " << x.r.first << x.r.second << endl;
            int s = (x.r.first-x.l.first)*(x.r.second-x.l.second);
            // cout << s << endl;
            area.push_back(s);
        }
        sort(area.begin(),area.end());
        rep(i,area.size()) {
            if (i != area.size()-1) cout << area[i] << " ";
            else cout << area[i] << endl;
        }
    }
}


Measured memory_bytes: 3148
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String s = sc.next();
		
		if(a<3200) {
			System.out.println("red");
		}else {
			System.out.println(s);
		}
	
		
		
	}
}

Measured memory_bytes: 22996
#include<stdio.h>
int m[1000000];
int main()
{

    int a,b,i,j;

    scanf("%d",&a);
    for(j=1 ; j<a ; j++)
    {
        scanf("%d",&b);
        m[b]++;
    }
    for(i=1 ; i<=a ; i++)
    {
        printf("%d\n",m[i]);
    }




    return 0;
}


Measured memory_bytes: 2460
coo=list(map(int, input().split()))
tcoo=coo[0]
acoo=coo[1]
k=coo[2]
if k >= tcoo:
    k-=tcoo
    tcoo=0
    if k >= acoo:
        acoo=0
    else:
        acoo-=k
else:
    tcoo-=k
print(str(tcoo)+" "+str(acoo))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,i;
  string s,t,m="";
  cin>>n;
  cin>>s>>t;
  for(i=0;i<n;i++)
  {
    m+=s[i];
    m+=t[i];
  }
  cout<<m;
 return 0;
}

Measured memory_bytes: 256
use proconio::input;

macro_rules! chmax {
    ($max_v: expr, $v: expr) => {
        if $v > $max_v {
            $max_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        n: usize,
        abc: [(i64, i64, i64); n],
    };
    let mut dp = vec![vec![0; 3]; n + 1];
    for (i, &(a_i, b_i, c_i)) in abc.iter().enumerate() {
        chmax!(dp[i + 1][0], std::cmp::max(dp[i][1] + a_i, dp[i][2] + a_i));
        chmax!(dp[i + 1][1], std::cmp::max(dp[i][0] + b_i, dp[i][2] + b_i));
        chmax!(dp[i + 1][2], std::cmp::max(dp[i][0] + c_i, dp[i][1] + c_i));
    }
    let ans = dp[n].iter().max().unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 11532
/*  
     author : masaow    
     g++ : 17.3.20  
*/        
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             x.begin(),x.end() 
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;  
/*  
    time : 10 : 14    
    date : 22.01.2020
*/    
// int L,R,mid,target,idx ;
int tests() 
{   int n ,i ; 
    cin >> n ; 
    int s = 0 ; 
    vector <int> a(n) ;
    forn(i,0,n)
        cin >> a[i],s += a[i] ;
    
    int v1 =  s+n-1 ;
       v1 /= n ; 
    int ans = 2e9 ; 
    int best  = 0 ;
    forn(i,0,n)
       best += (a[i]-v1)*(a[i]-v1) ; 
    ans  = min(ans,best) ; 
    s /= n ; 
    v1 = s  ;   
   best  = 0 ; 
    forn(i,0,n)
       best += (a[i]-v1)*(a[i]-v1) ; 
    ans  = min(ans,best) ; 
    cout << ans ; 
    return 0 ; 
}
int main(){
    I__O ;  
    int cases = 1 ; 
    //cin >> cases;  
    while(cases--)
      tests(); 
  return 0 ; 
}

Measured memory_bytes: 256
def dis(a):
  return ((a[0]-a[2])*(a[0]-a[2])+(a[1]-a[3])*(a[1]-a[3]))**0.5

n = int(input())
p=[]
for i in range(n):
  a,b = map(int,input().split())
  p.append([a,b])
d=[[0]*n for _ in range(n)]
s=0
for i in range(n):
  for j in range(i+1,n):
    g = dis(p[i]+p[j])
    d[i][j]=d[j][i]=g
    s+=2*g
print("%.7f"%(s/n))


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

int n, m;
int A, B, C, cnt;
ll a[MAX], b[MAX], c[MAX], d[MAX], s1[MAX], s2[MAX];

int main()
{
    cin >> n >> m >> A >> B >> C;
    for(int i = 1; i <= A; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= B; i++) scanf("%lld", &b[i]);
    for(int i = 1; i <= C; i++) scanf("%lld", &c[i]);
    sort(a+1, a+A+1, greater<int>()), sort(b+1, b+B+1, greater<int>()), sort(c+1, c+C+1, greater<int>());
    for(int i = 1; i <= C; i++){
        s1[i] = s1[i-1]+c[i];
    }
    for(int i = 1; i <= min(A, n); i++) d[++cnt] = a[i];
    for(int i = 1; i <= min(B, m); i++) d[++cnt] = b[i];
    sort(d+1, d+cnt+1, greater<int>());
    for(int i = 1; i <= cnt; i++){
        s2[i] = s2[i-1]+d[i];
    }
    ll ans = -1e18;
    for(int i = 0; i <= C; i++){
        if(i > n+m) break;
        ll s = s1[i]+s2[n+m-i];
        ans = max(ans, s);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 20096
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static long[] ans;

        static void Main(string[] args)
        {
            //[summary]C - Typical Stairs
            var line = ReadLine();
            int N = line[0];
            int M = line[1];

            ans = new long[N + 1];
            ans[0] = 1;

            GetBrokenFloors(M);

            for(int i = 1; i <= N; i++)
            {
                if (ans[i] == -1)
                {
                    ans[i] = 0;
                }
                else
                {
                    if (i == 1)
                    {
                        ans[i] = 1;
                    }
                    else
                    {
                        long sum = ans[i - 1] + ans[i - 2];
                        ans[i] = sum % 1000000007;
                    }
                }
            }

            Console.WriteLine(ans[N]);
        }

        static void GetBrokenFloors(int M)
        {
            for (int i = 0; i < M; i++)
            {
                int a = int.Parse(Console.ReadLine());
                ans[a] = -1;
            }
        }

        static List<int> ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => int.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 14164
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

def cmb_1(n, r):
    r = min(n - r, r)
    if (r < 0) or (n < r):
        return 0

    if r == 0:
        return 1

    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N = getN()
A = [0] + getList()
imos = copy.deepcopy(A)
for i in range(1, N):
    imos[i + 1] += imos[i]

ans = 0
for i in Counter(imos).items():
    ans += cmb_1(i[1], 2)
print(ans)

Measured memory_bytes: 45792
#
# abc122 b
#
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """ATCODER"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """HATAGAYA"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """SHINJUKU"""
        output = """0"""
        self.assertIO(input, output)


def resolve():
    S = input()

    ans = 0
    for i in range(len(S)):
        t = 0
        if S[i] == "A" or S[i] == "C" or S[i] == "G" or S[i] == "T":
            t += 1
            for j in range(i+1, len(S)):
                if S[j] == "A" or S[j] == "C" or S[j] == "G" or S[j] == "T":
                    t += 1
                else:
                    break
        ans = max(ans, t)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16220
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

a,b,n = inL()

x = min(b-1,n)
print(int(a*x/b)-a*int(x/b))


Measured memory_bytes: 61888
#include <vector>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <string>
#include <utility>
#include <stack>
#include <numeric>
#include <random>
#include <algorithm>
#include <queue>
using namespace std;

#define rep(i, b, e) for(i = b; i < e; ++i)
#define repr(i, b, e) for (i = b; i >= e; --i)
#define ull unsigned long long int
#define ll long long int
#define pint pair<int, int>

#define M_DEBUG 1
#define PI 3.141592653589793
#define MOD 100000007

#define M 1000000000

#define E '\n'

ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;

int xy[][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

int bfs(vector<string> maze, pint p) {
    int maxfar = 0;
    vector<vector<int> > dist(h, vector<int>(w, -1));
    dist[p.second][p.first] = 0;
    queue<pint> q;
    q.push(p);
    while (!q.empty()) {
        pint pp = q.front();
        q.pop();
        x = pp.first;
        y = pp.second;
        for (int i = 0; i < 4; ++i) {
            int xx = xy[i][0] + x;
            int yy = xy[i][1] + y;
            if (xx < w && yy < h && xx >= 0 && yy >= 0 && maze[yy][xx] != '#' && dist[yy][xx] < 0) {
                d = dist[y][x] + 1;
                dist[yy][xx] = d;
                q.push(make_pair(xx, yy));
            }
        }
    }

    for (int i = 0; i < h; ++i) 
        for (int j = 0; j < w; ++j) 
            if (dist[i][j] > maxfar) 
                maxfar = dist[i][j];

    return maxfar;
}

int main(void){
    vector<string> maze;
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        string ss;
        cin >> ss;
        maze.emplace_back(ss);
    }
    int maxdist = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (maze[i][j] == '#')
                continue;
            b = bfs(maze, make_pair(j, i));
            if (b > maxdist) 
                maxdist = b;
        }
    }


    cout << maxdist << endl;


    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        
        if(Math.abs(a-c)<= d || (Math.abs(a-b)<= d && Math.abs(b-c)<= d)){
            System.out.println("Yes");
        }else{
        System.out.println("No");
        }
    }
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   int r,c;
   cin>>r>>c;
   string s;
   for (int i=0;i<r;i++){
    cin>>s;
    cout<<s<<endl<<s<<endl;
   }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int fibona(int );

int depth[50];

int main(){
    int num, i;

    for( i = 0; i < 50; i++) {
      depth[i] = -1;
    }

    scanf("%d", &num);
    printf("%d\n", fibona(num));

    return 0;
}

int fibona(int n){
    if( n == 0 || n == 1) {
      return depth[n] = 1;
    }
    if( depth[n] != -1) {
      return depth[n];
    }
    return depth[n] = fibona(n - 1) + fibona(n - 2);
}



Measured memory_bytes: 2112
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]

X = sorted(AB, key= lambda x: (x[1], x[0]))

flag = True
time = 0
for task in X:
    if time + task[0] > task[1]:
        flag = False
        break
    time += task[0]

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 91476
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#define rep(i,n) for(int i = 0;i < n;i++)
#define N 20005
using namespace std;
int main(){
    int Testcase;
    cin >> Testcase;
    while(Testcase--){
        string s1,s2;
        cin>>s1>>s2;
        int l1=s1.length(),l2=s2.length();
        int dp[1005][1005];
        rep(i,l1+1){
            rep(j,l2+1){
                dp[i][j]=0;
            }
        }
        rep(i,l1){
            rep(j,l2){
                if(s1[i]==s2[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        cout << dp[l1][l2]<<endl;
    }
}

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

m = sorted([tuple(map(int, input().split())) for _ in range(N)])
need = M #残りの欲しいエナドリの数
totalprice = 0 #現時点での金額

for i, nowmer in enumerate(m):
    nowprice = nowmer[0]
    stock = nowmer[1]
    totalprice += nowprice * min(need, stock)
    need -= min(need, stock)
    if need <= 0: break

print(totalprice)


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

int main() {
	int H,W;
	while(1) {
		scanf("%d%d",&H,&W);
		if (H==0 && W ==0) break;
		for(int j=0;j<H;++j) {
			for(int i=0;i<W;++i) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 2592
// abc136d.cpp : Gathering Children
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define up(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define ot(x) cout<<(x)
#define ote(x) cout<<(x)<<endl

int main(){
  string S; cin>>S;
  int n = S.length();

  vi divpoint, group;
  bool high_low = false; // low
  up(i,0,n,1){
    if(!high_low && S[i]=='R'){ // ↑
      divpoint.push_back(i); // グループの切れ目
      high_low = true; // hi
    }
    else if(high_low && S[i]=='L'){ // ↓
      group.push_back(i); // グループの集合場所（L側）
      high_low = false; // low
    }
  }
  divpoint.push_back(n);

  vi o(n);
  up(i,0,group.size(),1)
    up(j,divpoint[i],divpoint[i+1],1)
      o[ j%2==group[i]%2?  group[i]: group[i]-1 ]++;

  ot(o[0]); up(i,1,n,1) cout<<" "<<o[i]; ote("");

}

Measured memory_bytes: 1532
#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    if (a >= 13)
        printf("%d\n", b);
    if (a <= 12 && a >= 6)
        printf("%d\n", b / 2);
    if (a < 6)
        printf("0\n");
    return 0;
}

Measured memory_bytes: 128