akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	string s; cin >> s;
	int n=s.size();
	bool f=0;
	REP(i,n/2){
		if(s[i]!=s[(n-1)/2+1+i])
			f=1;
	}
	int r=(n-1)/2;
	REP(i,r/2){
		if(s[i]!=s[r-1-i])
			f=1;
	}
	if(f){
		cout << "No" << endl;
	}
	else{
		cout << "Yes" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <set>
#include <map>
#include <list>
#include <cstdlib>
#include <queue>
#include <stack>
#include <bitset>

using namespace std;

#define MOD 1000000007
#define PI 3.1415926535897932
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define repi(i, n) for (int i = 0; i <= n; i++)
#define repie(i, j, n) for (int i = j; i <= n; i++)
#define all(x) x.begin(), x.end()
#define println() cout << endl
#define P pair<int, int>
#define fi first
#define se second

typedef long long ll;

long long modinv(long long a, long long m)
{
    long long b = m, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}

void solve1() {
    int n; cin >> n;
    vector<int> h(n); rep(i, n) cin >> h[i];

    int dp[n+n]; dp[0] = 0;

    for(int i = 1; i < n; i++)
    {
        if (i - 1 >= 1)
            dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
        else
            dp[i] = dp[i - 1] + abs(h[i - 1] - h[i]); //i-2<1のときi-2の足場はないのだ！
    }

    cout << dp[n-1] << endl;
}

int main()
{
    solve1();
}


Measured memory_bytes: 3976
/*  
     author : masaow    
     g++ : 17.3.20  
*/        
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- "
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long  
#define p(x)               cout << x << "\n" ; 
#define MOD                100000007
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"
#define mi                 map <int,int> 
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             x.begin(),x.end() 
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;  
/*  
    time : 10 : 14    
    date : 24.01.2020
*/    
// int L,R,mid,target,idx ;
string S1,S2 ;
string S ; 
int best[3013][3013] ; 
int solve(int p1 ,int p2){ 
  if(p1 == -1 || p2 == -1 ){
    return 0 ; 
  } 
  if(best[p1+1][p2+1] != -1 )
    return best[p1+1][p2+1] ; 
  if(S1[p1] == S2[p2]){ 
    return (best[p1+1][p2+1] = 1 + solve(p1-1,p2-1)) ;
  } 
  int result = 0 ; 
  result = max(solve(p1-1,p2),solve(p1,p2-1)) ;
  return (best[p1+1][p2+1] = result)  ; 
}
int tests() 
{   
  cin >> S1 >> S2 ; 
  int i,j ; 
  forn(i,0,S1.size()+1 )
    forn(j,0,S2.size()+1)
      best[i][j] = -1 ; 

  solve(S1.size()-1,S2.size()-1)  ;     
  i = S1.size() ;  
  j = S2.size() ;  
  while(i > 0 && j  > 0){
    if(S1[i-1] == S2[j-1])
      S.pb(S2[--j]),--i ; 
    else if(best[i][j] == best[i-1][j])
      i-- ; 
    else 
      j-- ; 
  }    
  reverse(all(S)) ; 
  cout << S << '\n';
  
}

int main(){
    I__O ;  
    int cases = 1 ; 
    //cin >> cases;  
    while(cases--)
      tests(); 
  return 0 ; 
}

Measured memory_bytes: 35968
//vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n; 
  cin >> n;
  vector<double>x(n);
  vector<string>u(n);
  rep(i,n) cin >> x.at(i) >> u.at(i);
  double sum=0;
  rep(i,n){
    if(u.at(i)=="JPY") sum += x.at(i);
    else if(u.at(i)=="BTC") sum+= x.at(i) * 380000;
//  cout << x.at(i) << endl;
//  cout << u.at(i) << endl;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

int main() {
  i64 n;
  cin >> n;
  i64 ans = n - 1;
  for(i64 i = 1;i * i <= n;i++) {
    if(n % i == 0) {
      ans = min(ans, i - 1 + (n / i) - 1);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
ms = [list(map(int, input().split())) for _ in range(m)]
res = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i!=j:
            uf.union(ms[j][0]-1,ms[j][1]-1)
    if len(uf.roots())!=1:
        res += 1
print(res)

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

using namespace std;



int main(void)
{
    vector<vector<int>> num(3,vector<int>(3));
    
    for (int i = 0; i < 3;i++){
        for (int j = 0; j < 3;j++){
            cin >> num.at(i).at(j);
        }
    }
    int t = num.at(0).at(1)-num.at(0).at(0);
    int t2 = num.at(0).at(2) - num.at(0).at(1);
    int tempj = num.at(1).at(0) - num.at(0).at(0);
    int tempj2 = num.at(2).at(0) - num.at(1).at(0);

    for (int i = 1; i < 3; i++){
            if (num.at(i).at(1) - num.at(i).at(0)!=t){
                cout << "No" << endl;
                return 0;
            }
            if (num.at(i).at(2) - num.at(i).at(1) != t2){
                cout << "No" << endl;
                return 0;
            }
            if (num.at(1).at(i) - num.at(0).at(i) != tempj){
                cout << "No" << endl;
                return 0;
            }
            if (num.at(2).at(i) - num.at(1).at(i) != tempj2){
                cout << "No" << endl;
                return 0;
            }
    }
    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#import numpy as np
#from itertools import combinations as comb
from itertools import combinations_with_replacement as comb_with
A = int(input())
#A,B= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())

B = int(input())
C = int(input())
X = int(input())

l=0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            m=a*500 + b*100 + c *50
            if m==X:
                l+=1
print(l)


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

int main()
{
    string s;
    cin >> s;

    ll ans = 0;
    ll cnt = 0;
    for (ll i = 0; i < s.length(); i++)
    {
        if (s[i] == 'R')
            cnt++;
        else
        {
            ans = max(cnt, ans);
            cnt = 0;
        }
    }
    ans = max(cnt, ans);

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


Measured memory_bytes: 3720
n,m = list(map(int,input().split()))

a = []
for i in range(m):
    a.append(list(map(int,input().split())))

b = [[0 for i in range(n)] for j in range(n)]

for i in a:
    b[i[1]-1][i[0]-1] = 1
    b[i[0]-1][i[1]-1] = 1
c = [sum(b[i]) for i in range(n)]
ans = 0
while 1 in c:
    d = c.index(1)
    e = b[d].index(1)
    b[e][d] = 0
    b[d][e] = 0
    c = [sum(b[i]) for i in range(n)]
    ans += 1
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;

int main()
{
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    vector<vector<int>> grid(h, vector<int>(w, 0));
    rep(i,h)rep(j,w){
        if(i<h-b&&j<a){
            grid[i][j]=1;
        }else if(a<=j&&h-b<=i){
            grid[i][j]=1;
        }
    }
    rep(i,h)rep(j,w){
        cout<<grid[i][j];
        if(j==w-1)cout<<endl;
    }
}

Measured memory_bytes: 5120
#include<iostream>

using namespace std;
 
int main(void)
{
  int n,x,t; cin>>n>>x>>t;
  unsigned long int sum=0,r=0;
  
  for(;;){
    if(n<=sum){break;}
    sum+=x;
    r+=t;
  }
  
  cout<<r<<endl;
    
  return 0;
}

Measured memory_bytes: 3588
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if ((a < 0 && b > 0 ) || a == 0 || b == 0) {
			System.out.println("Zero");
		} else {
			if ((a < 0 && b < 0) && ((b - a) % 2 == 0)) {
			    System.out.println("Negative");
			} else {
				System.out.println("Positive");
			}
		}
		
	}
}

Measured memory_bytes: 9428
// Created by abhay
#include <bits/stdc++.h>
#define sz(a) int((a).size())
#define pb push_back
#define allc c.begin(),c.end()
#define tr(c,i) for(typeof(c).begin() i = c.begin(); i != c.end(); i++)
#define present(c,x) (c.find(x) != c.end())
#define cpresent(c,x) (find(allc,x) != c.end())
#define rep(i,n) for(int i=0;i<(n);++i)
#define ll long long
const double pi=3.14;
using namespace std;

int main()

{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll m,n;
	cin>>n>>m;
	ll a[m];
	ll sum=0;
	rep(i,m) {cin>>a[i];sum=sum+a[i];}
	if(n-sum>=0) cout<<(n-sum);
	else cout<<-1;
	
}

Measured memory_bytes: 3732
#include<bits/stdc++.h>
using namespace std;
#include <stdio.h>
#include <time.h>
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
const int MOD = 1000000007;

int main(){
   int n;   cin >> n;
   int a[n];
   rep(i,n) cin >> a[i];

   int q;   cin >> q;
   int m[q],l[q];
   rep(i,q) cin >> m[i];

   for(int bit=0;bit < (1 << n) ; bit++){
       int sum=0;
       for(int i=0;i<n;i++){
           if(bit & (1 << i)){
               sum+=a[i];
           }

       }
       for(int j=0;j<q;j++){
           if(sum == m[j])l[j]=INF;
       }

   }

   for(int i=0;i<q;i++){
       if(l[i]==INF)cout << "yes" << endl;
       else cout << "no" << endl;
   }
}


Measured memory_bytes: 3104
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        try(Scanner sc = new Scanner(System.in)){
            String line = sc.nextLine();
            String answer = "";
            int length = line.length();
            for (int i=0; i< length; i++){
                char ch = line.charAt(i);
                if(Character.isLowerCase(ch)){
                    ch = Character.toUpperCase(ch);
                }else{
                    ch =Character.toLowerCase(ch);
                }
                answer = answer + ch;
            }
            System.out.println(answer);
        }
    }
}


Measured memory_bytes: 31492
#include <stdio.h>

int main(void)
{
  int a,b,c,d;

  scanf("%d %d %d %d", &a, &b, &c, &d);
  if(a*b > c*d) {
    printf("%d\n", a*b);
  } else {
    printf("%d\n", c*d);
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

#define debug(x) cout << #x << ": " << x << endl;
#define ll long long
#define mod 1000000007

#define COMMENT

const int N = 2000099;
ll fact[N];
ll finv[N];
ll inv[N];

void inverse_modulao() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for(int i = 2;i < N;i++) {
    fact[i] = fact[i-1]*i%mod;
    inv[i] = mod-mod/i*inv[mod%i]%mod;
    finv[i] = finv[i-1]*inv[i]%mod;
  }
}

ll nCr(int n, int r) {
  return fact[n]*finv[r]%mod*finv[n-r]%mod;
}

int main() {

//  freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);

  inverse_modulao();
  int A[10];
  for(int i = 0;i < 4;i++) {
    cin >> A[i];
  }

  ll ans = nCr(A[0]+A[1], A[0]);

  for(int i = A[0]+1;i <= A[2];i++) {
    ans = (ans + nCr(A[3]+i, i)) % mod;
  }

  for(int i = A[1]+1;i <= A[3];i++) {
    ans = (ans + nCr(A[2]+i, i)) % mod;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 47104
N = int(input())
S = [int(input()) for _ in range(N)]

p = []
for v in S:
    if (v % 10 != 0):
        p.append(v)

if (len(p) == 0):
    print(0)
    exit()

minimum = min(p)
if (sum(S) % 10 != 0):
    print(sum(S))
    exit()

print(sum(S) - minimum)


Measured memory_bytes: 3060
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

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())

def dfs(s):
    if int(s) > N:
        return 0
    if all(s.count(c) > 0 for c in "753"):
        ret = 1
    else:
        ret = 0

    for c in "753":
        ret += dfs(s + c)
    return ret

print(dfs("0"))

Measured memory_bytes: 12708
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<cstdlib>

using namespace std;


int main() {
	int x;
	cin >> x;
	vector<int> sieve(x+1, 1);
	sieve[1] = 0;
	for (int i = 2; i*i <= x; ++i) {
		if (sieve[i]) {
			for (int j = i * i; j <= x; j *= i) {
				sieve[j] = 0;
			}
		}
	}
	auto ret = x;
	while (sieve[ret]) --ret;
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline


def resolve():
    n, q = map(int, input().split())

    to = [[] for _ in range(n)]

    for _ in range(n-1):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    ns = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        ns[p] += x

    visited = [False] * n
    stack = [0]
    while len(stack) > 0:
        num = stack.pop()
        visited[num] = True
        for i in to[num]:
            if visited[i]:
                continue
            ns[i] += ns[num]
            stack.append(i)
    print(*ns)
resolve()

Measured memory_bytes: 93952
let factors : int -> (int * int) list = fun n ->
  let rec loop_i n i =
    if i * i > n then
      if n == 1 then [] else [(n, 1)]
    else if n mod i = 0 then
      let (n', c) = loop_j (n/i) i 1
      in
      (i, c) :: loop_i n' (i + 1)
    else
      loop_i n (i + 1)
  and loop_j n i j =
    if n mod i = 0 then
      loop_j (n / i) i (j + 1)
    else
      (n, j)
  in
  loop_i n 2

let rec print_int_list = function
    [] -> ()
  | (x :: xs) ->
     print_int x;
     print_char ' ';
     print_int_list xs

let rec merge = function
    ([], _) -> []
  | (_, []) -> []
  | ((x, cx)::xs, (y,cy)::ys) ->
     if x = y then
       x :: merge (xs, ys)
     else if x < y then
       merge (xs, (y,cy)::ys)
     else
       merge ((x,cx)::xs, ys)

let () =
  let (a, b) = Scanf.sscanf (input_line stdin) "%d %d" (fun a b -> (a, b)) in
  let facta = factors a in
  let factb = factors b in
  let ans_l  = 1 :: merge (facta, factb) in
  let ans = List.length ans_l
  in
  print_int ans;
  print_newline ()


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
 
int main() {
    
    int h,a;
    cin>>h>>a;

    cout<<(h+a-1)/a<<endl;

 return 0;
}

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

using namespace std;

int main()
{
    // cout<<"Hello World";
    map<int, bool> move_map;
    bool yes = false;
    int h, n;
    cin >> h >> n;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        h -= a;
    }
    if(h > 0){
        cout << "No";
    }else{
        cout << "Yes";
    }
}

Measured memory_bytes: 256
s = input()

if (
  (('N' in s) and ('S' in s) and (not 'W' in s) and (not 'E' in s)) or
  (('W' in s) and ('E' in s) and (not 'N' in s) and (not 'S' in s)) or
  (('N' in s) and ('S' in s) and ('W' in s) and ('E' in s))
):
  print('Yes')
else:
  print('No')


Measured memory_bytes: 9120
#include<bits/stdc++.h>
using namespace std;
     
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long int
#define pb push_back
#define endl "\n"
#define ff first
#define ss second
#define N 100009
#define mod 1000000007
#define med 998244353
#define debug cout<<"There There\n";
#define debug1(x) cout<<"\nValue is "<<x<<endl
#define debug2(x,y) cout<<"\nValue is "<<x<<" "<<y<<endl
#define debug3(x,y,z) cout<<"\nValue is "<<x<<" "<<y<<" "<<z<<endl  
#define pr pair<int,int>
#define mx INT_MAX
#define lmx LONG_MAX
#define err return 0
#define cn continue
#define bre break

int n;
int x,y,z;
vector<int> v[N];
int visited[N];

void dfs(int a,int b)
{
	visited[a]=1;
	for(auto i:v[a])
	{
		if(i==b||(visited[i]==1))
		{
			continue;
		}
		dfs(i,a);
	}
}

int32_t main()
{
	int m;
	IOS;
	cin>>n;
	memset(visited,0,sizeof(visited));
	cin>>m;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y>>z;
		x--,y--;
		v[x].pb(y);
		v[y].pb(x);
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(visited[i]==0)
		{
			dfs(i,-1);
			ans++;
		}
	}	
	cout<<ans<<endl;
}	


Measured memory_bytes: 11136
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string S;
    cin >> S;

    for (int i = 0; i < (int)S.size(); i++) {
        if (S[i] == '1')
            cout << '9';
        else if (S[i] == '9')
            cout << '1';
        else
            cout << S[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
s_list = []
t_list = []
for i in range(N):
    s, t = map(str, input().split())
    t = int(t)
    s_list.append(s)
    t_list.append(t)

X = str(input())
X_index = s_list.index(X) + 1

result = 0
for i in range(X_index, N):
    result += t_list[i]

print(result)


Measured memory_bytes: 3060
/* ***************************************
Author        :Scau.ion
Created Time  :2016/09/11 19:56:38 UTC+8
File Name     :ion.cpp
*************************************** */

#include <bits/stdc++.h>

#define LL long long
#define ULL unsigned long long
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<PII>
#define X first
#define Y second
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define IN freopen("in", "r", stdin);
#define OUT freopen("out", "w", stdout);

using namespace std;

char s[20];
int a[20];
int n;
LL ans;

void dfs(int seat,LL sum,LL add)
{
    if (seat==n) ans+=sum+add;
    else
    {
        dfs(seat+1,sum+add,a[seat]);
        dfs(seat+1,sum,add*10+a[seat]);
    }
    return;
}

int main()
{
	scanf("%s",s);
    n=strlen(s);
    for (int j=0;j<n;++j)
        a[j]=s[j]-'0';
    ans=0;
    dfs(1,0,a[0]);
    cout<<ans<<endl;
	return 0;
}


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

int main(){

    int A, B, C, D, E, F; cin >> A >> B >> C >> D >> E >> F; 

    double v = 0;
    int ans1, ans2;

    for(int i = 0; 100 * A * i <= F; i++){
        for(int j = 0; 100 * A * i + 100 * j * B <= F; j++){
            for(int k = 0; 100 * A * i + 100 * j * B + C * k <= F; k++){
                for(int l = 0; 100 * A * i + 100 * j * B + C * k + D * l <= F; l++){


                    //if(x + y == 0) continue;

                    int x = 100*A*i + 100*B*j;
                    int y = C*k + D*l;
                    if(100*y > E*x) continue;

                    if(x + y == 0) continue;
                    
                    double _v = (double)(100 * y) / (x + y);
                    //cout << x << " " << y << " " << v << " " << _v << endl; 
                    if(v <= _v){
                        v = _v;
                        ans1 = x + y;
                        ans2 = y;                         
                    }
                }
            }
        }
    }

    cout << ans1 << " " << ans2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
const ll INF = ll(1e18)+1;


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

int n; ll k;
cin >> n >> k;
vl a(n);
rep(i,n) cin >> a[i];
sort(all(a));

ll l = -INF, r = INF;
while(r - l > 1) {
    ll mid = (l+r)/2;
    bool ok = [&]{
        ll cnt = 0;
        rep(i,n) {
            if(a[i] >= 0) {
                int l = -1, r = n;
                while(r - l > 1) {
                    int c = (l+r)/2;
                    if(a[i]*a[c] < mid) l = c; else r = c;
                }
                cnt += r;
            }
            else {
                int l = -1, r = n;
                while(r - l > 1) {
                    int c = (l+r)/2;
                    if(a[i]*a[c] < mid) r = c; else l = c;
                }
                cnt += n-r;
            }
            if(a[i]*a[i] < mid) cnt--;
        }
        cnt /= 2;
        return cnt < k;
    }();
    if(ok) l = mid; else r = mid;
}

cout << l << endl;
return 0;
}

Measured memory_bytes: 1792
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
n,m = LI()
v = LIR(m)
p2 = [1]
for i in range(n):
    p2.append(p2[-1]*2)
dp = [[0 for i in range(p2[n])] for j in range(n)]
dp[0][1] = 1
for i in range(1,p2[n]):
    for k in range(n):
        for a,b in v:
            a -= 1
            b -= 1
            if k==a or k == b:
                c = p2[a]
                d = p2[b]
                if i&c and not i&d:
                    dp[b][i|d] += dp[k][i]
                if (not i&c) and i&d:
                    dp[a][i|c] += dp[k][i]
ans = 0
for i in range(1,n):
    ans += dp[i][-1]
print(ans)
"""

#D
n,p,q = LI()
v = [None for j in range(n)]
sa = 0
sb = 0
for i in range(n):
    a,b,c = LI()
    v[i] = [a,b,c]
    sa += a
    sb += b
dp = [[[float("inf") for i in range(sb+1)] for j in range(sa+1)] for k in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for a in range(sa):
        for b in range(sb):
            ai,bi,ci = v[i]
            if a + ai <= sa and b + bi <= sb:
                dp[i+1][a+ai][b+bi] = min(dp[i+1][a+ai][b+bi],dp[i][a][b]+ci,dp[i][a+ai][b+bi])
            dp[i+1][a][b] = min(dp[i+1][a][b],dp[i][a][b])
li = [[p,q]]
while li[-1][0] <= sa and li[-1][1] <= sb:
    li.append([li[-1][0]+p,li[-1][1]+q])
li.pop(-1)
ans = float("inf")
for a,b in li:
    ans = min(ans,dp[n][a][b])
if ans == float("inf"):
    print(-1)
else:
    print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 116316
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
if sum(a)<sum(b):
    print(-1)
else:
    s=0
    k=[]
    m=0
    for i in range(n):
        d=a[i]-b[i]
        if d>=0:
            k.append(d)
        else:
            m+=d
            s+=1
    k.sort(reverse=True)
    j=0
    while m<0:
        m+=k[j]
        s+=1
        j+=1
    print(s)

Measured memory_bytes: 18708
import sys
A = list(input())
B = list(input())
C = list(input())
A = A[::-1]
B = B[::-1]
C = C[::-1]
X = 0
while True:
    if X == 0:
        if A:
            S = A.pop()
            if S == 'a':
                X = 0
            elif S == 'b':
                X = 1
            else:
                X = 2
        else:
            print('A')
            sys.exit()
    elif X == 1:
        if B:
            S = B.pop()
            if S == 'a':
                X = 0
            elif S == 'b':
                X = 1
            else:
                X = 2
        else:
            print('B')
            sys.exit()
    else:
        if C:
            S = C.pop()
            if S == 'a':
                X = 0
            elif S == 'b':
                X = 1
            else:
                X = 2
        else:
            print('C')
            sys.exit()

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

int main() {
  int A,B,N,K;
  cin >>N;
  double ans;
  vector<long long>a(N),b(N);
 for(int i=0;i<N;i++){
   cin>>a[i];
 }
  b[0]=0;
  b[1]=abs(a[1]-a[0]);
  for(int i=2;i<N;i++){
    b[i]=min(b[i-1]+abs(a[i]-a[i-1]),b[i-2]+abs(a[i]-a[i-2]));
  }
  cout <<b[N-1]<< endl;
}


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

int main(){
	int n;
	while(cin>>n,n){
		int day[32][51]={0};
		int map[51][51]={0};
		int M=0;
		for(int i=1;i<=n;i++)map[i][0]=1,map[i][i]=1;
		for(int i=1,num,tmp;i<=n;i++){
			for(cin>>num;num>0;num--){
				cin>>tmp;
				day[tmp][i]=1;
			}
		}
		for(int i=1,flag=0;i<=31;i++){
			if(i==31)cout<<-1<<endl;
			else{
				int data[51]={0};
				for(int j=1;j<=n;j++){
					if(day[i][j]){
						for(int k=1;k<=n;k++)if(map[j][k])data[k]=1;
					}
				}
				for(int j=1;j<=n;j++){
					if(day[i][j]){
						for(int k=1;k<=n;k++)if(data[k])map[j][k]=1;
					}
				}
				for(int j=1;j<=n;j++)if(data[j])data[0]++;
				if(data[0]==n)flag=1;
			}
			if(flag)cout<<i<<endl;
			if(flag)break;
		}
	}
	return 0;
}


Measured memory_bytes: 1184
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main(){
 char b;
 cin >> b;
 if (b == 'A'){
   cout << "T\n";
 }
 if (b == 'T'){
   cout << "A\n";
 }
   if (b == 'C'){
   cout << "G\n";
 }
 if (b == 'G'){
   cout << "C\n";
 }
  return 0; 
}

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;

int main(int argc, char const *argv[])
{
    int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
    int x3 = x2 - (y2 - y1);
    int y3 = y2 + (x2 - x1);
    int x4 = x3 - (y3 - y2);
    int y4 = y3 + (x3 - x2);
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
#define ull unsigned long long
#define vii vector <int>
#define pii pair <int, int>
#define fi first
#define se second
#define rep(i,a,n)		for(int i=a;i<n;i++)
#define endl '\n'
#define mem(a,b) memset(a, b, sizeof a)
#define mod 1000000007LL;
#define mkp make_pair
#define pb push_back
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
using namespace std;
double pi=3.1415926535;
double eps=0.000001;

void print(vector <int> &arr){
	for(int i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	
	cout<<endl;
}


int32_t main(){
/////////////////////////////////////////////////////////////////////
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cerr.tie(NULL);
//For fast IO
///////////////////////////////////////////////////////////////////// 
//	std::cout.unsetf ( std::ios::floatfield );  // floatfield not set
//    std::cout.precision(10);
	int n;
	cin>>n;
	int arr[n][3];
	rep(i,0,n) cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
	int dp[n+1][3];
	dp[0][0]=0;
	dp[0][1]=0;
	dp[0][2]=0;
	rep(i,1,n+1){
		dp[i][0]=max(dp[i-1][1]+arr[i-1][1], dp[i-1][2]+arr[i-1][2]);
		dp[i][1]=max(dp[i-1][0]+arr[i-1][0], dp[i-1][2]+arr[i-1][2]);
		dp[i][2]=max(dp[i-1][1]+arr[i-1][1], dp[i-1][0]+arr[i-1][0]);
	}
//	rep(i,0,n+1){
//		cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
//	}
	cout<<max3(dp[n][0], dp[n][1], dp[n][2])<<endl;
	return 0;
	}
	


Measured memory_bytes: 4992
def solve(d, K):
  r = 1
  for k in range(K,1,-2):
    if d >= 10**k:
      return 0
    t = (-d)%10
    d = abs((d-t*(10**(k-1)-1))//10)
    r *= 10-t-(K==k)
  return r*(10**(K%2)) if d == 0 else 0

D = int(input())
result = 0
l = len(str(D))
for k in range(l,2*l+1):
  result += solve(D, k)

print(result)

Measured memory_bytes: 3064
/*
Thank you for helping me out Endagorion
You have really been an inspiration
I will prove my worth to you
i will return in APRIL

"May God help me in this venture of mine"

*/


#include <iostream>
#include <sstream>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
// #include <multiset>
#include <cstring>
#include <queue>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>

using namespace std;

#define endl '\n'
#define lli long long int
#define USE_MATH_DEFINES
const long INF = 100000;

// int dr[]={0,0,1,-1};
int countt[1010101];
// int dc[]={1,-1,0,0};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	#ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	#endif
	
	int n,l;
	cin>>n>>l;
	multiset<string> s;
	for(int i=0;i<n;i++)
	{
		string temp;
		cin>>temp;
		// sort(&temp[0],&temp[temp.length()-1]);
		s.insert(temp);
	}
	for(multiset<string>::iterator it = s.begin();it!=s.end();it++)
	{
		string temp = *it;
		cout<<temp;
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,k=0,a[25],max=0,d=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int j=1;j<n;j++)
	{
		int i;
		for(i=0;i<j;i++)
		{
			if(a[i]<=a[j])
		{
			k++;
		}
	    }
		if(k==i)
		{
			d++;
			k=0;
		}
		else k=0;
		
	}
	printf("%d",d+1);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define x first
#define y second
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ve vector
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define pb push_back
#define sz(a) (int)(a.size())
//using namespace __gnu_pbds;
using namespace std;

// // // functions: find_by_order  & order_of_key
// typedef tree<
// int,
// null_type,
// less<int>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

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

const int inf=(int)2e9;
const long long mod=1000000007; //1E9+7
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

ll powmod(ll a,ll p){
	ll ans=1;
	while(p){
		if(p&1) ans*=a;
		p/=2;a*=a; ans%=mod;a%=mod;
	}
	return ans;
}
ll mdinv(ll a){return powmod(a,mod-2); }

const int N=3e3+2;
int DP[N][N];
int v[N];
int p[N];

int sol(int l,int r){
	if(l>r) return 0;
	if(l==r) return v[l];
	if(DP[l][r]!=-1) return DP[l][r];
	int a=v[l]-sol(l+1,r)+p[r]-p[l];
	int b=v[r]-sol(l,r-1)+p[r-1]-p[l-1];
	return DP[l][r]=max(a,b);
}

signed main(){
	IOS
	memset(DP,-1,sizeof(DP));
	int n;cin>>n;
	forn(i,n){
		cin>>v[i+1];
		p[i+1]=p[i]+v[i+1];
	}
	int my=sol(1,n);
	int his=p[n]-my;
	cout<<my-his;
}


Measured memory_bytes: 70912
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 0; i < 50000; i++){
        if(i * i <= N){
            ans = i;
        }
        else{
            break;
        }
    }
    cout << ans * ans << endl;
}


Measured memory_bytes: 256
from itertools import permutations
def main():
    n=int(input())
    pp=tuple(map(int,input().split()))
    qq=tuple(map(int,input().split()))
    res=[]
    for i, p in enumerate(permutations(list(range(1,n+1)))):
        if pp == p: 
            res.append(i+1)
        if qq == p:
            res.append(i+1)
        if len(res) == 2:
            print(abs(res[1]-res[0]))
            return

main()

Measured memory_bytes: 3060
#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,a[maxn],b[maxn];
int main(){
    read(n);
    for (int i=1;i<=n;i++) b[i]=read(a[i]);
    int cnt=0,ans;
    for (int i=1;i<n;i++){
        if (a[i]==i) swap(a[i],a[i+1]),cnt++;
    }
    if (a[n]==n) cnt++;
    ans=cnt;
    cnt=0;
    for (int i=n;i>1;i--){
        if (b[i]==i) swap(b[i],b[i-1]),cnt++;
    }
    if (b[1]==1) cnt++;
    ans=min(ans,cnt);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<math.h>
using namespace std;

void a()
{
    string s,t;
    cin >> s >> t;
    if (t.substr(0,t.length()-1)==s)
    cout << "Yes";
    else cout << "No"; 

    return;
}
void b()
{
    int a,b,c,k;
    cin >>a >> b >> c >> k;
    if(a>k)cout <<k;
    else{
        if(a+b>=k)cout <<a;
        else cout << 2*a+b-k;
    }
    return;
}
void c()
{
    return;
}
void d()
{
    return;
}
void e()
{
    return;
}
void f()
{
    return;
}
int main(void){
    //a();
    b();
    //c();
    //d();
    //e();
    //f();

    return 0;
}

Measured memory_bytes: 3624
while True:
	a,b,c,d,e = map(int,raw_input().split())
	if a==0:
		break
	na,nb,nc = map(int,raw_input().split())
	t=na+nb+nc
	ans=na*a+nb*b+nc*c
	if t < d:
		if ans > d*e:
			ans=d*e
	else:
		tmp = 0
		dd=d
		cnt=0
		if dd>=nc:
			cnt+=nc*c
			dd-=nc
		else:
			cnt+=dd*c
			dd=0

		if dd>=nb:
			cnt+=nb*b
			dd-=nb
		else:
			cnt+=dd*b
			dd=0

		if dd>=na:
			cnt+=na*a
			dd-=na
		else:
			cnt+=dd*a
			dd=0
		
		if cnt >= d*e:
			if e<a:
				a=e
			if e<b:
				b=e
			if e<c:
				c=e
			dd=d
			cnt=0
			# print "cnt"
			if dd>=nc:
				cnt+=nc*e
				dd-=nc
			else:
				cnt+=dd*e
				cnt+=(nc-dd)*min(e,c)
				dd=0
			# print cnt
			if dd>=nb:
				cnt+=nb*e
				dd-=nb
			else:
				cnt+=dd*e
				cnt+=(nb-dd)*min(e,b)
				dd=0
# 70 100 340 4 200
# 1 1 2
			# print cnt
			if dd>=na:
				cnt+=na*e
				dd-=na
			else:
				cnt+=dd*e
				cnt+=(na-dd)*min(e,a)
				dd=0
			ans=cnt

	print ans

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

vector<int> pre_kmp(string pat) {
	int k;
	vector<int> table((int)pat.size() + 1);
	table[0] = -1;

	for (int i = 1; i <= pat.size(); ++i) {
		k = table[i-1];

		while (k >= 0) {
			if (pat[k] == pat[i-1]) break;
			else k = table[k];
		}

		table[i] = k + 1;
	}

	return table;
}

int main() {
	string s; cin >> s;
	int n = s.size();
	string t = s; reverse(ALL(t));
	vi vp = pre_kmp(s), vq = pre_kmp(t);

	int M = n - vp[n];

	if (M == 1) {
		cout << n << endl;
		cout << 1 << endl;
	} else if (M == n || n % M != 0) {
		cout << 1 << endl;
		cout << 1 << endl;
	} else {
		int ans = 0;
		for (int i = 0; i < n-1; ++i) {
			int c = i + 1 - vp[i+1], d = n - i - 1 - vq[n-i-1];
			if ((c == i + 1 || (i + 1) % c != 0) && (d == n - i - 1 || (n - i - 1) % d != 0)) {
				++ans;
			} 
		}
		cout << 2 << endl;
		cout << ans << endl;
	}

	return 0;
}

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

int main()
{
  int A, B;
  string Ans="No";
  cin >> A >> B;
  string S=to_string(A)+to_string(B);
  int C=stoi(S);
  rep(i,317){
    if(i*i==C){
      Ans="Yes";
      break;
    }
  }
  cout << Ans << endl;
} 

Measured memory_bytes: 256
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func readInt() (read int) {
	scanner.Scan()
	read, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return
}

func main() {
	scanner.Split(bufio.ScanWords)

	MOD := 998244353
	n := readInt()
	s := readInt()
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, s+1)
	}

	A := make([]int, n)
	for i := 0; i < n; i++ {
		A[i] = readInt()
	}

	dp[0][0] = 1
	for i := 0; i < n; i++ {
		for j := 0; j < s+1; j++ {
			dp[i+1][j] += (2 * dp[i][j] % MOD)
			dp[i+1][j] %= MOD
			if j+A[i] <= s {
				dp[i+1][j+A[i]] += (dp[i][j] % MOD)
				dp[i+1][j+A[i]] %= MOD
			}
		}
	}

	fmt.Println(dp[n][s])
}


Measured memory_bytes: 76872
import sys
from math import sqrt, floor

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def main():
    a, b, n = MI()

    if b - 1 <= n:
        print((a * (b - 1)) // b - (a * ((b - 1) // b)))
    else:
        print((a * n) // b - (a * (n // b)))


if __name__ == "__main__":
    main()


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

const int MAX_N = 100000 + 10;
int A[MAX_N];
vector<int> g[MAX_N];
bool ans;

ll f(int v, int p) {
  if (!ans) return 0;
  ll T = 0;
  if (g[v].size() == 1 && p == -1) {
    ll ci = f(g[v][0], v);
    if (A[v] != ci) { ans = false; }
    return 0;
  } else if (g[v].size() == 1 && p != -1) {
    T = A[v];
  } else {
    ll L = 0;
    vector<ll> c;
    for (int u : g[v]) if (u != p) {
      ll ci = f(u, v);
      L += ci;
      c.push_back(ci);
    }
    T = 2 * A[v] - L;
    if (T < 0 || T > A[v]) { ans = false; }
    if ((L - T) % 2 != 0) { ans = false; }
    if ((L - T) < 0) { ans = false; }
    ll P = (L - T) / 2;
    ll Q = L/2;
    REP(i, c.size()) {
      Q = min(Q, L-c[i]);
    }
    // if (ans) {
      // cout << "v=" << v << ", Q=" << Q << ", p=" << P << endl;
    // }
    if (Q < P) { ans = false; }
  }
  if (p == -1) {
    if (T != 0) { ans = false; }
  }
  return T;
}

int main2() {
  REP(i, MAX_N) g[i].clear();
  int N;
  scanf("%d", &N);
  REP(i, N) {
    scanf("%d", &A[i]);
  }
  REP(i, N-1) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  ans = true;
  f(0, -1);
  cout << (ans ? "YES":"NO") << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}

Measured memory_bytes: 15488
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> v(n + 1);
  for (int i = 0; i < n; i++) {
    v[i + 1] = v[i];
    if (s[i] == '#') {
      v[i + 1]++;
    }
  }
  int ans = n;
  for (int i = 0; i <= n; i++) {
    ans = min(ans, v[i] + (n - i - v[n] + v[i]));
  }
  cout << ans << endl;

  return 0;
}


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

const int inf=0x3f3f3f3f;
const int maxn=2005;
typedef long long LL;
int n, z, w;
int data[maxn];

int main(){
    while(~scanf("%d%d%d", &n, &z, &w)){
        for(int i=1;i<=n;i++)scanf("%d", &data[i]);
        data[0]=data[1];
        printf("%d\n", max(abs(w-data[n]), abs(data[n]-data[n-1])));
    }
    return 0;
}


Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn main() {
    let nk: Vec<usize> = read_vec();
    let n = nk[0];
    let k = nk[1] as u64;
    let mut a: Vec<u64> = read_vec();
    let mut b: Vec<u64> = vec![0; n];

    for i in 0..n {
        let mut cnt: u64 = 0;
        let tmp: u64 = a[i];
        for j in (i + 1)..n {
            if tmp > a[j] {
                cnt += 1;
            }
        }
        b[i] = cnt;
    }

    let mut b_sum: u64 = 0;

    for tmp in b {
        b_sum = (b_sum + tmp) % 1000000007;
    }

    a.sort();

    let mut c_sum: u64 = 0;

    let mut tmp = a[0];
    let mut cnt: u64 = 0;
    for i in 1..n {
        if tmp != a[i] {
            tmp = a[i];
            cnt = i as u64;
        }
        c_sum = (c_sum + cnt) % 1000000007;
    }

    let tmp1 = (k * b_sum) % 1000000007;
    let tmp2 = ((((k * (k - 1)) / 2) % 1000000007) * c_sum) % 1000000007;
    let ans = (tmp1 + tmp2) % 1000000007;
    println!("{}", ans);
}


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

#define mod 1000000007
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, x = 1, y = 1, z = 1;
    cin >> n;

    for (int i = 0; i < n; i++) {
        z = (z*8)%mod;
        y = (y*9)%mod;
        x = (x*10)%mod;
    }
    y = (y*2) % mod;
    cout << (x-y+z+mod)%mod;
}

Measured memory_bytes: 3504
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
#define MOD 10000
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const ull B=100000007;
const int INF=1e9;
int main(){
      std::ios::sync_with_stdio(false);
      std::cin.tie(0);
      int n,m;
      cin>>n>>m;
      int ans=m,now=m;
      REP(i,n){
            int a,b;
            cin>>a>>b;
            now+=a-b;
            if(now<0){
                  cout<<0<<endl;
                  return 0;
            }
            ans=max(ans,now);
      }
      cout<<ans<<endl;
}

Measured memory_bytes: 1196
#include<iostream>

using namespace std;

int K, X;

const int P_MAX = 1000000;
const int M_MAX = -1000000;

int main() {
    cin >> K >> X;
    
    int max_p = P_MAX;
    int min_p = M_MAX;

    if (X+K-1 >= P_MAX) {
        max_p = P_MAX;
    } else {
        max_p = X+K-1;
    }

    if (X-K+1 <= M_MAX) {
        min_p = M_MAX;
    } else {
        min_p = X-K+1;
    }

    for (int i = min_p; i <= max_p; i++) {
        if(i==max_p) {
            cout << i << endl;
        } else {
            cout << i << ' ';
        }
    }
}

Measured memory_bytes: 256