akhauriyash/Code-Regression huggingface dataset:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
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_MAX	2,147,483,647 = 2*1.0e9

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

  int ans = 0;
  for(int j = 1; j <= N; j+=2){
    int cnt = 0;
    for(int i = 1 ; i <= j; i++){
      if(j %i == 0) cnt++;
    }
    if(cnt == 8) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF (1<<28)
#define N (1<<17)

int h[100010];
int main(){
	int n; cin >> n;
	
	for(int i = 0 ; i < n ; i++){
		int a,b;
		cin >> a >> b;
		a--,b--;
		h[a]++;
		h[b+1]--;
	}
	int ans = 0 , cur = 0;
	for(int i = 0 ; i <= 100001 ; i++){
		cur += h[i];
		//if(cur) cout << i << " " << cur << endl;
		if(cur >= i) ans = max(ans,i);
	}
	cout << ans << endl;
	
}

Measured memory_bytes: 1212
from __future__ import print_function

import sys
input = sys.stdin.readline


def main():
    a, b, c = map(int, input().strip().split())
    for k in range(1, b + 1):
        if (k * a) % b == c:
            print("YES")
            return
    print("NO")
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
from collections import deque
n = int(input())
path = {u:[] for u in range(1, n+1)}
for i in range(1, n):
    u, v, w = map(int, input().split())
    path[u].append((v,w))
    path[v].append((u,w))

queue = deque()
queue.append(1) # (parent , child, distance)
distance_li = [-1] * (n+1)
distance_li[1] = 0

# for i in range(1,n):
#     print(i, path[i])

while len(queue) > 0:
    u = queue.popleft()
    for v,w in path[u]:
        if distance_li[v] != -1:
            continue
        distance_li[v] = (distance_li[u] + w) % 2
        queue.append(v)
for i in range(1,n+1):
    print(distance_li[i])

Measured memory_bytes: 47584
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <stack>
#include <vector>

#define FOR(i,k,n) for(int (i) = (k); (i) < (n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x,y) cerr << #x << ": " << x << ", " << #y << ": " << y << endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<i_i, int> p_i;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
template<class T> using vv=vector< vector<T> >;
typedef deque<int> di;
typedef deque< deque<int> > ddi;


int main() {
    char s[20001] = {};
    scanf("%s",s);
    int n = strlen(s); 
    stack<int> T;
    stack<i_i> S1; 
    stack<int> S2;
    int sum = 0;
    rep(i,n) {
        if(s[i] == '\\') {
            T.push(i);
        } else if(s[i] == '/' && !T.empty()) {
            int t = T.top();
            T.pop();
            int s = (i-t-1) * 1 + 1;  
            S1.push(make_pair(t,s));  
        }
    }
    while(!S1.empty()) {
        i_i a = S1.top();
        S1.pop();     
        while(!S1.empty() && S1.top().first > a.first) {
            i_i b = S1.top();
            a.second += b.second;
            S1.pop();
        }
        sum += a.second;
        S2.push(a.second);
    }
    cout << sum << endl;
    cout << S2.size();
    while(!S2.empty()) {
        cout << " " << S2.top();
        S2.pop();
    } 
    cout << endl;
	return 0;
}

Measured memory_bytes: 3276
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  string s,t;
  cin >> s >> t;
  int n = s.size();
  int m = t.size();

  char S[n];
  char T[m];

  for(int i=0;i<n;i++) S[i] = s[i];
  for(int i=0;i<m;i++) T[i] = t[i];

  sort(S,S+n);
  sort(T,T+m);
  reverse(T,T+m);

  for(int i=0;i<n;i++) s[i] = S[i];
  for(int i=0;i<m;i++) t[i] = T[i];

  if(s<t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

int in(){int x;scanf("%d",&x);return x;}

signed main(){

  bitset<32> b(in());
  cout<< b <<endl;
  cout<< ~b <<endl;
  cout<< (b<<1) <<endl;
  cout<< (b>>1) <<endl;

}


Measured memory_bytes: 3292
h, w, k = map(int,input().split())
cak = [input() for i in range(h)]
nos = []
ans = [[-1 for i in range(w)] for j in range(h)]

for i,l in enumerate(cak):
    if not "#" in l:
        nos.append(i)

ni = 1
nh = -1
sf = True
for i,l in enumerate(cak):
    if sf and i in nos:
        continue
    elif i in nos:
        ans[i] = ans[i-1]
    else:
        lft = l.find("#")
        for j in range(lft+1):
            ans[i][j] = ni
        for j in range(lft+1,w):
            if l[j] == "#":
                ni += 1
            ans[i][j] = ni
        if sf:
            for j in range(i):
                ans[j] = ans[i]
            sf = False
        ni += 1

for l in ans:
    print(" ".join(map(str,l)))


Measured memory_bytes: 7284
a = input()
b = input()
c = input()


turn = 'a'

A = B = C = 0

while 1:

    if turn == 'a':
        if len(a) == A:
            print('A')
            break
        turn = a[A]
        A+=1

    elif turn == 'b':
        if len(b) == B:
            print('B')
            break
        turn = b[B]
        B+=1
    else:
        if len(c) == C:
            print('C')
            break
        turn = c[C]
        C+=1


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define sd(val) scanf("%d",&val)
#define ss(val) scanf("%s",&val)
#define sl(val) scanf("%lld",&val)
#define all(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
#define FF first
#define SS second
#define ll long long int
#define MOD 1000000007
#define clr(val) memset(val,0,sizeof(val))
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


int main() 
{
	/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin); 
	freopen("output.txt", "w", stdout);
	#endif*/
	int a,b,c;
	cin>>a>>b;
	c=a*b;
	cout<<c;


return 0;
   
}

Measured memory_bytes: 3564
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] s = str.split(" ");
		int w = Integer.parseInt(s[0]);
		int h = Integer.parseInt(s[1]);
		int x = Integer.parseInt(s[2]);
		int y = Integer.parseInt(s[3]);
		int r = Integer.parseInt(s[4]);

		if(((x + r) <= w) && (0 <= (x - r)) && ((y + r) <= h)&&(0 <= (y - r))){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

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

int main(){
  int a,b,c,d;
  int q=0;

  cin >> a >> b;
  c= min(a*125/10, b*10); d= max(a*125/10, b*10);

  int i=c;
  while(i<d+10){
    if(i*8/100==a && i*10/100==b){
      q = i;
      break;
    }
    i++;
  }
  if(q==0){cout << "-1" << endl;}else{
  cout << q << endl;}
}

Measured memory_bytes: 256
import sys
from collections import deque

input = sys.stdin.readline
N,M = [int(x) for x in input().rstrip().split()]

to = [list() for _ in range(N)]

for i in range(M):
    a,b = [int(x)-1 for x in input().rstrip().split()]
    to[a].append(b)
    to[b].append(a)

sign = [0]*N
dist = [N]*N
dist[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()

    for x in to[v]:
        if dist[x] > dist[v]+1:
            dist[x] = dist[v]+1
            sign[x] = v+1
            q.append(x)
    
print('Yes')
for i in sign[1:]:
    print(i)




Measured memory_bytes: 38656
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		String[]s = new String[H + 2];
		for(int i = 0; i < H + 2; i++) {
			s[i] = "";
		}
		for(int i = 0; i < W + 2; i++) {
			s[0] += "#";
			s[H + 1] += "#";
		}
		for(int i = 0; i < H; i++) {
			String t = sc.next();
			t = "#" + t + "#";
			s[i + 1] = t;
		}
		sc.close();
		for(String k : s) {
			System.out.println(k);
		}
	}
}

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

