akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(N):
    ans += min(B[i],A[i]+A[i+1])
    if B[i]>A[i]:
        A[i+1] = max(A[i+1]-(B[i]-A[i]),0)
print(ans)

Measured memory_bytes: 19156
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

lst = [i + 1 for i in range(N)]

count = 0
for i in permutations(lst):
    # print (i)
    if i == P:
        a = count
    if i == Q:
        b = count
    count += 1

print (abs(a - b))

Measured memory_bytes: 3064
#include <iostream>

int main() {
    bool memo[1000001] = { 0 };

    int s;
    std::cin >> s;

    for (int i = 1;; i++) {
        if (memo[s]) {
            std::cout << i << std::endl;
            break;
        }
        memo[s] = true;

        if (s % 2 == 0) {
            s /= 2;
        } else {
            s = 3 * s + 1;
        }
    }
    
    return 0;
}

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

#define range 100005
#define mod 1000000007
#define eps 1e-9
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define _ <<" "<<

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;
typedef vector<iii> viii;


vector<ll> a;
vector<ll> b;
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,W;
    cin>>n>>W;
    ll wt[n+1],v[n+1];
    for(int i=1;i<=n;i++)
        cin>>wt[i]>>v[i];
    for(int i=0;i<=100000;i++)
    	a.pb(1e18);
    a[0] = 0 ;
    b=a;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=100000;j++)
        {
            if(v[i]<=j)
              b[j] = min(a[j],a[j - v[i]] + wt[i]);
            else b[j] = a[j];
        }
            
        a = b;
    }
    ll ans = 0;
    for(int i=1;i<=100000;i++)
    {
        if(a[i]<=W)
          ans = i;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 1908
#include<stdio.h>
#include<string.h>
#include<algorithm>
int N,W,dp[105][20005],v[105],w[105],i,j;


int main()
{
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&N,&W);
	for(i=0;i<N;i++)scanf("%d%d",&v[i],&w[i]);
	for(i=N;i>=0;i--)
	{
		for(j=0;j<=W;j++)
		{
			if(i==N)dp[i][j]=0;
			else if(j<w[i])dp[i][j]=dp[i+1][j];
			else dp[i][j]=std::max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
		}
	}
	printf("%d\n",dp[0][W]);
	return 0;
}

Measured memory_bytes: 9240
using System;

namespace ITP1_6_C
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[, ,] room = new int[4, 3, 10];
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 10; k++) room[i, j, k] = 0;
                }
            }

            for (int i = 0; i < n; i++)
            {
                string[] str = Console.ReadLine().Split(' ');
                room[int.Parse(str[0]) - 1, int.Parse(str[1]) - 1, int.Parse(str[2]) - 1] += int.Parse(str[3]);
            }

            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 10; k++) Console.Write(" " + room[i, j, k]);

                    Console.WriteLine();
                }

                if (i != 3)
                {
                    for (int j = 0; j < 20; j++) Console.Write("#");
                    Console.WriteLine();
                }
            }

        }
    }
}

Measured memory_bytes: 9220
//Date and time of submission: 
 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
ll x,a,b;
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin>>x>>a>>b;
	if(abs(x-a)<abs(x-b))
	cout<<"A";
	else
	cout<<"B";
	return 0;
}


Measured memory_bytes: 256
class Tree():
    def __init__(self):
        self.nodes = {}
        self.nodes[-1] = None
    def add_node(self, id):
        if id not in self.nodes:
            self.nodes[id] = Node(id)        
    def add_child(self, parent_id, left_id, right_id):
        self.add_node(parent_id)
        self.add_node(left_id)
        self.add_node(right_id)
        self.nodes[parent_id].add_child(self.nodes[left_id], self.nodes[right_id])
    
class Node():
    def __init__(self, id):
        self.id = id
        self.parent = self.left = self.right = None
        self.depth = self.height = 0

    def add_child(self, left, right):
        self.left = left
        self.right = right
        
        self.update_height()
        
        for child in self.children():
            child.parent = self
            child.update_depth()
    def update_height(self):
        if self.degree():
            self.height = max([child.height + 1 for child in self.children()])
            if self.parent:
                self.parent.update_height()
            
    def update_depth(self):
        self.depth = self.parent.depth + 1
        for child in self.children():
            child.update_depth()
                
    def nodetype(self):
        if self.parent:
            if self.degree():
                return 'internal node'
            else:
                return 'leaf'
        else:
            return 'root'
    def degree(self):
        return len(self.children())
    
    def children(self):
        return [child for child in [self.left, self.right] if child]
    
    def sibling(self):
        if self.parent and self.parent.degree() == 2:
            if self.parent.left == self:
                return self.parent.right.id
            else:
                return self.parent.left.id
        else:
            return -1
        

    def __str__(self):
        return 'node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(
            self.id,
            self.parent.id if self.parent else - 1,
            self.sibling(),
            self.degree(),
            self.depth,
            self.height,
            self.nodetype())
    
