akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
a = list(map(int, input().split()))
posi = []
nega = []
zero = []
for i in range(n):
    if a[i] < 0:
        nega.append(a[i] * -1)
    elif a[i] > 0:
        posi.append(a[i])
    else:
        zero.append(a[i])
zero = len(zero)
posi.sort()
nega.sort()
lp, ln = len(posi), len(nega)
if k <= lp * ln:
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = lp * ln
        cur = 0
        for i in range(ln)[::-1]:
            while cur < lp and posi[cur] < (m + nega[i] - 1) // nega[i]:
                cur += 1
            cnt -= cur
        if cnt >= k:
            l = m
        else:
            r = m
    print(-1 * l)
elif k <= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2):
    print(0)
else:
    k -= n * (n - 1) // 2 - (lp * (lp - 1) // 2) - (ln * (ln - 1) // 2)
    l, r = 0, 10 ** 18
    while r - l > 1:
        m = (l + r) // 2
        cnt = 0
        cur = ln - 1
        for i in range(ln):
            while cur and nega[cur] > m // nega[i]:
                cur -= 1
            if cur > i:
                cnt += cur - i
        cur2 = lp - 1
        for i in range(lp):
            while cur2 and posi[cur2] > m // posi[i]:
                cur2 -= 1
            if cur2 > i:
                cnt += cur2 - i
        if cnt >= k:
            r = m
        else:
            l = m
    print(r)

Measured memory_bytes: 99984
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] H = new int[N];
        for (int i = 0; i < N; i++) {
            H[i] = sc.nextInt();
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N - 1; i++) {
            if (H[i] <= H[i + 1] - 1) {
                // ok. making H[i + 1] lower than current status.
                H[i + 1] -= 1;
            } else if (H[i] == H[i + 1]) {
                // ok. no change.
            } else {
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");
        return;
    }

}

Measured memory_bytes: 50092
import qualified Data.ByteString.Char8 as C
import Data.List
import qualified Data.Set as S
import Data.Vector.Generic ((!))
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack

sol v = if cnt>0 then "Fennec" else "Snuke"
  where
  n = U.head v
  u = U.tail v
  tree = build n $ U.unfoldrN (n-1) split2 u
  split2 u = Just ((U.head v,U.last v), w) where (v,w) = U.splitAt 2 u
  d1 = levels n tree 1
  dn = levels n tree n
  cnt = foldl' (\s i -> if d1!i <= dn!i then s+1 else s-1) 0 [1..n]

build :: Int -> U.Vector (Int, Int) -> V.Vector (U.Vector Int)
build n es = V.create $ do
  v <- VM.replicate (n+1) U.empty
  let add a b = VM.read v a >>= VM.write v a . (U.cons b) 
  U.forM_ es $ \(a,b) -> do
    add a b
    add b a
  return v