using namespace std;

const int N = 3100;

double p[N], dp[N][N];

int main() {
	int n;
	double ans = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> p[i];
	dp[1][0] = double(1) - p[1];
	dp[1][1] = p[1];
	for (int i = 2; i <= n; ++i) {
		dp[i][0] = dp[i - 1][0] * (double(1) - p[i]);
		for (int j = 1; j <= i; ++j)
			dp[i][j] = dp[i - 1][j] * (double(1) - p[i]) + dp[i - 1][j - 1] * p[i];
	}
	for (int i = n / 2 + 1; i <= n; ++i)
		ans += dp[n][i];
	cout << setprecision(9) << ans << '\n';
}


Measured memory_bytes: 72448
while 1:
  try:
    a, b = map(int, input().split())
    cross = [[0 for i in range(a + 1)] for j in range(b + 1)]
    n = int(input())
    for i in range(n):
      x_i, y_i = map(int, input().split())
      cross[y_i][x_i] = 1
    for x in range(a + 1):
      for y in range(b + 1):
        if x != 0 and y != 0:
          if cross[y][x] == 1:
            cross[y][x] = 0
          elif x == 1 and y == 1:
            cross[1][1] = 1
          else:
            cross[y][x] = cross[y - 1][x] + cross[y][x - 1]
    print(cross[b][a])
  except:
    break


Measured memory_bytes: 5600
#include <bits/stdc++.h>
#include <string>
using namespace std;
typedef long long ll;

ll mod=998244353;
double PI=3.14159265358979323846;
int main(){
    double a,b,x;
    cin>>a>>b>>x;
    
    x/=a;
    
    double deg=atan(b/a);
    if(a*b/2>x){
        double aa=x*2/b;
        deg=atan(b/aa);
    }else{
        double bb=(a*b-x)*2/a;
        deg=atan(bb/a);
    }
    
    cout<<fixed<<setprecision(20)<<deg*180.0/PI<<endl;
}