tree = Tree()

n = int(input())
for i in range(n):
    id, left, right = map(int, input().split())
    tree.add_child(id, left, right)

for id in tree.nodes:
    if id != -1:
        print(tree.nodes[id])

Measured memory_bytes: 6796
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		String S = scanner.next();
		String T = scanner.next();
		int A = scanner.nextInt();
		int B = scanner.nextInt();
		String U = scanner.next();
		if (S.equals(U)) {
			A--;
		} else {
			B--;
		}
		System.out.println(A + " " + B);
	}
}


Measured memory_bytes: 21204
#include <stdio.h>
#include <iostream>

#include <sstream>
#include <fstream>
#include <cmath>
#include <vector>


using namespace std;


int main( int argc , char ** argv ){
	
	int H = 0 , W = 0;
	cin >> H >> W;

	vector<string> A;
	for(int i =0 ; i < H ; i++){
		string buf;
		cin >> buf;
		A.push_back(buf);
	}

	int count = 0;
	for(auto a : A){
		for(char _a : a){
			if(_a == '#') count ++;
		}
	}


	if(W+(H-1) != count) cout << "Impossible" << endl;
	else cout << "Possible" << endl;
}



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

vector<pair<long long, long long>> prime_factorize(long long n)
{
    vector<pair<long long, long long>> res;
    for (long long p = 2; p * p <= n; ++p)
    {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0)
        {
            ++num;
            n /= p;
        }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

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

    auto pf = prime_factorize(N);
    ll res = 0;
    for (auto p : pf)
    {
        ll e = p.second;
        ll tmp = 0, cur = 1;
        while (e >= cur)
        {
            e -= cur++, ++tmp;
        }
        res += tmp;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3600
#include <iostream>

int main() {
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    int s[m], c[m];
    for(int i = 0; i < m; i++) {
        scanf("%d", s + i);
        scanf("%d", c + i);
        s[i] -= 1;
    }

    int digit[n];
    for(int i = 0; i < n; i++) digit[i] = -1;

    for(int i = 0; i < m; i++) {
        if(digit[s[i]] == -1) {
            digit[s[i]] = c[i];
        }else if(digit[s[i]] != c[i]) {
            printf("-1\n");
            return 0;
        }
    }

    if((digit[0] == 0) && (n > 1)) {
        printf("-1\n");
        return 0;
    }

    for(int i = 0; i < n; i++) {
        if(digit[i] == -1) {
            if(i == 0 && n > 1) {
                digit[i] = 1;
            }else {
                digit[i] = 0;
            }
        }
        printf("%d", digit[i]);
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int s=0;
  int x=n;
  while(x>0){
    s+=x%10;
    x/=10;
  }
  cout<<(n%s==0?"Yes":"No")<<endl;
}

Measured memory_bytes: 3536
N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
illegal=False
for i in range(N):
  if illegal:
    break
  
  node_list=[-1]*N
  #bfs
  d=1
  queue={i}
  while(True):
    new_queue=set()
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.add(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)


Measured memory_bytes: 3444
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n, k, a, b; cin >> n >> k;
	for (int h = 0; h < k; h++) {
		cin >> a >> b;
		if (n - a + 1 < a) { a = n - a + 1; }
		if (n - b + 1 < b) { b = n - b + 1; }
		if (n - a >= a && n - b >= b) {
			if (min(a, b) % 3 != 0) {
				cout << min(a, b) % 3 << endl;
			}
			else {
				cout << 3 << endl;
			}
		}
	}
	cin >> n;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string in;
	int a, b;
	vector<int> st;

	while (cin >> in) {
		if (in.at(0) >= '0' && in.at(0) <= '9') {
			st.emplace_back(stoi(in));
		} else {
			b = st.back();
			st.pop_back();
			a = st.back();
			st.pop_back();
			if (in.at(0) == '+') {
				st.emplace_back(a + b);
			} else if (in.at(0) == '-') {
				st.emplace_back(a - b);
			} else if (in.at(0) == '*') {
				st.emplace_back(a * b);
			}
		}
	}
	cout << st.back() << endl;
}


Measured memory_bytes: 3236
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] country = new int[sc.nextInt()];
		int M = sc.nextInt();
		for(int i = 0; i < M; i++) {
			int point = sc.nextInt()-1;
			country[point] = country[point]+1;
			point = sc.nextInt()-1;
			country[point] = country[point]+1;
		}
		for (int i : country) {
			System.out.println(i);
		}
	}

}