levels :: Int -> V.Vector (U.Vector Int) -> Int -> U.Vector Int
levels n tree v0 = U.create $ do
  d <- UM.replicate (n+1) maxBound
  UM.write d v0 0
  let
    loop q = case S.minView q of
      Nothing -> return ()
      Just ((lvl,nd),q') ->
        let
          f q v = do
            lvl0 <- UM.read d v
            if lvl+1 >= lvl0
              then return q
              else do
                UM.write d v (lvl+1)
                return . S.insert (lvl+1,v) $ S.delete (lvl0,v) q
        in
          U.foldM f q' (tree!nd) >>= loop
  loop $ S.singleton (0,v0)
  return d

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

int main() {
  string S;
  cin>>S;
  string ans;
  rep(i,S.size()){
    if(S[i]=='0') ans += '0';
    else if(S[i]=='1') ans += '1';
    else if(S[i]=='B'&&ans.size()!=0) ans.pop_back();
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define main() int main()
#define ff1(i,n) for(int i=1;i<=n;++i)
#define ff0(i,n) for(int i=0;i<n;++i)
#define pi acos(-1.0)
#define ms(a, x) memset(a, x, sizeof(a))
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define binarycount __builtin_popcount(x)
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define fir first
#define sec second
#define debug(x) cout<<x<<'\n'
#define sa(a) scanf("%d", &a)
#define sab(a, b) scanf("%d%d", &a, &b)
#define pa(a) printf("%d",a)
#define pab(a,b) printf("%d%d",a,b)
#define pii pair<string,int>
using namespace std;
#define maxn 100005
const int inf = 0x3f3f3f3f;
const int mod = 9973;
const double eps = 1e-8;
ll gcd(ll a, ll b) {return b==0?a:gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}
int max(int x,int y){if(x>y) return x;return y;}
ll powmod(ll a,ll b){
    ull ans = 1, pow = a%mod;
    while(b) { if(b&1) ans = (ans*pow)%mod; pow = (pow*pow)%mod; b >>= 1; }
    return ans%mod;
}

struct Edge
{
    int to, next, val;
} e[maxn << 1];
int head[maxn], tot = 0;
int dis[maxn], dep[maxn], pre[maxn][21];
int n,m,ans;
int d[maxn],c[maxn],dp[maxn];
void init()
{
    ms(head, -1);
    tot = 0;ms(d,0);ans=0;ms(dp,0);
}
void add(int x, int y, int val)
{
    e[tot].to = y, e[tot].val = val, e[tot].next = head[x], head[x] = tot++;
}

int dfs(int x)
{
	if(!c[x]) return 0;
	if(dp[x])return dp[x];
	ll tt=0;
 	for (int i = head[x]; ~i; i = e[i].next)
    {
    	int y=e[i].to;
        tt=max(tt,dfs(y)+1);
    }
    return dp[x]=tt;
}
main()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y,1);
		if(!d[y])d[y]=1;//d为出度 
		if(!c[x])c[x]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(!d[i]){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(dp[i],ans);
		//cout<<dp[i]<<endl;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace std;
long long n,a[200010],ans,x;
int main(){
    cin>>n;
    for (long long i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    ans+=a[n-1];
    for (long long i=n-2;i>0;i--){
        ans=ans+a[i];
        x++;
        if (x+2==n) break;
        ans=ans+a[i];
        x++;
        if (x+2==n) break;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
  vector<int> A(4);
  rep(i,4) cin >> A[i];
  sort(A.begin(),A.end());
  if(A[0] == 1 && A[1] == 4 && A[2] == 7 && A[3] == 9){
    puts("YES");
  }
  else puts("NO");
  return 0;
}


Measured memory_bytes: 256
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[]) {
  ll N, x;
  cin >> N >> x;
  vector<ll> a(N);
  for (size_t i = 0; i < a.size(); i++) {
    ll temp = 0;
    scanf("%lld", &temp);
    a[i] = temp;
    // cout<<temp<<endl;
  }
  sort(a.begin(), a.end());
  ll ans = 0;
  for (size_t i = 0; i < a.size(); i++) {
    // cout<<a[i]<<endl;
    if (x >= a[i]) {
      ans++;
      x = x - a[i];
      //cout << ans << endl;
    } else {
      // cout << "break" << endl;
      break;
    }
    if (i == a.size() - 1 && x != 0) {
      ans--;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
rows, columns = map(int, input().split())
a = []
for i in range(rows):
    a.append(list(map(int, input().split())))
for i in range(rows):
    a[i].append(sum(a[i]))

b = [sum(i) for i in zip(*a)]
a.append(b)

for r in a:
    print(" ".join(str(i) for i in r))



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

#define MAX 500000

struct Node
{
	int key;
	Node *parent, *left, *right;
public:
	Node() { parent = left = right = NULL; }
};

Node *root;

void insert(int u)
{
	Node *y = NULL; //x??????
	Node *x = root; //???????????§??????
	Node *z = new Node();
	z->key = u;
	//?????????????????§?§????
	while (x != NULL) {
		y = x;
		if (z->key < x->key)
			x = x->left;
		else x = x->right;
	}
	z->parent = y;

	//?????????????????????????????\
	if (y == NULL) root = z;
	else if (z->key < y->key) y->left = z;
	else y->right = z;
}

Node *findNode(Node *n, int u)
{
	while (n != NULL && n->key != u) {
		if (u < n->key) n = n->left;
		else n = n->right;
	}
	return n;
}

Node *getMin(Node *x)
{
	while (x->left != NULL)
		x = x->left;
	return x;
}

//??????????????§?¬???????????±???????
Node *getNext(Node *x)
{
	//????????????????????°??????????????§????°??????????????±???????
	if (x->right != NULL) 
		return getMin(x->right);
		
	//???????????°??????????????£???????????????????????????????????¨?????????????????????????±???????
	Node *y = x->parent;
	while (y != NULL&&y->right == x) {
		x = y;
		y = y->parent;
	}
	return y;
}

void deleteNode(Node *z)
{
	Node *x, *y;

	//y : ?????????????????????????£? ?????????	
	if (z->left == NULL || z->right == NULL) y = z; //??????????????\?????????????????????
	else y = getNext(z); //??????????????°??????????????§??????

	//x : y??????????????? ?????????
	if (y->left != NULL) x = y->left;
	else x = y->right;
 
	//y???????????????????????????x??????????????????
	if (x != NULL) x->parent = y->parent;
	if (y->parent == NULL) root = x;
	else if (y == y->parent->left)
		y->parent->left = x;
	else y->parent->right = x;
		
	//getNext()??§y?????????????????´???????????????z????????????
	if (y != z) z->key = y->key;

	//y?????????
	free(y);
}

void Preorder(Node *n)
{
	if (n == NULL) return;
	printf(" %d", n->key);
	Preorder(n->left);
	Preorder(n->right);
}

void Inorder(Node *u)
{
	if (u == NULL) return;
	Inorder(u->left);
	printf(" %d", u->key);
	Inorder(u->right);
}

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

	char order[20];
	int z;
	for (int i = 0; i < n; i++) {
		scanf("%s", order);
		switch (order[0])
		{
		case 'd':
			scanf("%d", &z);
			deleteNode(findNode(root, z));
			break;
		case 'f':
			scanf("%d", &z);
			if (findNode(root, z) != NULL) printf("yes\n");
			else printf("no\n");
			break;
		case 'i':
			scanf("%d", &z);
			insert(z);
			break;
		case 'p':
			Inorder(root);
			printf("\n");
			Preorder(root);
			printf("\n");
			break;
		
		default:
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 19792
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int t = n;
  bool a = false;
  for (int i=1; i<=n; i++) {
    if (t%10 == 7) {
      a = true;
    }
    t /= 10;
  }
  if (a == true) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int main() {
    stack<int> S1;
    stack<pair<int, int> > S2;
     char ch;
     int sum = 0;
   
     for ( int i = 0; cin >> ch; i++ ) {
         if ( ch == '\\' ) S1.push(i);
         else if ( ch == '/' && S1.size() > 0 ) {
            int j = S1.top(); S1.pop();
             sum += i - j;
             int a = i - j;
             while ( S2.size() > 0 && S2.top().first > j ) {
                 a += S2.top().second; S2.pop();
                 }
             S2.push(make_pair(j, a));
             }
     }
    
     vector<int> ans;
     int t = 0;
    while ( S2.size() > 0 ) { ans.push_back(S2.top().second); S2.pop(); }
     reverse(ans.begin(), ans.end());
     cout << sum << endl;
     cout << ans.size();
     for ( int i = 0; i < ans.size(); i++ ) {
         cout << " ";
         t += ans[i];
         cout << ans[i];
         }
     cout << endl;
    
     return 0;
    }


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
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 (a>b) { a=b; return 1; } return 0; }

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

    int n; cin >> n;
    vei a(n); rep(i,n) cin >> a[i];
    reverse(all(a));
    rep(i,n) {
        if(i != n - 1)cout << a[i] << " ";
        else cout <<a[i] << endl;
    }

}




Measured memory_bytes: 3124
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scn =new Scanner(System.in);
		int n = scn.nextInt(), m = scn.nextInt(), o = scn.nextInt();
		int min = Math.min(Math.min(n,m),o);
		int max = Math.max(Math.max(n, m), o);
		System.out.println(max-min);


		scn.close();
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> r(n);
    vector<int> l(n);
    int res = 0;
    for(int i=0; i<n; i++){
        cin >> l[i] >> r[i];
        res = res + (r[i] - l[i] + 1);
    }
    cout << res << endl;
    return 0;
}




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

char pair_char(char c) {
    switch (c) {
        case 'i': case 'w':
            return c;
        case '(':
            return ')';
        case ')':
            return '(';
    }
}

int main() {
    string s; cin >> s;
    int count = 0;
    for (int i = 0; i < s.size()/2; i++) {
        if (s[i] != pair_char(s[s.size()-i-1])) {
            count++;
        }
    }
    if (s.size() % 2 == 1) {
        if (s[s.size()/2] != pair_char(s[s.size()/2])) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
int main(){
  int n,i;
  int *x;
  int minv=0,maxv;

scanf("%d",&n);
if(n<2||n>200000)return 0;

x = (int *)malloc(sizeof(int) * n);

for(i = 0;i<n;i++){
scanf("%d",&x[i]);
if(x[i]<1||x[i]>1000000001)return 0;
}


minv = x[0];
maxv=x[1]-x[0];
for(i=1;i<n;i++) {
  if(maxv<x[i]-minv){
  maxv = x[i]-minv;
}
  if(x[i]<minv){
  minv = x[i];
}
}

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

return 0;
}



Measured memory_bytes: 2636
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

int main(){
   int n,a,b,c,d;
   cin >> n >> a >> b >> c >> d;
   string s; cin >> s;
   if(c<d){
      for(int i=a;i<d-1;i++){
         if(s[i]=='#'&&s[i+1]=='#'){
            cout << "No" << endl;
            return 0;
         }
      }
      cout << "Yes" << endl;
   }else{
      for(int i = b-2;i<d-1;i++){
         if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){
            cout << "Yes" << endl;
            return 0;
         }
      }
      cout << "No"<<endl;
   }
  
   return 0;
}

Measured memory_bytes: 640
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

# N = int(sys.stdin.readline())
# S = sys.stdin.readline().rstrip().split()
#
# if len(set(S)) == 3:
#     print('Three')
# else:
#     print('Four')

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
ac = 0
bc = 0

A.sort(reverse=True)
for i, a in enumerate(A):
    if i % 2 == 0:
        ac += a
    else:
        bc += a
print(ac - bc)


Measured memory_bytes: 13584
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 28;
const double EPS = 1e-10;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

bool visited[100005];
vector<int> v[100005];
deque<int> ans;
int n, m;

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

	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;

		v[a].push_back(b);
		v[b].push_back(a);
	}

	ans.push_back(1);

	if (v[1].size() == 0) {
		cout << 1 << endl;
		return 0;
	}
	visited[1] = true;

	while (1) {
		int back = ans.back();
		//cout << back << endl;

		int flag = 0;
		for (int i = 0;i < v[back].size();i++) {
			if (visited[v[back][i]] == 0) {
				ans.push_back(v[back][i]);
				flag = 1;
				visited[v[back][i]] = true;
				break;
			}
		}
		if (flag == 0) {
			break;
		}
	}

	while (1) {
		int front = ans.front();

		int flag = 0;
		for (int i = 0;i < v[front].size();i++) {
			if (visited[v[front][i]] == 0) {
				ans.push_front(v[front][i]);
				flag = 1;
				visited[v[front][i]] = true;
				break;
			}
		}
		if (flag == 0) {
			break;
		}
	}
	cout << ans.size() << endl;

	while (ans.size() > 0) {
		cout << ans.front();
		if (ans.size() > 1) cout << " ";
		ans.pop_front();
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 6784
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

struct CountUnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;
    vector<int> cnt;

    CountUnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        cnt.assign(sz, 1);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

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

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)  return;
        if(rank[x] < rank[y]){
            par[x] = y;
            cnt[y] += cnt[x];
        }
        else{
            par[y] = x;
            cnt[x] += cnt[y];
            if(rank[x] == rank[y])  ++rank[x];
        }
    }

    int get_cnt(int x){
        return cnt[find(x)];
    }
};

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

    int n, m, k;
    cin >> n >> m >> k;
    CountUnionFind uf(n);
    vector<vector<int>> graph(n);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
        uf.unite(a, b);
    }
    vector<int> block(n, 0);
    for(int i = 0; i < k; ++i){
        int c, d;
        cin >> c >> d;
        --c, --d;
        if(uf.same(c, d)){
            ++block[c];
            ++block[d];
        }
    }
    for(int i = 0; i < n; ++i){
        int ans = uf.get_cnt(i) - (int)graph[i].size() - block[i] - 1;
        cout << ans;
        cout << ((i == n - 1) ? '\n' : ' ');
    }
}

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

int main()
{
	unsigned long a, b, n;
	unsigned long ans;
	cin >> a >> b >> n;
	if (b-2 >= n) {
		ans = (a*n / b) - a * (n / b);
	}
	else {
		ans = (a*(b - 1) / b) - a * ((b - 1) / b);
	}
	cout << ans << endl;
}


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

int main(){
	int N,X;
	cin>>N>>X;
	vector<int> L (N);
	for (int i =0;i<N;i++){
		cin>>L.at(i);
	}

	int D = 0;
	int num =1;
	for (int i =0;i<N;i++){
		if (D<=X){
			D+=L.at(num-1);
			num+=1;
		}
		else{
			break;
		}
	}

	if (D<=X){
		num+=1;
	}
	cout<<num-1<<endl;
}


Measured memory_bytes: 256
X,K,D = map(int, input().split())
x = 0
if X == 0:
  if K%2 == 0:
    print (0)
  else:
    print (abs(D))
  x =1
elif X < 0:
  if abs(X) >= K*D:
    print (abs(X+K*D))
  else:
    K = K-(-1*X//D)
    X = X+(-1*X//D)*D
    if K%2 == 0:
      print (abs(X))
    else:
      print (abs(X+D))
else:
  if X >= K*D:
    print (X-K*D)
  else:
    K = K-(X//D)
    X = X-(X//D)*D
    if K%2 == 0:
      print (abs(X))
    else:
      print (abs(X-D))


Measured memory_bytes: 9200
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < n;i++)
#define ll long long
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s,t;cin>>s>>t;
  string p=t+s;
  cout<<p;
}

Measured memory_bytes: 256
use std::io::{BufRead, StdinLock};
use std::str::FromStr;

fn read<T: FromStr>(stdin_lock: &mut StdinLock, buf: &mut Vec<u8>, delimiter: u8) -> T {
    buf.clear();
    let l = stdin_lock.read_until(delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let a = read(&mut stdin_lock, &mut buf, b' ');
    let b = read(&mut stdin_lock, &mut buf, b'\n');
    println!("{}", solve(a, b));
}

fn solve(a: u8, b: u8) -> u8 {
    if a == b {
        a + b
    } else if a > b {
        a + a - 1
    } else {
        b + b - 1
    }
}

#[test]
fn example1() {
    assert_eq!(9, solve(5, 3))
}

#[test]
fn example2() {
    assert_eq!(7, solve(3, 4))
}

#[test]
fn example3() {
    assert_eq!(12, solve(6, 6))
}


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

int main(){
    string w;
    string t;
    cin >> w;
    int count = 0;
    for(;;){
        cin >> t;
        if(t == "END_OF_TEXT") break;
        transform(t.begin(), t.end(), t.begin(), ::tolower);
        if(w == t) count++;
    }
    
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3164
#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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/






int A, B, T;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> A >> B >> T;

	int ans = T / A * B;
	cout << ans << endl;
}


Measured memory_bytes: 384
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        x: usize,
    }

    if x==0 {
        println!("1");
    } else {
        println!("0");
    }

}


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

typedef long long int ll;

//const double PI=3.14159265358979323846;

int main () {
    int s, w; cin >> s >> w;
    if (w >= s) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3104
MOD = 10**9+7
a = 10**6
n, k = map(int, input().split())
nums = [i for i in range(n+1)]
min_n = sum(nums[:k])
max_n = sum(nums[-k:])
res = (max_n-min_n)+1
res %= MOD
i = 0
while k+i <= n:
    min_n += nums[k+i]
    max_n += nums[-(k+i+1)]
    diff = max_n - min_n
    res += diff+1
    res %= MOD
    i += 1

print(res)


Measured memory_bytes: 18164
#include <stdio.h>

int main(void) {
	int n,i,j;
	int a[20],v[20];
	
	scanf("%d",&n);
	for(i = 0;i < n;i++){
		scanf("%d %d",&a[i],&v[i]);
	}
	
	for(i = 0;i < n-1;i++){
		for(j = i;j < n;j++){
			if(v[i] < v[j]){
				v[i] ^= v[j] ^= v[i] ^= v[j];
				a[i] ^= a[j] ^= a[i] ^= a[j];
			}else if(v[i] == v[j]){
				if(a[i] > a[j]){
					a[i] ^= a[j] ^= a[i] ^= a[j];
				}
			}
		}
	}
	
	printf("%d %d\n",a[0],v[0]);
	
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>

#include <set>
#include <unordered_map>
#include <stack>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
using ll = long long;
template<class T>bool chmaxj(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; }
void YesNo(bool y) { cout << (y ? "Yes" : "No") << endl; } //true==yes


#define INF 21474836

//////////////////////////////////////////////////////////////

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

int main() {

	string S;
	int N;
	cin >> N;
	cin >> S;

	vector<int> R_n(N, 0);
	vector<int> B_n(N, 0);
	vector<int> G_n(N, 0);

	rep(i, N) {

		if (S[i] == 'R')R_n[i]++;
		if (S[i] == 'B')B_n[i]++;
		if (S[i] == 'G')G_n[i]++;

		if (i < N - 1) {
			R_n[i + 1] = R_n[i];
			B_n[i + 1] = B_n[i];
			G_n[i + 1] = G_n[i];
		}
	}

	long long ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {

			bool check = (j + j - i < N);

			if (S[i] == 'R') {
				if (S[j] == 'B') {
					ans += G_n[N-1] - G_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'G')ans--;
				}
				if (S[j] == 'G') {
					ans += B_n[N - 1] - B_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'B')ans--;
				}
			}
			if (S[i] == 'B') {
				if (S[j] == 'R') {
					ans += G_n[N - 1] - G_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'G')ans--;
				}
				if (S[j] == 'G') {
					ans += R_n[N - 1] - R_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'R')ans--;
				}
			}
			if (S[i] == 'G') {
				if (S[j] == 'R') {
					ans += B_n[N - 1] - B_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'B')ans--;
				}
				if (S[j] == 'B') {
					ans += R_n[N - 1] - R_n[j];
					if (!check)continue;
					if (S[j + j - i] == 'R')ans--;
				}
			}
		}
	}

	cout << ans << endl;



}