Measured memory_bytes: 4072
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextFloat() float64 {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return float64(i)
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	var list []float64
	for i := 0; i < n; i++ {
		list = append(list, nextFloat())
	}
	sort.Float64s(list)
	var ans float64
	for i, v := range list {
		if i == 0 {
			ans = v
		} else {
			ans = (ans + v) / 2.0
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
def dfs(arr: list, index: int, length: int, S: str) -> int :

    if index == length-1:
        return cal(arr, S)

    index += 1
    return dfs(arr+[index], index, length, S) + dfs(arr, index, length, S)


def cal(arr: list, S: str) -> int :
    s = 0
    tmp = arr[0]

    for a in arr[1:]:
        s += int(S[tmp:a])
        tmp = a
    s += int(S[arr[-1]:])
    
    #print(s)

    return s

S = input()

arr = [0]
ans = dfs(arr, 0, len(S), S)

print(ans)





Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <queue>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

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

    vector<int> g[N];
    map<P ,int> m;
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
        if(a > b) swap(a, b);
        m[P(a, b)] = i;
    }
    
    int num = 0;
    for(int i=0; i<N; i++){
        num = max(num, (int)g[i].size());
    }

    int c[N-1];
    fill(c, c+N-1, -1);
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        bool used[num];
        fill(used, used+num, false);
        for(int i=0; i<g[now].size(); i++){
            int a = now;
            int b = g[now][i];
            if(a > b) swap(a, b);
            int en = m[P(a, b)];
            if(c[en] != -1) used[c[en]] = true;
        }
        int color = 0;
        for(int i=0; i<g[now].size(); i++){
            while(used[color]){
                color++;
            }
            int a = now;
            int next = g[now][i];
            int b = next;
            if(a > b) swap(a, b);
            int en = m[P(a, b)];
            if(c[en] == -1){
                c[en] = color;
                used[color] = true;
                q.push(next);
            }
        }
    }

    cout << num << endl;
    for(int i=0; i<N-1; i++){
        cout << c[i]+1 << endl;
    }

    return 0;
}


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

int main(){
    int n, m, p, x;
    int s, winner;
    int result;
    cin >> n >> m >> p;
    while(n || m || p){
        s = 0;
        for(int i=0;i<n;++i){
            cin >> x;
            if(i+1==m) winner = x;
            s += x;
        }
        if(winner){
            result = (s * (100-p)) / winner;
        }else{
            result = 0;
        }
        cout << result << endl;
        cin >> n >> m >> p;
    }
}

Measured memory_bytes: 1160
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

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

def readInts():
  return list(map(int,input().split()))
def main():
    s,w = readInts()
    if w >= s:
        print('unsafe')
    else:
        print('safe')
if __name__ == '__main__':
  main()