Measured memory_bytes: 21844
package main

import "fmt"

func main() {
	var x, ans int
	fmt.Scan(&x)
	ans = (x / 11) * 2
	if x%11 != 0 {
		if x%11 > 6 {
			ans += 2
		} else {
			ans++
		}
	}
	fmt.Println(ans)
}


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

int main(){
	string s;
	cin >> s;
	int cnt=0;
	for (auto& i:s){
		if (i == 'o') ++cnt;
	}
	int a=cnt+15-s.size();
	if (a >= 8)cout << "YES";
	else cout << "NO";
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    private static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(final String[] args) throws IOException {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out, true);

        int n = in.nextInt();
        String[] tokens = in.nextLine().split(" ");

        int max = 0;
        int count = 0;

        int previous = Integer.parseInt(tokens[0]);
        int current = 0;

        for (int i = 1; i < n; i++) {
            current = Integer.parseInt(tokens[i]);
            if (current <= previous) {
                count++;
            } else {
                max = Math.max(max, count);
                count = 0;
            }
            previous = current;
        }
        max = Math.max(max, count);

        out.println(max);
    }
}


Measured memory_bytes: 45012
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

struct tri{
  ll f,s,t;
};

bool comp(const tri& l, const tri& r){
  return l.t < r.t;
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N;ll K;cin >> N >> K;
  vector<tri> v(N);
  ll b;
  b = K+2*N-1;
  int index = 0;
  repp(x,K,K+N){
    if(x%2==0)continue;
    v[index].f = x;
    v[index].s = b;
    v[index].t = x+b;
    ++index;
    --b;
  }
  repp(x,K,K+N){
    if(x%2==1)continue;
    v[index].f = x;
    v[index].s = b;
    v[index].t = x+b;
    ++index;
    --b;
  }

  sort(all(v),comp);
  ll c = K+2*N;
  rep(i,N){
    if(v[i].t>c){
      cout << -1 << endl;
      return 0;
    }
    v[i].t = c;
    ++c;
  }
  rep(i,N) cout << v[i].f SP v[i].s SP v[i].t << endl;
  return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int64_t MOD = 1e9 + 7;

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

  int64_t N, K;
  cin >> N >> K;
  int64_t div = N / K;
  int64_t res = N;
  res = min(res, N - div * K);
  res = min(res, abs(N - (div + 1) * K));
  cout << res << endl;


  return 0;
}


Measured memory_bytes: 256
# 配るDP
import math
import numpy as np
import copy
from collections import defaultdict, Counter
from itertools import product
from bisect import bisect_left, bisect_right

def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))

N = int(input())
h = inpl()

INF = float('inf')

# 最小化問題なのでINFに初期化
dp = [ INF ] * N

# 初期状態
dp[0] = 0

# ループ
for i in range(0, N-2):
    dp[i+1] = min(dp[i+1], dp[i] + abs(h[i] - h[i+1]))
    dp[i+2] = min(dp[i+2], dp[i] + abs(h[i] - h[i+2]))

dp[-1] = min(dp[-1], dp[-2] + abs(h[-1] - h[-2]))
print(dp[N-1])

Measured memory_bytes: 22780
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,a,b;
    cin>>x>>a>>b;
    string s;
    if(b-a<=0)
        cout<<"delicious\n";
    else if(b-a<=x)
        cout<<"safe\n";
    else
        cout<<"dangerous\n";
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <complex>