/*
int main() {


	string S;
	cin >> S;
	if (S[0] == '7' || S[1] == '7' || S[2] == '7')cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}

*/

Measured memory_bytes: 3660
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}

void solve()
{
	int x;
	cin >> x;
	if(x == 7 || x == 5 || x == 3) cout << "YES";
	else cout << "NO";
}


 
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PI 3.141592653589793238462
typedef long long ll;
typedef long double db;
ll d[10000007];
int main(){
    ll n,ans=0;cin>>n;
    for(ll i=1;i<=n;i++){
        d[i]=2;
    }d[1]=1;
    for(ll i=2;i<=n;i++){
        for(ll j=i+i;j<=n;j+=i){
            d[j]++;
        }
    }
    for(ll i=1;i<=n;i++){
        ans+=d[i]*i;
    }
    cout<<ans<<endl;
}
    
     

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

int main() {
    int a,b;
    int n,m;
    cin >> n>>m;
    vector<int> c(n,0);
    rep(i,m){
        cin >>a>>b;
        c[a-1]++;
        c[b-1]++;
    }
    rep(i,n){
        cout<<c[i]<<endl;
    }
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

int H, W;
string a[10];

int main(int argc, char const *argv[]) {
	cin >> H >> W;
	for (int i = 0; i < H; i++) cin >> a[i];
	char cur = a[0][0];
	int x = 0, y = 0;
	bool flag = false;
	while (true) {
		bool no = false;
		if (x == H-1 && y == W-1) {
			flag = true;
			break;
		}
		if (x+1 < H && a[x+1][y] == '#') {
			a[x][y] = '.';
			for (int i = 0; i < W; i++) {
				if (a[x][i] == '#') {
					no = true;
					break;
				}
			}
			if (no) break;
			x++;
		}
		else if (y+1 < W && a[x][y+1] == '#') {
			a[x][y] = '.';
			for (int i = 0; i < H; i++) {
				if (a[i][y] == '#') {
					no = true;
					break;
				}
			}
			if (no) break;
			y++;
		}
		else break;
	}

	if (flag) cout << "Possible" << endl;
	else cout << "Impossible" << endl;
	return 0;
}

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

ll factor(ll n){
    ll mod = 5;
    ll ans = 0;
    while(n > 0){
        ans += n / mod;
         n /= 5;
   }      
    return ans;
}

int main(){
    ll n;
    cin >> n;
    if(n<10 ||  n%2==1){
      cout << 0 << endl;
       return 0;
   }
    if(n%2==0) cout << factor(n/2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, ma = 0;
    ll H;
    ll ans = LLONG_MAX;
    cin >> N >> H;
    vi a(N), b(N);
    rep(i, N) {
        cin >> a[i] >> b[i];
        smax(ma, a[i]);
    }

    sort(b.rbegin(), b.rend());
    ll sm = 0;
    rep(i, sz(b) + 1) {
        ll val = (max<ll>((H - sm), 0) + ma - 1) / ma + i;
        smin(ans, val);
        if (i == sz(b))break;
        sm += b[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=2e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;
char a[105][105];
int memo[105][105][205];
int n,m;
int solve(int x,int y,int curr){
	if((x==n-1) && (y==m-1)){
		return (curr || (a[x][y]=='#'));
	}
	if(x>=n || y>=m){
		return 1e9;
	}
	int &ret = memo[x][y][curr];
	if(~ret)return ret;
	ret = 0;
	if(a[x][y]=='.'){
		ret = solve(x+1,y,0) + (curr!=0);
		ret = min(ret,solve(x,y+1,0)+(curr!=0));
	}
	else{
		ret = min(solve(x+1,y,curr+1) , solve(x,y+1,curr+1));
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();	
 	
 	scanf("%d %d",&n,&m);
 	for(int i=0;i<n;i++)scanf("%s",&a[i]);
 	memset(memo,-1,sizeof(memo));
 	printf("%d\n",solve(0,0,0) );
}		


Measured memory_bytes: 9216
n, k = map(int, input().split())
MOD = 10 ** 9 + 7

cnt = [0] * (k + 1)
for num in range(1, k + 1):
    cnt[num] = pow((k // num), n, MOD)

for num in range(1, k + 1)[::-1]:
    for i in range(2, k // num + 1):
        cnt[num] -= cnt[num * i]
        cnt[num] % MOD

ans = 0
for num in range(1, k + 1):
    ans += cnt[num] * num
    ans %= MOD
print(ans)


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

#define FOR(i, a, b)  for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << "\n"
#define _ << " _ " <<
#define ll long long
#define pil pair <int, ll>
#define pii pair <int, int>

using namespace std;

int out[100010][5];
int tb[100100][5];
int n, num;


void ispis() {
  REP(sol, 4) {
    REP(i, num) {
      if (out[i][sol] == 0) cout << "S";
      else                  cout << "W";
    }
    cout << endl;
  }
  cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);

  cin >> n;
  string s;
  cin >> s;
  out[0][0] = 0;
  out[0][1] = 0;
  out[0][2] = 1;
  out[0][3] = 1;

  out[1][0] = 0;
  out[1][1] = 1;
  out[1][2] = 0;
  out[1][3] = 1;

  if (s[0] == 'o') {
    tb[n - 1][0] = 0;
    tb[n - 1][1] = 1;
    tb[n - 1][2] = 1;
    tb[n - 1][3] = 0;
  } else {
    tb[n - 1][0] = 1;
    tb[n - 1][1] = 0;
    tb[n - 1][2] = 0;
    tb[n - 1][3] = 1;
  }

  num = 2;
  FOR(i, 1, n - 1) {
    num++;
    if (s[i] == 'o') {
      REP(j, 4) {
        if (out[i][j] == 0) {
          out[i + 1][j] = out[i - 1][j];
        } else {
          out[i + 1][j] = !out[i - 1][j];
          //cout << out[i - 1][j] << endl;
        }
      }
    } else {
      REP(j, 4) {
        if (out[i][j] == 0) {
          out[i + 1][j] = !out[i - 1][j];
        } else {
          out[i + 1][j] = out[i - 1][j];
        }
      }
    }
    //ispis();
  }
  int sol = -1;

  int i = n - 1;
  if (s[i] == 'o') {
    REP(j, 4) {
      if (out[i][j] == 0) {
        if (out[0][j] == out[i - 1][j] && out[i][j] == tb[i][j]) {
          sol = j;
          break;
        }
      } else {
        if (out[0][j] == !out[i - 1][j] && out[i][j] == tb[i][j]) {
          sol = j;
          break;
        }
      }
    }
  } else {
    REP(j, 4) {
      if (out[i][j] == 0) {
        if (out[0][j] == !out[i - 1][j] && out[i][j] == tb[i][j]) {
          sol = j;
          break;
        }
      } else {
        if (out[0][j] == out[i - 1][j] && out[i][j] == tb[i][j]) {
          sol = j;
          break;
        }
      }
    }
  }
  if (sol == -1) {
    cout << "-1\n";
    return 0;
  }
  REP(i, n) {
    if (out[i][sol] == 0) cout << "S";
     else                 cout << "W";
  }
  cout << endl;
  //ispis();


  return 0;
}


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

using ll = long long;
const ll mod = 1e9+7;

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<ll> a(n);
	for(int i=0;i<n;i++) {
		scanf("%lld", &a[i]);
	}
	sort(a.begin(), a.end(), [](ll a, ll b) {return abs(a) > abs(b);});
	ll ans = 1;
	for(int i=0;i<k;i++) {
		ans = ans * a[i] % mod;
	}
	if(ans > 0) {
		printf("%lld\n", (ans+mod)%mod);
	} else {
		int c=k-1;
		for(;c>=0;c--) {
			if(a[c] < 0) break;
		}
		bool chk = false;
		int d;
		if(c >= 0) {
			for(int i=k;i<n;i++) {
				if(a[i] > 0) {
					d = i;
					chk = true;
					break;
				}
			}
		}	

		int e=k-1;
		bool chk2 = false;
		for(;e>=0;e--) {
			if(a[e] > 0) {
				break;
			}
		}
		int f;
		if(e >= 0) {
	
			for(int i=k;i<n;i++) {
				if(a[i] < 0) {
					f = i;
					chk2 = true;
					break;
				}
			}
		}
		// printf("%d %d\n", chk, chk2);
		if(chk || chk2) {
			int x;
			ans = 1;
			if(chk && chk2) {
				if(abs(a[d])*abs(a[e]) > abs(a[f])*abs(a[c])) {
					ans = a[d];
					x = c;
				} else {
					ans = a[f];
					x = e;
				}
			} else if (chk) {
				ans = a[d];
				x=c;
			} else if (chk2) {
				ans = a[f];
				x=e;
			}
			for(int i=0;i<k;i++) {
				if(i != x) ans = ans * a[i] % mod;
			}
			// printf("=====\n");
		} else {
			ans = 1;
			// printf("%d %d\n", n-1, n-k);
			for(int i=n-1;i>=n-k;i--) {
				ans = ans * a[i] % mod;
				// printf("%lld\n", a[i]);
			}
			// printf("==========\n");
		}
		printf("%lld\n", (ans+mod)%mod);
	}
	// vector<ll> p, m;
	// for(int i=n-1;i>=0;i--) {
	// 	if(a[i]>=0) {
	// 		p.push_back(a[i]);
	// 	}
	// 	else {
	// 		m.push_back(a[i]);
	// 	}
	// }
	// sort(p.begin(), p.end(), [](ll a, ll b) {return a>b;});
	// sort(m.begin(), m.end(), [](ll a, ll b) {return a<b;});
	// int i=0, j=0;
	// ll ans = 1;
	// while(k>=2 && i+1 < p.size() && j+1 < m.size()) {
	// 	if(p[i]*p[i+1] > m[j]*m[j+1]) {
	// 		ans = ((ans * p[i]) % mod)*p[i+1] % mod;
	// 		i+=2;
	// 	} else {
	// 		ans = ((ans * m[j]) % mod)*m[j+1] % mod;
	// 		j+=2;
	// 	}
	// 	k-=2;
	// }
	// while(k>=2 && j+1 < m.size()) {

	// }
}

Measured memory_bytes: 4816
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

mat mul(mat &A, mat &B){
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++){
        for (int k = 0; k < B.size(); k++){
            for (int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

mat pow(mat A, ll n){
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

const double inf = 1e10;

struct D {
    vector<double> l, r;
    D():l(3, inf), r(3, -inf) {}
    void add(double x, int v){
        ++v;
        mins(l[v], x);
        maxs(r[v], x);
    }
    double get(double t){
        double nl = inf, nr = -inf;
        rep(i, 3){
            mins(nl, l[i] + i * t);
            maxs(nr, r[i] + i * t);
        }
        return nr - nl;
    }

    vector<double> events(){
        vector<double> ts;
        rep(i, 3)rep(j, i){
            {
                double t = (l[j] - l[i]) / (i - j);
                if (t > 0) ts.push_back(t);
            }
            {
                double t = (r[j] - r[i]) / (i - j);
                if (t > 0) ts.push_back(t);
            }
        }
        return ts;
    }
};

int main(){
    int n;
    cin >> n;
    D xd, yd;
    rep(i, n){
        int x, y;
        char d;
        cin >> x >> y >> d;
        if(d == 'L') xd.add(x, -1), yd.add(y, 0);
        if(d == 'R') xd.add(x, 1), yd.add(y, 0);
        if(d == 'U') xd.add(x, 0), yd.add(y, 1);
        if(d == 'D') xd.add(x, 0), yd.add(y, -1);
    }
    vector<double> ts;
    ts.push_back(0);
    ts.push_back(inf);
    {
        auto nts = xd.events();
        ts.insert(ts.end(), nts.begin(), nts.end());
    }
    {
        auto nts = yd.events();
        ts.insert(ts.end(), nts.begin(), nts.end());
    }
    sort(ts.begin(), ts.end());
    double ans = 1e18;
    for (double t : ts){
        double now = xd.get(t) * yd.get(t);
        mins(ans, now);
    }
    printf("%.10lf\n", ans);
    
}

Measured memory_bytes: 3792
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include<queue>

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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int gcd(int a, int b){return b ? gcd(b, a%b) : a;}
int lcm(int a, int b){return a*b / gcd(a, b);}

ll nC2(ll n){
    return n*(n-1)/2;
}

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

    ll total = 0;
    for(int i = 0; i <= n; i++){
        total += nC2(cnt[i]);
    }
    for(int i = 0; i < n; i++){
        ll ans = total;
        ans -= nC2(cnt[a[i]]);
        ans += nC2(cnt[a[i]]-1);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 5048
#include <stdio.h>

int main(void)
{;
	char x = 'a',title;
//空白まで読み捨て
	while(x != ' ')
	{
		scanf("%c",&x);
	}
//略称の文字を読み込む
	scanf("%c",&title);
//結果を出力
	printf("A%cC\n",title);
	return 0;
}

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

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

    string s;
    cin >> s;
    int n = (s.size()+1)/2;
    string ans = "";
    rep(i, n){
        ans += s[i*2];
    }
    cout << ans << endl;
}

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

int main(){
    int w,h,x,y;
    cin>>w>>h>>x>>y;
    double ans=0.5*w*h;
    int f = x==(w-x)&&y==(h-y) ? 1 : 0;
    cout<<ans<<' '<<f<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;

	if (N >= K) {
		cout << K * X + (N - K) * Y << endl;
	}
	else {
		cout << N * X << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int a, b, d, r;
    double f;

    scanf("%d %d", &a, &b);

    d = a / b;
    r = a % b;
    f = 1. * a / b;

    printf("%d %d %.5lf", d, r, f);

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s, ans;
  cin >> s;
  rep(i, 1, s.size() +1) {
    if(i%2 == 1)
      ans += s.at(i-1);
  }
  
  cout << ans << "\n";

}


Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
int main(){
	scanf("%d",&n);
	int p=1;
	while (p<n)p<<=1;
	if (p==n){
		puts("No");
		return 0;
	}
	puts("Yes");
	p>>=1;
	if (n%4==3){
		for (int i=2;i<=2*n;i++)printf("%d %d\n",i-1,i);
		return 0;
	}
	if (n%4==1){
		for (int i=3;i<=n;i++)printf("%d %d\n",i-1,i);
		printf("%d %d\n",n,n+2);
		for (int i=3;i<=n;i++)printf("%d %d\n",i-1+n,i+n);
		printf("%d %d\n",1,2);
		printf("%d %d\n",3,n+1);
	}
	if (n%4==0){
		for (int i=1;i<n;i++)a[i]=i;
		swap(a[p],a[n-p-1]);
		for (int i=2;i<n;i++)printf("%d %d\n",a[i-1],a[i]);
		printf("%d %d\n",a[n-1],a[1]+n);
		for (int i=2;i<n;i++)printf("%d %d\n",a[i-1]+n,a[i]+n);
		printf("%d %d\n",n,p);
		printf("%d %d\n",2*n,n-p);
	}
	if (n%4==2){
		for (int i=2;i<=n-1;i++)a[i]=i;
		swap(a[p-1],a[n^p]);
		if ((n^p)==2&&n!=6)swap(a[p-2],a[3]);
		for (int i=2;i<=n-2;i++)printf("%d %d\n",a[i],a[i+1]);
		printf("%d %d\n",a[n-1],n+a[2]);
		for (int i=2;i<=n-2;i++)printf("%d %d\n",n+a[i],n+a[i+1]);
		printf("%d %d\n",n,p);
		printf("%d %d\n",2*n,n^p);
		printf("%d %d\n",1,2);
		printf("%d %d\n",1+n,3);		
	}
	return 0;
}

Measured memory_bytes: 3200
#include <stdio.h>
int main(void){
    int i,a,z;
    char s[2000001];
    scanf("%s",s);
    for(i=0;s[i]!='A';i++)
        ;
    for(a=i;s[i];i++){
        if(s[i]=='Z'){
            z=i;
        }
    }
    printf("%d\n",z-a+1);
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>

int main(){
  int N,A[100],i,j,temp,count=0;

  scanf("%d",&N);
  if (N<1||N>100){
    printf("N ha 1-100 death.\n");
    exit(1);
  }
  for (i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  for (i=1;i<=N;i++){
    for (j=N-1;j>=i;j--){
      if (A[j] < A[j-1]){
	temp=A[j];
	A[j]=A[j-1];
	A[j-1]=temp;
	count++;
      }
    }
  }

  for (i=0;i<N;i++){
    printf("%d",A[i]);
    if (i<N-1){
      printf(" ");
    } else {
      printf("\n");
    }
  }
  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 604
#
# abc176 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 = """123456789"""
        output = """Yes"""
        self.assertIO(input, output)

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

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


def resolve():
    N = input()

    S = 0
    for i in range(len(N)):
        S += int(N[i])
    if S % 9 == 0:
        print("Yes")
    else:
        print("No")


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


Measured memory_bytes: 16356