Measured memory_bytes: 10852
//Sameer's Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define MOD 1000000007
#define pb push_back
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
#endif
    string s;
    cin >> s;
    //cout << s << endl;
    ll ans = 0;
    for (auto i : s)
    {
        //cout << (i) - '0' << endl;
        ans = ans + int(i - '0') % 9;
        ans = ans % 9;
    }
    //cout << ans << endl;
    ans = ans % 9;
    if (ans % 9 == 0)
    {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3784
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

i64 dp[1010][9];
int cnt[1010];

int main()
{
	for (int i = 0; i <= 8; ++i) dp[0][i] = 0;
	dp[0][0] = 1;
	for (int i = 1; i <= 500; ++i) {
		dp[i][0] = 1;
		for (int j = 1; j <= 7; ++j) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
	}
	i64 L;
	scanf("%lld", &L);
	for (int i = 500; i >= 7; --i) {
		int n = (int)(L / dp[i][7]);
		cnt[i] = n;
		L %= dp[i][7];
	}
	for (int i = 0; i <= 500; ++i) {
		printf("AVITSEF");
		for (int j = 0; j < cnt[i + 1]; ++j) printf("L");
	}
	puts("");

	return 0;
}


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

//文字列も数値として扱える話
int main()
{
    int N, L;
    cin >> N >> L;

    vector<string> S(N);
    for (size_t i = 0; i < N; i++)
    {
        cin >> S[i];
    }
    sort(S.begin(), S.end());
    for (auto &&i : S)
    {
        cout << i;
    }
    cout << endl;
}


Measured memory_bytes: 3636
#include <cstdio>
typedef long long ll;

#define N 200050
int a[N];
ll go[N],tc[N],mk[N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		
	ll ans=0;
	for(int i=2;i<=n;i++)
	{
		if(a[i]<a[i-1]) a[i]+=m;
		ans+=a[i]-a[i-1];
		if(a[i]>=a[i-1]+2)
		{
			go[a[i-1]+2]++;
			go[a[i]+1]--;
			tc[a[i]+1]-=a[i]-a[i-1]-1;
		}
		if(a[i]>m) a[i]-=m;
	}
	
	ll res=0;
	for(int i=1;i<=m+m;i++)
	{
		go[i]+=go[i-1];
		res+=go[i]+tc[i];
		mk[i]=res;
	}
	
	ll maxgo=0;
	for(int i=1;i<=m;i++)
		if(mk[i]+mk[i+m]>maxgo)
			maxgo=mk[i]+mk[i+m];
	printf("%lld\n",ans-maxgo);
}

Measured memory_bytes: 4736
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int main()
{
	scanf("%d",&n);
	m=1;
	while(m-1<=n)m<<=1;
	m>>=1;
	m--;
	if(n==m+1||n==1)
	{
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	for(int i=1;i<m;i++)
	  printf("%d %d\n%d %d\n",i,i+1,n+i,n+i+1);
	printf("%d %d\n",m,n+1);
	if(n==m)return 0;
	printf("1 %d\n%d %d\n1 %d\n%d %d\n",m+1,m+1,m+2,n+m+2,n+m+2,n+m+1);
	for(int i=m+3;i<=n;i++)
	  printf("%d %d\n%d %d\n",i+n-1,i,i-m-1,i+n);
	return 0;
}

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

int T;
ll n;

map<ll, ll> dis;


int A[3] = {2, 3, 5};
ll cost[4];

void solve(){
    priority_queue<pl, vector<pl>, greater<pl> > pq;
    dis.clear();
    dis[n] = 0;
    pq.push(mp(0, n)); 
    while(!pq.empty()){
        pl p = pq.top(); pq.pop();
        ll d = p.fi;
        ll id = p.se;
        if(id == 1)
            break;
        for(int i = 0;i < 3;i++){
            ll to = id / A[i];
            ll d1 = dis[id] + cost[i] + (id - A[i] * to) * cost[3];
            if(!dis.count(to) or (dis[to] > d1)){
                dis[to] = d1;
                pq.push(mp(dis[to], to));
            }
            to = to + 1;
            d1 = dis[id] + cost[i] + (A[i] * to - id) * cost[3];
            if(!dis.count(to) or (dis[to] > d1)){
                dis[to] = d1;
                pq.push(mp(dis[to], to));
            }
        }
    }
    ll ans = 1e18;
    for(auto v : dis){
        ll p = v.fi;
        if((ans - v.se) / cost[3] >= p){
            ans = min(ans, p * cost[3] + v.se);
        }
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 0;i < 4;i++){
            cin >> cost[i];
        }
        solve();
    }
    return 0;
}


Measured memory_bytes: 4640
import java.util.*;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int a,b=0,sum=0,max=0;
		a = sc.nextInt();
		
		int[] ary = new int[a];
		
		for(int i=0;i<a;i++)
		{
			ary[i] = sc.nextInt();
			if(ary[i]>max)
			{
				max = ary[i];
				b = i;
			}
		}
		
		for(int i=0;i<a;i++)
		{
			if(i==b)
				sum+=ary[i]/2;
			else
				sum+=ary[i];
		}
	
		
		
		
		System.out.println(sum);
	}
}

Measured memory_bytes: 23252
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] dice = new int[6];
        int[] dice2=new int[4];
		String W;

		for (int i = 0; i < dice.length; i++) {
			dice[i] = sc.nextInt();
		}
		int q=sc.nextInt();
        for(int i=0;i<q;i++){
            int num=0;
            int up=sc.nextInt();
            int side=sc.nextInt();
            
            if(up==dice[0]){
                if(side==dice[1])num=3;
                else if(side==dice[2])num=5;
                else if(side==dice[4])num=4;
                else if(side==dice[3])num=2;
                
        	}else if(up==dice[1]){
                if(side==dice[0])num=4;
                else if(side==dice[3])num=6;
                else if(side==dice[5])num=3;
                else if(side==dice[2])num=1;
                
        	}else if(up==dice[2]){
                if(side==dice[0])num=2;
                else if(side==dice[1])num=6;
                else if(side==dice[5])num=5;
                else if(side==dice[4])num=1;
                
        	}else if(up==dice[3]){
                if(side==dice[0])num=5;
                else if(side==dice[4])num=6;
                else if(side==dice[5])num=2;
                else if(side==dice[1])num=1;
                
        	}else if(up==dice[4]){
                if(side==dice[0])num=3;
                else if(side==dice[2])num=6;
                else if(side==dice[5])num=4;
                else if(side==dice[3])num=1;
                
        	}else{
                if(side==dice[1])num=4;
                else if(side==dice[3])num=5;
                else if(side==dice[4])num=3;
                else if(side==dice[2])num=2;
        	}
            System.out.println(dice[num-1]);
        }
        

		//Dice_1(W, dice);
        
		sc.close();
	}

	public static void Dice_1(String W, int[] dice) {
		String[] w = W.split("");
		for (int i = 0; i < w.length; i++) {
			if (w[i].equals("S")) {
				int num = dice[4];
				dice[4] = dice[5];
				dice[5] = dice[1];
				dice[1] = dice[0];
				dice[0] = num;
			} else if (w[i].equals("W")) {
				int num = dice[2];
				dice[2] = dice[5];
				dice[5] = dice[3];
				dice[3] = dice[0];
				dice[0] = num;
			} else if (w[i].equals("N")) {
				int num = dice[1];
				dice[1] = dice[5];
				dice[5] = dice[4];
				dice[4] = dice[0];
				dice[0] = num;

			} else if (w[i].equals("E")) {
				int num = dice[3];
				dice[3] = dice[5];
				dice[5] = dice[2];
				dice[2] = dice[0];
				dice[0] = num;

			}
		}
	}
}