#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define tr(c, i) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define rtr(c, i) for (typeof((c).rbegin()) i = (c).rbegin(); i != (c).rend(); --i)
#define contains(c, x) ((c).find(x) != (c).end())
#define Contains(c, x) (find(all(c), x) != (c).end())
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) REP(i, 0, (n))
#define To_String to_string< char,std::char_traits<char>,std::allocator<char> >

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll p[12];
ll func(ll n)
{
	string s;
	int c = 0;
	while (n) {
		int t = n % (-10) + c;
		s += char('0' + (t + 10) % 10);
		if (t == 10) n += 10;
		n /= (-10);
		c = (t < 0);
	}
	if (c) s += '1';
	reverse(all(s));
	return atoll(s.c_str());
}
int main()
{
	ios_base::sync_with_stdio(0);
	p[0] = 1;
	REP(i, 1, 12) p[i] = -10 * p[i-1];

	ll n;
	while (cin >> n) {
		if (n == 0) break;
		cout << func(n) << endl;
	}

	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		char[] array = scanner.next().toCharArray();

		int a = Character.getNumericValue(array[0]);
		int b = Character.getNumericValue(array[1]);
		int c = Character.getNumericValue(array[2]);
		int d = Character.getNumericValue(array[3]);

		String op1 = "+";
		String op2 = "+";
		String op3 = "+";

		int ans = a;

		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					ans = a;
					if (i == 0) {
						ans += b;
					} else {
						ans -= b;
					}
					if (j == 0) {
						ans += c;
					} else {
						ans -= c;
					}
					if (k == 0) {
						ans += d;
					} else {
						ans -= d;
					}
					if(ans == 7){
						if(i == 1){
							op1 = "-";
						}
						if(j == 1){
							op2 = "-";
						}
						if(k == 1){
							op3 = "-";
						}
						System.out.println(a + op1 + b + op2 + c + op3 + d + "=7");
						return;
					}
				}
			}
		}
	}
}


Measured memory_bytes: 23124
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			int num = sc.nextInt();
			list.add(num);
		}
		if (N == 1) {
			System.out.println(1);
			return;
		}
		Collections.sort(list);
		int[] ar = new int[1000001];
		for (int i = 0; i < list.size(); i++) {
			int num = list.get(i);
			int x = num;
			if (ar[x] != 0) {
				ar[x]++;
				continue;
			}
			int index = 2;
			while (x < 1000001) {
				ar[x]++;
				x = num * index;
				index++;
			}
		}
		long count = 0;
		for (Integer i : list) {
			if (ar[i] == 1) {
				count++;
			}
		}
		System.out.println(count);
	}
}

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