Measured memory_bytes: 26360
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((int)(x).size())

using namespace std;
typedef long long ll;


vector<long> place[26];
void solve(std::string s, std::string t){
  int s_size = s.size();
  int t_size = t.size();

  REP(i, s_size) place[s[i] - 'a'].push_back(i);

  REP(i, t_size) {
    if (place[t[i] - 'a'].empty()) {
      printf("-1\n");
      return;
    }
  }

  ll ans = 0;
  ll pos = place[t[0] - 'a'][0];
  for (int i = 1; i < t_size; i++) {
    auto next_iter = upper_bound(ALL(place[t[i] - 'a']), pos);

    if (next_iter == place[t[i] - 'a'].end()) {
      ans += s_size;
      pos = place[t[i] - 'a'][0];
    } else {
      pos = *next_iter;
    }
  }

  printf("%lld\n", ans + pos + 1);
}

int main(){
  std::string s;
  std::cin >> s;
  std::string t;
  std::cin >> t;
  solve(s, t);
  return 0;
}


Measured memory_bytes: 1664
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int N=in();
	REP(i,N){
		double x[2],y[2],r[2];
		cin>>x[0]>>y[0]>>r[0]>>x[1]>>y[1]>>r[1];
		double dist = hypot(x[1]-x[0],y[1]-y[0]);

		if(dist>r[0]+r[1]){
			out(0);
		}
		else if(r[0]<r[1] && dist<r[1]-r[0]){
			out(-2);
		}
		else if(r[1]<r[0] && dist<r[0]-r[1]){
			out(2);
		}
		else out(1);
	}
	
	return 0;
}



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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll N, K, S;
    cin >> N >> K >> S;
    vector<ll> ans(N, 0);
    ll acc = 0;
    ll cnt = 0;
    rep(i, N) {
        if (cnt < K) {
            cnt++;
            ans[i] = S;
        } else {
            if (S != 1000000000) {
                ans[i] = S + 1;
            } else {
                ans[i] = S - 1;
            }
        }
    }
    rep(i, N) cout << ans[i] << ' ';

}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 2176
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	int cnt = 0;
	for(char i = '0';i <= '9';++i){
		for(char j = '0';j <= '9';++j){
			for(char k = '0';k <= '9';++k){
				int flg = 0;
				for(int l = 0;l < n;++l){
					if(flg == 0){
						if(s[l] == i) flg = 1;
					}
					else if(flg == 1){
						if(s[l] == j) flg = 2;
					}
					else if(flg == 2){
						if(s[l] == k) flg = 3;
					}
					else break;
				}
				cnt += (flg == 3);
			}
		}
	}
	cout << cnt << '\n';
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<=n;i++)

int main(){
    int n; cin >> n;
    rep(i,100){
        rep(j,100){
            if(n == 4*i+7*j){
                cout << "Yes" << endl;
                return 0;
            } 
        }
    }
    cout << "No" << endl;
    return 0;
}


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

//短縮
#define rep(i,n) for(int i=0;i<(n);++i)
//sort()用
#define all(v) v.begin(), v.end()

#define PB(N) push_back(N)

using namespace std;

using Graph = vector<vector<int>>;