int main(){
	int n,ans=1,h,mah;
	cin>>n>>mah;
	for(int i=1;i<n;i++){
		cin>>h;
		if(h>=mah){
			ans++;
			mah=h;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
int gcd(int A,int B){
  if(A<B)
    swap(A,B);
  while(1){
    if(A%B==0)
      return B;
    int C=A%B;
    A=B;
    B=C;
  }
}
int minX(int A,int B){
  int C=gcd(A,B);
  return A*B/C;
}
signed main(){
  int N;
  cin>>N;
  int T,A;
  cin>>T>>A;
  int ans=T+A;
  rep(i,1,N){
    int t,a;
    cin>>t>>a;
    if(T<=t&&A<=a){
      T=t;
      A=a;
    }
    else{
      int TK=(T+t-1)/t,AK=(A+a-1)/a;
      T=t*max(TK,AK);
      A=a*max(TK,AK);
    }
  }
  ans=T+A;
  cout<<ans<<endl;
  }



Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
        #define ll long long int
        #define pb push_back
        #define mk make_pair
        #define ft first
        #define sc second
        #define ppb pop_back
        #define sz size
        #define forn(i,a,n) for(i=a;i<n;i++)
        #define M 998244353 
        #define inf 2e18
        
        int main() {
 
 
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        ll n;
        cin>>n;
        // ll ans=0;
        ll ans = (n/500)*1000;
        n%=500;
        ans += (n/5)*5;
        cout<<ans;

        return 0;
        }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main(){
    int A,B,C; cin >> A >> B >> C;
    int d[3] = {A,B,C};
    sort(d,d+3);
    int K; cin >> K;
    for (int i=0;i<K;i++) d[2]*=2;
    cout << d[0]+d[1]+d[2] << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        final long INF = (long) 1e15;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        long[] b = new long[n];
        for (int i = 0; i < n; i++) {
            b[i] = INF;
        }

        long ans = INF;
        for (int k = 0; k < n; k++) {
            long tmp = x * k;
            for (int i = 0; i < n; i++) {
                b[i] = Math.min(b[i], a[(i - k + n) % n]);
                tmp += b[i];
            }
            ans = Math.min(ans, tmp);
        }

        System.out.println(ans);
    }
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vi a(n);
    rep(i,n) cin>>a[i];
    ll ans=0;
    rep(i,n) ans+=a[i]-1;
    cout<<ans<<endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int n, k;
	cin >> n >> k;

	ll a[n];
	rep(i, n) cin >> a[i];

	ll MOD = 1e9+7;
	ll dp[2][k+1];
	// dp[i%2][j] : i-1番目の子供で飴がj個余るときの分け合う方法数
	rep(i, 2) rep(j, k+1) dp[i][j] = 0;
	dp[0][k] = 1;
	for(int i = 0; i < n; i++){
		dp[(i+1)%2][k] = dp[i%2][k];
		for(int j = k-1; j >= 0; j--){
			if(j >= k-a[i]){
				dp[(i+1)%2][j] = dp[(i+1)%2][j+1] + dp[i%2][j];
				dp[(i+1)%2][j] %= MOD;
			}
			else{
				dp[(i+1)%2][j] = dp[(i+1)%2][j+1] + dp[i%2][j];
				dp[(i+1)%2][j] %= MOD;
				dp[(i+1)%2][j] += MOD - dp[i%2][j+1+a[i]];
				dp[(i+1)%2][j] %= MOD;
			}
		}
	}

	cout << dp[n%2][0] << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD (1000000007)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

string s,t;

void input(){
    cin >> s >> t;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    int sz = s.size();
    string tmp = s;
    for(int i=0;i<sz;i++){
        string rec = tmp[sz-1] + tmp.substr(0, sz-1);
        if(rec == t){
            cout << "Yes" << endl;
            return 0;
        }
        tmp = rec;
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001

const ll MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

using mint = Fp<MOD>;

int main(){
    int L, R, d;
    int cnt = 0;
    cin >> L >> R >> d;
    for(int i = L; i <= R; i++){
        if(i % d == 0) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;++i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(), (c).end()


typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;


pair<Weight, Edges> minimumSpanningTree(const Graph &g, int r = 0) {
  int n = g.size();
  Edges T;
  Weight total = 0;

  vector<bool> visited(n);
  priority_queue<Edge> Q;
  Q.push( Edge(-1, r, 0) );
  while (!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (visited[e.dst]) continue;
    T.push_back(e);
    total += e.weight;
    visited[e.dst] = true;
    foreach(f, g[e.dst]) if (!visited[f->dst]) Q.push(*f);
  }
  return pair<Weight, Edges>(total, T);
}

int main() {
	int n,m;
	while(cin>>n>>m,n){
		Graph g(n);
		rep(i,m){
			int a,b,c; cin>>a>>b>>c;
			g[a].push_back(Edge(a,b,c));
			g[b].push_back(Edge(b,a,c));
		}
		cout<<minimumSpanningTree(g).first<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <numeric>

using namespace std;
long long int lcm(long long int a, long long int b) {
  long long int x = a * b;
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    long long int tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  long long int r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
  /* 最小公倍数を出力 */
  return x/b;
}

int main() {
  long long int a, b, c, d;
  cin >> a >> b >> c >> d;
  long long int c1 = (a % c == 0)? a / c : a/c + 1;
  long long int c2 = b / c;
  long long int c3 = (c2-c1+1);

  long long int d1 = (a % d == 0)? a / d : a/d + 1;
  long long int d2 = b / d;
  long long int d3 = (d2-d1+1);
  long long int lc= lcm(c,d);
  long long int e1 = (a % lc == 0)? a/lc : a/lc + 1;
  long long int e2 = b / lc;
  long long int e3 = (e2-e1+1);
  long long int n = b-a+1;
  long long int ans = n - (c3 + d3 - e3);
  if (c > n && a <= c && c <= b) ans++;
  if (d > n && a <= d && d <= b && c != d) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int N=100005,mu=1000000007;
int to[N<<1],edge,Next[N<<1],last[N],dp[2][N],x,y,n;
void add(int x,int y){
	to[++edge]=y;
	Next[edge]=last[x];
	last[x]=edge;
} 
void dfs(int x,int fa){
	dp[0][x]=dp[1][x]=1;
	for (int i=last[x];i;i=Next[i])
	if(to[i]!=fa){
		int u=to[i];
		dfs(u,x);
		dp[0][x]=1ll*dp[0][x]*dp[1][u]%mu;
		dp[1][x]=1ll*dp[1][x]*(dp[1][u]+dp[0][u])%mu;
	}
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	printf("%d\n",(dp[0][1]+dp[1][1])%mu); 
}

Measured memory_bytes: 8576
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100+10;
int n, a, b, p[N], c1, c2, c3;
int main()
{
	scanf( "%d%d%d", &n, &a, &b );
	for ( int i=1; i<=n; i++ ) 
	{
		scanf( "%d", &p[i] );
		if ( p[i]<=a ) ++c1;
		else if ( p[i]>=b+1 ) ++c2; 
		  else ++c3;
	}
	printf( "%d", min( c1, min( c2, c3 ) ) );
	return 0;
}

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

int gcd(long x, long y){
    if(x < y)swap(x, y);
    while(y>0){
        int r =  0;
        r = x%y;
        x = y;
        y = r;
    }
    cout << x << endl;
  return 0;
}

int main(){
  long a, b;
  cin >> a >> b;
  gcd(a, b);
}


Measured memory_bytes: 3092
N = int(input())
a = [int(x) for x in input().split()]
ans = 0
c = 1
tmp = 0
if 1 not in a:
    print(-1)
    quit()
for i in range(N):
    if a[i] == c:
        ans += i - tmp
        c += 1
        tmp = i+1
    elif i == N-1:
        ans += i - tmp + 1
print(ans)

Measured memory_bytes: 25768
n = int(input())
s = input()
turn = [0]
for i in range(n):
  if s[i] == 'W':
    turn.append(turn[-1] + 1)
  else:
    turn.append(turn[-1])
ans = n
for i in range(n):
  ans = min(ans, turn[i] + n - 1 - i - turn[n] + turn[i + 1])
print(ans)


Measured memory_bytes: 15520
#include<bits/stdc++.h>
//#include "/Users/Coder_Jay/Desktop/Codeforces/header.h"
 
// Competetive Template:
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
 
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ba  back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi first
#define se second
#define gcd __gcd
#define maxe *max_element
#define mine *min_element
 
#define forz(i,n) for(long long int i=0;i<n;i++)
#define rep(i,k,n) for (lli i = k; i <= n; i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define  START      auto start = chrono::steady_clock::now()
#define END         auto end = chrono::steady_clock::now()

using namespace std;
typedef pair <lli,lli> pll;
 
// CODE BEGINS :

int main()
{
    kira; START;
    
    lli k, x; cin>>k>>x;

    lli c=500*k;

    if(c>=x) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    END;
    return 0;
}





















Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	a,b,c = inputMap()
	getcontext().prec = 20007

	if Decimal(Decimal(a).sqrt() + Decimal(b).sqrt()) < Decimal(c).sqrt():
		print("Yes")
	else:
		print("No")


if __name__ == "__main__":
	main()


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

using namespace std;

long long a[200100], b[200100];
long long asum[400100];

int main()
{
    long long n, m, k;
    scanf("%lld%lld%lld", &n, &m, &k);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
        asum[i] = asum[i-1] + a[i];
    }
    long long ans =  upper_bound(asum+1, asum+1+n, k) - (asum+1);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%lld", &b[i]);
        if(b[i] <= k)
        {
            k -= b[i];
            ans = max(ans, (long long)(i+upper_bound(asum+1, asum+1+n, k) - (asum+1)));
        }else{
            break;
        }
    }
    printf("%lld\n", ans);

}

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

int main() {
  ll N;
  cin >> N;
  ll sum = 0;
  for(ll i=1; i<=N; i++) {
    if(i%15==0 || i%5==0 || i%3==0) continue;
    sum+=i;
  }
  cout << sum <<endl;
}

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;

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

    ll N, W, b; cin >> N >> W;
    vector<ll> w(N), v(N);
    vector<pair<ll, ll>> a[4];
    rep(i, N) {
        cin >> w[i] >> v[i];
        if (i == 0) b = w[i];
        a[w[i]-b].pb(make_pair(v[i], w[i]));
    }
    rep(i, 4) sort(rall(a[i]));
    rep(i, 4) a[i].insert(a[i].begin(), make_pair(0, 0));
    rep(i, 4) rep(j, a[i].size() - 1) {
        a[i][j+1].first += a[i][j].first;
        a[i][j+1].second += a[i][j].second;
    }
    ll res = 0;
    rep(i, a[0].size()) {
        rep(j, a[1].size()) {
            rep(k, a[2].size()) {
                rep(l, a[3].size()) {
                    if (a[0][i].second + a[1][j].second + a[2][k].second + a[3][l].second > W) continue;
                    res = max(res, a[0][i].first + a[1][j].first + a[2][k].first + a[3][l].first);
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define exists(s,x) (s).find(x)!=(s).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)
#define fi first
#define se second
typedef long long ll;
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

inline ll add(ll x, ll y) {return (x+y)%MOD;}
inline ll mul(ll x, ll y) {return (x*y)%MOD;}
inline ll sub(ll x, ll y) {
    ll res = x - y;
    if(res < 0) res += MOD;
    return res;
}
inline ll modpow(ll x, ll y) {
    ll res = 1;
    while(y) {
        if(y&1) res = mul(res,x);
        y >>= 1;
        x = mul(x,x);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;
    ll A, B; cin >> A >> B;
    ll amari = N % (A + B);
    ll shou = N / (A + B);
    ll ans = shou * A;
    ans += min(A,amari);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define llint long long

using namespace std;

string s, t;
llint n, m;
llint l, r;
llint z[200005];
llint a[26], b[26];
llint len[105], num[105][26];

void z_algorithm(string &s, llint z[])
{
	z[0] = s.size();
	
	int x = 0, y = 0;
	for(int i = 1; i < s.size(); i++){
		if(i > y){
			z[i] = 0;
			for(int j = 0; j < s.size(); j++){
				if(i+j > s.size() || s[i+j] != s[j]) break;
				z[i]++;
			}
			x = i, y = i + z[i] - 1;
		}
		else if(i + z[i-x] <= y) z[i] = z[i-x];
		else{
			z[i] = y-i+1;
			for(int j = y-i+1; j < s.size(); j++){
				if(i+j > s.size() || s[i+j] != s[j]) break;
				z[i]++;
			}
			x = i, y = i + z[i] - 1;
		}
	}
}

void calc(llint x, llint a[])
{
	if(x < 0) return;
	for(int i = 0; i < n; i++) a[s[i]-'a'] += x/n;
	for(int i = 0; i < x%n;i++) a[s[i]-'a']++;
}

void calc2(llint x, llint a[])
{
	if(x <= n){
		for(int i = 0; i < x; i++) a[s[i]-'a']++;
		return;
	}
	for(int i = 2; ; i++){
		if(x < len[i]){
			for(int j = 0; j < 26; j++) a[j] += num[i-1][j];
			calc2(x-len[i-1], a);
			break;
		}
	}
}

int main(void)
{
	cin >> s >> l >> r;
	s = s.substr(0, (int)s.size()/2);
	n = s.size();
	
	z_algorithm(s, z);
	int p = -1;
	for(int i = 1; i < n; i++){
		if(z[i] == n-i){
			p = i;
			break;
		}
	}
	if(p == -1){
		calc(r, a), calc(l-1, b);
		for(int i = 0; i < 26; i++) cout << a[i]-b[i] << " "; cout << endl;
		return 0;
	}
	
	t = s.substr(0, p);
	m = t.size();
	
	len[0] = m, len[1] = n;
	for(int i = 0; i < m; i++) num[0][t[i]-'a']++;
	for(int i = 0; i < n; i++) num[1][s[i]-'a']++;
	for(int i = 2; ; i++){
		len[i] = len[i-1] + len[i-2];
		for(int j = 0; j < 26; j++) num[i][j] = num[i-1][j] + num[i-2][j];
		if(len[i] > 1000000000000000000) break;
	}
	
	calc2(r, a), calc2(l-1, b);
	for(int i = 0; i < 26; i++) cout << a[i]-b[i] << " "; cout << endl;
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s, n,m;
getline(cin,s);
int l = s.size();
int x=0,y=0,z=0;
string s1, n1, m1;
s1 = s;
reverse(s.begin(),s.end());
if(s==s1)
    x = 1;
n = s.substr(0,(l-1)/2);
n1 = n;
reverse(n.begin(),n.end());
m = s.substr(((l+3)/2)-1);
m1 = m;
reverse(m.begin(),m.end());
if(n==n1)
    y =1;
if(m==m1)
    z =1;
    
if(x==1 && y==1 && z==1)
cout<<"Yes";
else
cout<<"No";
    return 0;
}


Measured memory_bytes: 256
import sys
from scipy.sparse.csgraph import floyd_warshall as f
def main():
  n,m,l,*t=map(int,sys.stdin.buffer.read().split())
  d=[[0]*(n+1)for _ in range(n+1)]
  for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=c
  d=f(f(d,0)<=l)
  d[d>n]=0
  print('\n'.join(map(str,map(int,[d[i]-1for i in zip(*[iter(t[m*3+1:])]*2)]))))
main()

Measured memory_bytes: 36252
/*
created by sanyam singhal
*/

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

#define pb push_back
#define mp make_pair
#define ll long long int
#define mod 1000000007
#define w(t) int t;	cin>>t while(t--)
#define triplet pair<int,pair<int,int>>
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define fastIO ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);
#define loop(i, k, n) for(ll i=k; i<n; i+=1)
#define loop2(i, k, n) for(ll i=k; i>=n; i--)
const ll inf = 1e18;

int n;  
int mat[22][22];

ll visited_all;
ll dp[22][1LL<<22];

void take_fileIO(){
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
  return;
}

ll recursive_solve(int i, int n, ll mask){
  if(visited_all==mask)
    return 1;
  else if(i==n)
    return 0;
  else if(dp[i][mask]!=-1)
    return dp[i][mask];
  else{
    ll ans=0;
    for(int j=0; j<n; j++){
      ll curr_mask = (1<<j);
      // cout<<i<<" "<<j<<" "<<curr_mask<<endl;
      // cout<<"mask result "<< (mask&curr_mask) <<endl;
      if(mat[i][j]==1 &&  ((mask&curr_mask) == 0)){

          // cout<<i<<" || "<<j<<" "<<curr_mask;
          ans = (ans + recursive_solve(i+1, n, (mask|curr_mask)))%mod;
      }
    }
    return dp[i][mask]=ans;
  }
}

void solve(){ 
  cin>>n;
  visited_all = (1<<n)-1;
  // cout<<visited_all<<endl;
  loop(i, 0, n)
    loop(j, 0, n)
      cin>>mat[i][j];
  memset(dp, -1, sizeof(dp));
  cout<<recursive_solve(0, n, 0LL)<<endl;
}

int main(){

  fastIO;
  // take_fileIO();
  solve();
  return 0;
}

Measured memory_bytes: 721280
#include <bits/stdc++.h>
#define FOR(v, a, b) for(int v = (a); v < (b); ++v)
#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(int v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define LLI long long int
#define fst first
#define snd second
#ifdef DEBUG
#include <boost/core/demangle.hpp>
#define dump(x) cerr << "L" << __LINE__ << ": in " << __PRETTY_FUNCTION__ << " \e[32;1m" << boost::core::demangle(typeid(x).name()) << "\e[37m" << " " << (#x) << " = " << (x) << "\e[m" << endl;
#else
#define dump(x)
#endif
using namespace std;
template <typename T> using V = vector<T>;
template <typename T, typename U> using P = pair<T,U>;
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}

template <typename T> ostream& operator<<(ostream &os, vector<T> &v){os << "{";ITR(i,v){if(i!=v.begin())os << ","; os << *i;}os << "}"; return os;}
template <typename T, typename U> ostream& operator<<(ostream& os, pair<T,U> &p){os << "(" << p.first << "," << p.second << ")"; return os;}

template <typename T> T& chmin(T &a, const T &b){return a = min(a,b);}
template <typename T> T& chmax(T &a, const T &b){return a = max(a,b);}

LLI dp[410][410];
bool visit[410][410];
vector<LLI> a, s;

LLI rec(int l, int r){ // [l,r)
  if(l+1==r) return 0;
  if(l+2==r) return a[l]+a[l+1];
  if(visit[l][r]) return dp[l][r];
  visit[l][r] = true;

  dp[l][r] = 1e18;
  FOR(i,l+1,r){
    chmin(dp[l][r], rec(l,i) + rec(i,r));
  }
  
  dp[l][r] += s[r] - s[l];

  return dp[l][r];
}

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

  int N; cin >> N;
  a = vector<LLI>(N); cin >> a;
  s = vector<LLI>(N+1);
  REP(i,N) s[i+1] = s[i] + a[i];
  
  cout << rec(0, N) << endl;
  
  return 0;
}


Measured memory_bytes: 1792
n,m = map(int,input().split())
h = [int(i) for i in input().split()]
flag = [True]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if h[a] >= h[b]: flag[b] = False
    if h[a] <= h[b]: flag[a] = False
ans = 0
for i in range(n):
    if flag[i]: ans += 1
print(ans)




Measured memory_bytes: 20116
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
#include <random>
#include <time.h>
#include <unordered_set>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

namespace std {
    template <>
    class hash<std::pair<int, int>> {
    public:
        size_t operator()(const std::pair<int, int>& x) const{
            return hash<int>()(x.first) ^ hash<int>()(x.second);
        }
    };
}

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for (int i = 0;i < 60; i++) {
        if (n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main(void) {
    int N; cin >> N;
    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        A[i] = {a, i+1};
    }
    sort(A.begin(), A.end());
    for (auto p : A) {
        cout << p.second << " ";
    }
    cout << endl;
}


Measured memory_bytes: 1664