int main(){
  long long A,V,B,W,T;
  cin >> A >> V >> B >> W >> T;

  if(W-V>0) cout << "NO";
  else if(W==V){
    cout << "NO";
  }
  else{
    if(abs(A-B)<=T*(V-W)){
      cout << "YES";
    }
    else cout << "NO";
  }
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,n); for(int i = 0;i < (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
long double pi = acos(-1);
const int INF = 1001001001;


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }


int main(){
  int n;
  cin >> n;
  int colors[9];
  rep(i,9)colors[i] = 0;
  rep(i,n){
    int a;
    cin >> a;
    colors[(min(a / 400,8))]++;
  }
  int min_n = 0;
  int max_n = 0;
  rep(i,8)if(colors[i] != 0)min_n++;
  if(min_n == 0){
    min_n = 1;
    max_n = colors[8];
  }
  else{
    max_n = min_n + colors[8];
  }
  cout << min_n << " " << max_n << endl;
}

Measured memory_bytes: 256
#include "stdio.h"

int main()
{
  int a, b, c[51], d, e, sum = 0;
  scanf("%d", &a);
  for(b = 0; b < a; b++)
  {
    scanf("%d", &c[b]);
  }
  for(d = 0; d < a; d++)
  {
    for(e = d + 1; e < a; e++)
    {
      sum += c[d] * c[e];
    }
  }
  printf("%d", sum);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
string s,t;
int dp[2001][2001][2];
int main()
{
    int m,n;cin >> m >> n >> s >> t;
    int ma = 0;
    for( int i = 0; i <= m; i++ )
    {
        for( int j = 0; j <= n; j++ )
        {
            int a = m - i, b = n - j;
            if( a < m )
            {
                if( s[a] == 'I' ) dp[i][j][0] = dp[i - 1][j][1] + 1;
                else if( dp[i - 1][j][0] ) dp[i][j][1] = dp[i - 1][j][0] + 1;
            }
            if( b < n )
            {
                if( t[b] == 'I' )dp[i][j][0] = max( dp[i][j][0], dp[i][j - 1][1] + 1 );
                else if( dp[i][j - 1][0] )dp[i][j][1] = max( dp[i][j][1], dp[i][j - 1][0] + 1 );
            }
            ma = max( ma, dp[i][j][1] - 1 );
            ma = max( ma, dp[i][j][0] );
        }
    }
    printf( "%d\n", ma );
    return 0;
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll n,m; cin >> n >> m;
    vvl a(n,vl(2));
    ll ac = 0,pe = 0;
    rep(i,m){
        int p;string s;
        cin >> p >> s;
        p--;
        if(s == "AC"){
            if(a[p][0] == 0){
                pe+=a[p][1];
                ac++;
                a[p][0] = 1;
            }
        }
        else{
            a[p][1]++;
        }
    }
    cout << ac << " " << pe << endl;
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	double t,a;
	cin>>n>>t>>a;
	double h[n+1];
	double minn=10000;
	int ind;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		h[i]=t-h[i]*0.006;
		double cha=abs(h[i]-a);
		if(cha<minn)
		{
		   minn=cha;
		   ind=i;
		}   
	}
	cout<<ind<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	double d=n/3.0;
	fcout(8)<<d*d*d<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
using ll = long long;

int main() {
    lli N, Q;
    cin >> N >> Q;

    string S;
    cin >> S;

    vector<lli> l(Q);
    vector<lli> r(Q);

    for (int i = 0; i < Q; ++i) {
        cin >> l[i] >> r[i];
    }

    // 累積和を計算
    vector<lli> count(N);
    lli counter = 0;
    count[0] = 0;
    for (int i = 1; i < N; ++i) {
        if (S[i] == 'C' && S[i - 1] == 'A') {
            ++counter;
        }
        count[i] = counter;
    }


    for (int i = 0; i < Q; ++i) {
        lli numL = l[i] - 1;
        lli numR = r[i] - 1;

        lli answer = count[numR] - count[numL];
        cout << answer << endl;
    }

    return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

lli a, b;

lli F(lli n)
{
  lli ans = (n & 1LL) ^ ((n & 2LL)>>1LL) ? 1 : 0;
  for (int bit = 1; bit < 60; bit ++)
  {
    lli smallest = 1LL << bit;
    if (smallest > n || !(n & smallest)) continue;
    lli cnt = (n & (smallest - 1)) + 1;
    if (cnt & 1LL) ans |= smallest;
    DEBUG printf("\t%d %lld %lld\n", bit, cnt, ans);
  }
  return ans;
}

int main()
{
  while (scanf("%lld %lld", &a, &b) != EOF)
  {
    lli ans = F(max(0LL, a - 1)) ^ F(b);
    printf("%lld\n", ans);
  }
  return 0;
}

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

Int h, w, a, b;
vector<vector<Int>> ans;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> h >> w >> a >> b;
	ans.resize(h, vector<Int>(w, 0));
	for(Int i=0; i<b; ++i)
		for(Int j=0; j<a; ++j)
			ans[i][j] = 1;
	for(Int i=0; i<h-b; ++i)
		for(Int j=0; j<w-a; ++j)
			ans[b+i][a+j] = 1;
	for(auto i:ans){
		for(auto j:i) cout << j;
		cout << "\n";
	}
}

Measured memory_bytes: 9088
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

using namespace std;
typedef long long ll;

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

int main() {

    ll N,X;
    cin >> N >> X;
    ll L[N];
    rep(i,N) cin >> L[i];
    ll D[N+1];
    ll out = 0;
    rep(i,N+1){
        if(i==0) D[i] = 0;
        else D[i] = D[i-1]+L[i-1];
        if(D[i]<=X) out++;
    }
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int i, j;
  int h, w;

  while(1){
    scanf("%d %d", &h,&w);

    if(h ==0 && w == 0)break;

    for ( i = 0 ; i < h; i++ ){
      for(j=0;j<w; j++ ){    
      if(i == 0 || i == h - 1 || j == 0 ||j == w - 1){
	printf("#");
      }
      else{
	printf(".");
      }
    }
    printf("\n");
}
    printf("\n");
  }  
  return 0;
}



Measured memory_bytes: 2028
#include <iostream>
using namespace std;
int main(){
  int N, r = 0;
  cin >> N;
  int count = 0;
  while(N != 0){
    r = N % 10;
    N = N / 10;
    if(r == 2){
      count++;
    }
    //cout << r << endl;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int max(int x, int y){
  if(x<y){return y;}
  else{return x;}
}

int gcm(int x, int y){
  int ma = max(x,y);
  int mi = x + y - ma;
  int p = ma % mi;
  while(p>1){
    ma = mi;
    mi = p;
    p = ma % mi;
  }
  if(p==0){
    return mi;
  }else{
    return 1;
  }
}

int ykrd(int* a, int n){
  int i, g;
  g = gcm(a[0], a[1]);
  for(i=1; i<n-1; i++){
    g = gcm(g, a[i+1]);
  }
  return g;
}

int main(void){
  int N, i;
  scanf("%d", &N);
  int a[N];
  for(i=0; i<N; i++){
    scanf("%d", &a[i]);
  }

  printf("%d", ykrd(&a[0], N));
  return 0;
}


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

/* BFSで解く */
int main() {
  int n, x, y;
  std::cin >> n >> x >> y;
  
  /* グラフ */
  std::vector<std::vector<int>> G(n);

  /* 隣接リスト表現 */
  G[x-1].push_back(y-1);
  G[y-1].push_back(x-1);

  for (int i = 0; i < n-1; ++i) {
    G[i].push_back(i+1); // i=>i+1の辺 
    G[i+1].push_back(i); // i+1=>iの辺
  }


  std::vector<int> d(n, 0); // d[i]には距離がiの数を格納
  
  /* 0~n-1のすべての頂点に関してBFSでそこからの最短距離を計算する */
  for (int i = 0; i < n; ++i) {
    std::vector<int> dist(n, -1); // 出発点からの距離と未発見かどうかを管理 -1=>未発見
    std::queue<int> q;        // 訪問予定の頂点を入れる
    
    dist[i] = 0; // 出発点iの距離は0
    q.push(i);  // iを訪問予定にする

    /* qが空になるまで続ける */
    while (!q.empty()) {
      int v = q.front();
      q.pop();

      /* vと隣接する頂点で未訪問の頂点をqに加える */
      for (int nv : G[v]) {
        /* 訪問済みの頂点はskip */
        if (dist[nv] != -1) continue;

        /* 訪問予定の頂点をqに加える */
        dist[nv] = dist[v] + 1;
        q.push(nv);

        /* 距離をカウント */
        d[dist[nv]]++; 
      }
    }
  }

  /* ダブリを削除 */
  for (size_t i = 1; i < d.size(); ++i) 
    d[i] /= 2;
  
  /* 結果表示 */
  for (size_t i = 1; i < d.size(); ++i)
    std::cout << d[i] << std::endl;

  return 0;
}


Measured memory_bytes: 3660
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
    int n;
    cin >> n;
    vector<int> s(n), t(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        t[i] = s[i];
    }
    sort(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        if(s[i]!=t[n-1]){
            cout << t[n - 1] << endl;
        }else
            cout << t[n - 2] << endl;
    }
    return 0;
}

Measured memory_bytes: 4804
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# ①割引券を使わない場合の最少額
ans = min(a) + min(b)

# 割引券の金額を1つずつ確認し、①よりも低い場合に入れ替える
for _ in range(M):
    x, y, c = map(int, input().split())
    price = a[x - 1] + b[y - 1] - c
    ans = min(ans, price)

print(ans)

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

int main(){
  int n;
  cin >> n;
  ll a[n+1], b[n];
  for(int i=0; i<(n+1); ++i) cin >> a[i];
  for(int i=0; i<n; ++i) cin >> b[i];
  
  ll res = 0;
  for(int i=0; i<n; ++i){
    if((a[i]+a[i+1]) > b[i]){
      res += b[i];
      if(b[i] <= a[i]){
        a[i] -= b[i];
      }
      else{
        a[i+1] -= (b[i] - a[i]);
        a[i] = 0;
      }
    }
    else{
      res += (a[i] + a[i+1]);
      a[i] = 0;
      a[i+1] = 0;
    }
  }
  
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1792
/*suri_kumkaran*/
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
typedef long long int int64;
typedef vector<int64> VI64;
typedef vector<pair<int64,int64>> VII64;
typedef vector<string> VS;
typedef vector<vector<int64>> VVI;
 
int64 fast_pow(int64 a,int64 b)
{
  if(b==1)
    return a%MOD;
  int64 sm=fast_pow(a,b/2);
  int64 ans= (sm*sm)%MOD;
  if(b&1)
    ans=(ans*a)%MOD;
  return ans;
}

int64 MI(int64 a)
{
  return fast_pow(a,MOD-2);
}

int main()
{
    IOS;
    int64 T=1,i,j;
    //cin>>T;
    int64 spf[1000005]={0};
    spf[0]=0;
    spf[1]=1;
    for(i=2;i<=1000002;i++)
    {
      if(!spf[i])
      {
        for(j=i;j<=1000002;j+=i)
          spf[j]=i;
      }
    }
    while(T--)
    {
      unordered_map<int64,int64> lcm;
      int64 n,tem;
      cin>>n;
      int64 ans=0;
      for(i=0;i<n;i++)
      {
        cin>>tem;
        ans+=MI(tem);
        ans%=MOD;
        while(spf[tem]!=1)
        {
          int64 fac=spf[tem];
          int64 cnt=0;
          while(tem%fac==0)
          {
            tem/=fac;
            cnt++;
          }
          lcm[fac]=max(lcm[fac],cnt);
        }
      }
      int64 lcmval=1;
      for(auto x: lcm)
      {
        tem=fast_pow(x.F,x.S);
        lcmval*=tem;
        lcmval%=MOD;
      }
      cout<<(lcmval*ans)%MOD<<endl;
    }
 
    return 0;
}


Measured memory_bytes: 8448
n, k = map(int, input().split())
s = input()
happy = 0

if n == 1:
  print(0)
elif n == 2:
  print(1)
else:
  for i in range(n-1):
    if s[i] == s[i+1]:
      happy += 1
  print(min(happy+2*k, n-1))

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


int main(){
    int n,x; cin>>n;
    cin>>x; int pre=x; ll ans=0;
    for(int i=1;i<n;i++){
       cin>>x;
       if(pre>=x) {ans+=(pre-x);}
       pre=max(pre,x);
    }
    cout<<ans;
}

Measured memory_bytes: 3544
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

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

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

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

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

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

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

fn main() {
    input!(n: usize,w:usize,wv: [(usize,usize);n]);
    let mut wv = wv;
    let result = solve(n, w, &mut wv);
    println!("{:?}",result);
}

pub fn solve(n: usize,w: usize,wv: &mut Vec<(usize,usize)>) -> usize {
    let mut dp = vec![vec![0;w + 1];n + 1];

    for i in 0..n {
        for j in 0..(w + 1) {
            let (weight,value) = wv[i];
            if j >= weight {
                let used = dp[i][j - weight] + value;
                dp[i + 1][j] = if used > dp[i][j] {used} else {dp[i][j]}; 
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    };
    return dp[n][w]  
}

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

def x(a):
    A = 0
    num = []
    while a != 0:
        num.append(a % 10)
        a //= 10
    num.reverse()
    for i in num:
        A += i
    return A

c = 0

for j in range(n+1):
    if (x(j)>=a)and(x(j)<=b):
        c += j

print(c)

Measured memory_bytes: 3060
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n = int(input())
    P = list(map(int, input().split()))
    ans = 0
    arr = [[P[i], i] for i in range(n)]
    arr.sort(key=lambda x: -x[0])
    seg = SegTree(0, n, [0]*n)
    for v, idx in arr:
        seg.update(idx, 1)
        if idx < n-1 and seg.query(idx+1, n) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 1:
                    L = M
                else:
                    R = M
            x = R
            L, R = x, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) < 2:
                    L = M
                else:
                    R = M
            r_range = R - x
            L, R = -1, idx
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) == 0:
                    R = M
                else:
                    L = M
            l_range = idx - L
            ans += v * l_range * r_range
            #print("right : ", v, l_range, r_range)
        if 0 < idx and seg.query(0, idx) > 0:
            L, R = idx, n
            while L+1 < R:
                M = (L+R)//2
                if seg.query(idx+1, M+1) == 0:
                    L = M
                else:
                    R = M
            r_range = R - idx
            L, R = 0, idx
            while L+1 < R:
                M = (L+R)//2
                if seg.query(M, idx) < 1:
                    R = M
                else:
                    L = M
            x = L
            L, R = -1, x
            while L+1 < R:
                M = (L+R+1)//2
                if seg.query(M, idx) < 2:
                    R = M
                else:
                    L = M
            l_range = x - L
            ans += v * l_range * r_range
            #print("right : ", v, l_range, r_range)
        #print("ans : ", v, ans)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 99668