akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x7f
#define MAX_INF_VAL 0x7f7f7f7f
#define pi 3.141592653589
#define eps 1e-10
//#define p 2173412051LL
#define sz 2

using namespace std;

int main() {
	int n, k, s;
	scanf( "%d%d%d", &n, &k, &s );
	for( int i = 0; i < k; ++i )
		printf( "%d ", s );
	for( int i = k; i < n; ++i )
		if( s == 1000000000 )
			printf( "%d ", 1 );
		else
			printf( "%d ", 1000000000 );
	return 0;
}

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

int req(int N,int now,vector<bool> passed,vector<int> num,vector<vector<bool>> mp) {
  if (now == N) {
    for (int i=0; i<N-1; i++) {
      if (!mp[num[i]][num[i+1]]) {
        break;
      }
      if (i==N-2) {
        return 1;
      }
    }
    return 0;
  }
  int ans = 0;
  for (int i=1; i<N; i++) {
    if (passed[i]) {
      continue;
    }
    num[now] = i;
    passed[i] = true;
    ans += req(N,now+1,passed,num,mp);
    passed[i] = false;
  }
  return ans;
}

int main() {
  int N,M,A,B;
  cin >> N >> M;
  vector<vector<bool>> mp(N,vector<bool> (N,false));
  
  for (int i=0; i<M; i++) {
    cin >> A >> B;
    mp[A-1][B-1] = true;
    mp[B-1][A-1] = true;
  }
  
  vector<bool> passed(N,false);
  passed[0] = true;
  vector<int> num(N,0);
  
  cout << req(N,1,passed,num,mp) << endl;
  
  return 0;
}

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

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


using namespace std;


void check( int val ){
	
	cout << val << endl;
}

long long pow(int km , int nm){

	long long to = 1;
	for(int i = 0 ; i < nm ; i++){

		to *= km;
	}

	return to;
}

int main( int argc , char ** argv ){
	
	int N , K;
	cin >> N >> K;

	cout << pow(K-1 , N-1)*K << endl;


}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static int N, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());
        int[] S = new int[M];
        int[] C = new int[M];
        for(int i = 0; i < M; i++) {
            S[i] = Integer.parseInt(sc.next());
            C[i] = Integer.parseInt(sc.next());
        }

        for(int i = 0; i < 1000; i++) {
            if(ok(Integer.toString(i), S, C)) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }
    static boolean ok(String str, int[] s, int[] c) {
    	if(str.length() != N) return false;
        for(int i = 0; i < M; i++) {
            if(str.charAt(s[i] - 1) != c[i] + '0') return false;
        }
        return true;
    }
}


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

int main()
{
  int n;
  cin >> n;
  
  double s;
  s = 0;
  
  double x;
  string u;
  
  for(int i=0; i<n; i++){
    cin >> x >> u;
    if(u == "JPY")
      s += x;
    else if(u == "BTC")
      s += x*380000.0;
  }
  
  cout << s;
    
  return 0;
}

Measured memory_bytes: 256
a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
x=[int(input()) for _ in range(q)]
s.append(1<<64)
t.append(1<<64)
import bisect
for i in range(q):
    sl=s[bisect.bisect_left(s,x[i])-1]
    sr=s[bisect.bisect_left(s,x[i])]
    tl=t[bisect.bisect_left(t,x[i])-1]
    tr=t[bisect.bisect_left(t,x[i])]
    #print(sl,sr,tl,tr)
    z=[max(abs(x[i]-sl),abs(x[i]-tl)),
       max(abs(sr-x[i]),abs(tr-x[i])),
       abs(x[i]-sl)*2+abs(tr-x[i]),
       abs(x[i]-tl)*2+abs(sr-x[i]),
       abs(tr-x[i])*2+abs(x[i]-sl),
       abs(sr-x[i])*2+abs(x[i]-tl),]
    #print(z)
    print(min(z))

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

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

    int n;
    cin >> n;
    int* a = new int[n];
    vector<pair<int, int>> ps;

    rep(i, n)
    {
        cin >> a[i];
        ps.push_back(pair<int,int>(a[i], i));
    }
    sort(ps.begin(), ps.end());
    rep(i, n)
    {
        cout << (ps[i].second + 1) << " ";
    }
    cout << endl;

    return 0;
}

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

int main() {
	int H=0,W=0;
	while(1)
	{
		cin>>H>>W;
		if(H==0 && W==0)break;
		for(int i=1;i<=H;i++)
		{
			for(int j=1;j<=W;j++)
			{
			cout<<"#";
			}
			cout<<endl;
		}
		cout<<endl;
	}
	return 0;
}




Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define debug(x) cerr << #x << ": " << x << '\n'

int main() {
    int A[3][3];
    rep(i, 3) rep(j, 3) cin >> A[i][j];
    int N;
    cin >> N;
    int b;
    rep(n, N) {
        cin >> b;
        rep(i, 3) {
            rep(j, 3) {
                if(A[i][j] == b) {
                    A[i][j] = -1;
                }
            }
        }
    }
    if (A[0][0] == A[1][1] && A[1][1] == A[2][2]) {
        cout << "Yes" << endl;
        return 0;
    } else if (A[0][2] == A[1][1] && A[2][0]) {
        cout << "Yes" << endl;
        return 0;
    }
    rep(i, 3) {
        if(A[i][0] == A[i][1] && A[i][1] == A[i][2]) {
            cout << "Yes" << endl;
            return 0;
        }
        if(A[0][i] == A[1][i] && A[1][i] == A[2][i]) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())
S = input()
S += S[0]

def roop(St):
    for i in range(1,N+1):
        flag = 1
        if S[i] == 'x':
            flag *= -1
        if St[i] == 'W':
            flag *= -1
        if St[i-1] == 'W':
            flag *= -1
        if flag == 1:
            St += 'S'
        else:
            St += 'W'
    return St
ans = '-1'
candidate = ('SS','WS','SW','WW')
for i in candidate:
    a = roop(i)
    if a[0] == a[-2] and a[1] == a[-1] :
        ans = a[0:N]
        break
print(ans)

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void){
  string in;
  cin >> in;

  string cor = "CODEFESTIVAL2016";
  int ans = 0;
  for(int i=0;i<in.size();i++){
    if(in[i] != cor[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        m = input()
        for i in range(m):
            s = raw_input()
            count = set()
            for i in range(1, len(s)):
                l = s[:i]
                r = s[i:]
                count.add(l + r)
                count.add(l + r[::-1])
                count.add(l[::-1] + r)
                count.add(l[::-1] + r[::-1])
                count.add(r + l)
                count.add(r + l[::-1])
                count.add(r[::-1] + l)
                count.add(r[::-1] + l[::-1])
            print len(count)
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Measured memory_bytes: 4752
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    int M = sc.nextInt();
    int C = sc.nextInt();
    int[][] A = new int[N][M];
    int[] B = new int[M];

    for (int i = 0; i < M; i++) {
      B[i] = sc.nextInt();
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        A[i][j] = sc.nextInt();
      }
    }

    sc.close();

    int count = 0;

    for (int i = 0; i < N; i++) {
      int sum = C;
      for (int j = 0; j < M; j++) {
        sum += A[i][j] * B[j]; 
      }
      if (0 < sum) {
        count++;
      }
    }
    

    System.out.println(count);

  }

}

Measured memory_bytes: 23764
// 1_6_A

#include <iostream>
using namespace std;

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

Measured memory_bytes: 3088
S = input()
a=int(S[:2])
b=int(S[2:])
if (1<=a and a<=12):   
    if (1<=b and b<=12):
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if (1<=b and b<=12):
        print("YYMM")
    else:
        print("NA")

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;

int main() {

	int64_t A, B, C, X, Y;
	cin >> A >> B >> C >> X >> Y;

	int64_t ans = A*X+B*Y+C*2*(X+Y);

		for (int i = 0;i <= X;i++) {
			if (Y - X + i > 0)
				ans = min(ans, A * i + B * (Y - X + i) + C * 2 * (X - i));

			else
				ans = min(ans, A * i + C * 2 * (X - i));
		}
	

		for (int i = 0;i <= Y;i++) {
			if (X - Y + i > 0)
				ans = min(ans, A * (X - Y + i) + B * i + C * 2 * (Y - i));

			else
				ans = min(ans, B * i + C * 2 * (Y - i));
		}

	cout << ans;


	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())

const int INF = 1 << 30;
struct graph {
  int n;
  struct edge {
    int src, dst;
    int capacity, residue;
    size_t rev;
  };
  edge &rev(edge e) { return adj[e.dst][e.rev]; };

  vector<vector<edge>> adj;
  graph(int n) : n(n), adj(n) { }
  void add_edge(int src, int dst, int capacity) {
    adj[src].push_back({src, dst, capacity, 0, adj[dst].size()});
    adj[dst].push_back({dst, src, 0, 0, adj[src].size()-1});
  }
  int max_flow(int s, int t) {
    for (int u = 0; u < n; ++u)
      for (auto &e: adj[u]) e.residue = e.capacity;
    int total = 0;
    while (1) {
      vector<int> prev(n, -1); prev[s] = -2;
      queue<int> que; que.push(s);
      while (!que.empty() && prev[t] == -1) {
        int u = que.front(); que.pop();
        for (edge &e: adj[u]) {
          if (prev[e.dst] == -1 && e.residue > 0) {
            prev[e.dst] = e.rev;
            que.push(e.dst);
          }
        }
      }
      if (prev[t] == -1) break;
      int inc = INF;
      for (int u = t; u != s; u = adj[u][prev[u]].dst) 
        inc = min(inc, rev(adj[u][prev[u]]).residue);
      for (int u = t; u != s; u = adj[u][prev[u]].dst) {
        adj[u][prev[u]].residue += inc;
        rev(adj[u][prev[u]]).residue -= inc;
      }
      total += inc;
    } // { u : visited[u] == true } is s-side
    return total;
  }
};

int main() {
  for (int n, m; scanf("%d %d", &n, &m) == 2; ) {
    graph g(n);
    for (int i = 0; i < m; ++i) {
      int u, v, w;
      scanf("%d %d %d", &u, &v, &w);
      g.add_edge(u, v, w);
    }
    printf("%d\n", g.max_flow(0, n-1));
  }
}

Measured memory_bytes: 3332
import java.util.Scanner;

public class Main {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    int a = Integer.parseInt(sc.next());
    int b = Integer.parseInt(sc.next());
    
    int c = a + b;
    
    if (c % 2 == 0) {
      System.out.println(c / 2);
    } else {
      System.out.println(c / 2 + 1);
    }
  }
}

Measured memory_bytes: 21844
#include <iostream>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <iterator>

using namespace std;
int main()
{
    int n, m, tmp;
    set<int> a, b, result;
    cin >> n;
    for (int i=0; i<n; ++i){
        cin >> tmp;
        a.insert(tmp);
    }
    cin >> m;
    for (int i=0; i<m; ++i){
        cin >> tmp;
        b.insert(tmp);
    }
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(result, result.end()));
    for (auto itr=result.begin(); itr != result.end(); ++itr){
        cout << *itr << endl;
    }
}


Measured memory_bytes: 23720
#include<stdio.h>
int main(void){
	char a[1];
	scanf("%s",a);
	if(a[0]=='A'){
		printf("T");
	}
	else if(a[0]=='T'){
		printf("A");
	}
	else if(a[0]=='G'){
		printf("C");
	}
	else if(a[0]=='C'){
		printf("G");
	}
return 0;
}

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

int prime[50001];
bool is_prime[50001];

int res(int n)
{
	int p=0;
	for(int i=0;i<n+1;i++){
		is_prime[i] = true;
	}
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<n+1;i++){
		if(is_prime[i]){
			prime[p++] = i;
			for(int j=2*i;j<n+1;j+=i){
				is_prime[j] = false;
			}
		}
	}
	return p;
}
int binsearch(int key,int left,int right)
{
	while(left<=right){
		int middle = (left+right)/2;
		if(key == prime[middle])
			return 1;
		else if(key<prime[middle])
			right = middle-1;
		else
			left = middle+1;
	}
	return 0;
}
int main()
{
	int n;
	int count;
	int p = res(50000);
	while(cin >> n){
		if(n==0)
			break;
		count = 0;
		for(int i=0;i<p;i++){
			if(prime[i] < n/2+1)
				count+=binsearch(n-prime[i],i,p);
			else
				break;
		}
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 936
#include<stdio.h>
int main()
{
    int A, B;
    scanf("%d %d ", &A, &B);
    if(A==1 && B==2)
    {
        printf("3\n");
    }
    else if(A==1 && B==3)
    {
        printf("2\n");
    }
    else if(A==2 && B==1)
    {
        printf("3\n");
    }
    else if(A==2 && B==3)
    {
        printf("1\n");
    }
    else if(A==3 && B==1)
    {
        printf("2\n");
    }
    else if(A==3 && B==2)
    {
        printf("1\n");
    }
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static ConsoleApp.Util;
using static System.Math;

namespace ConsoleApp
{
    class Program
    {
       
        static void Main(string[] args)
        {
            var input = ReadLine().Split();
            var s = input[0];
            var t = input[1];
            var arr = ReadLine().Split().Select(int.Parse).ToArray();
            int a = arr[0];
            int b = arr[1];

            var u = ReadLine();
            if(u == s){
                a--;
            }
            else{
                b--;
            }
            WriteLine(a + " "+ b);
        }

        
    }


    static class Util{
        public static void ChMin(ref long a,long b){
            
            if(a > b){
                a = b;
            }
        }

        public static void ChMax(ref long a,long b){
            if(a < b){
                a = b;
            }
        }



		
    }
}



Measured memory_bytes: 11348
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

typedef long long LL;

inline int read()
{
	char c=getchar();int num=0,f=1;
	for(;!isdigit(c);c=getchar())
		f=c=='-'?-1:f;
	for(;isdigit(c);c=getchar())
		num=num*10+c-'0';
	return num*f;
}

const int N=205;

int n,a[N],ans;

int main()
{
	n=read()<<1;
	for(int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i+=2) ans+=a[i];
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
const int INF = 1001001001;
const ll LINF = 1e18;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)

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

bool p_comp_fs(const P p1, const P p2){ return p1.first < p2.first;};
bool p_comp_fg(const P p1, const P p2){ return p1.first > p2.first;};
bool p_comp_ss(const P p1, const P p2){ return p1.second < p2.second;};
bool p_comp_sg(const P p1, const P p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}


int main(){
    ll N; cin >> N; map<ll, ll> m;
    REP(i, N){
        ll a; cin >> a; m[a]++;
    }
    
    bool ok = true;
    if(N % 2 == 0 && m[0] > 0) ok = false;
    if(N % 2 == 1 && m[0] != 1) ok = false;
    FORMAP(it, m){
        if(it->first == 0) continue;
        else if(it->second != 2) {
            ok = false; break;
        }
    }
    ll ret = 1; const ll mod = 1e9+7;
    if(ok) REP(i, N / 2) ret = ret * 2 % mod;
    cout << (ok ? ret : 0) << endstr;
    return 0;
}


Measured memory_bytes: 4224
s = input()
t = input()
c = 0
ctemp = 0 

for i in range((len(s)-len(t))+1):
  for j in range(len(t)):
    if s[j+i] == t[j]:
      ctemp += 1
  c = max(c,ctemp)
  ctemp = 0
  
ans = len(t) - c
print(ans)

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

using namespace std;

int main(){
    int n, soma = 0;

    cin >> n;

    int houses[n];

    for(int i = 0; i < n; i++){
        cin >> houses[i];
    }

    sort(houses, houses + n);

    for(int i = n-1; i > 0; i--){
        soma += houses[i] - houses[i - 1];
    }

    cout << soma;
}

Measured memory_bytes: 256
N = input()
A = list(map(int, input().split()))
C = sorted(A)
l = len(A)
i = 0
S = 1

while i < l:
   S = S * C[i]
   i = i + 1
   if S > 1000000000000000000:
        print(-1)
        break
   elif i == l:
        print(S)
        break

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


int main() {
  string S;
  cin >> S;
  if (S.at(0) == S.at(1) || S.at(1) == S.at(2) || S.at(2) == S.at(3)) {
    cout << "Bad" << endl;
  }
  else {
    cout << "Good" << endl;
  }
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

typedef ll V;
const V INF_V = LLONG_MAX;
const int ME = 18;
const int N = 1<<ME;

class RMQ_segtree{
public:
    V dat[2*N-1];
    RMQ_segtree(){
        REP(i, 2*N - 1) dat[i] = INF_V;
    }

    void update(int k, V a){
        //k番目の要素をaに変更
        k += N-1;
        dat[k] = a;
        while(k>0){
            k = (k-1)/2;
            dat[k] = min(dat[2*k+1], dat[2*k+2]);
        }
    }

    V recursion(int a, int b, int k, int l, int r){
        //最小値計算用の再帰関数
        if(r<=a || b<=l) return INF_V;
        if(a<=l && r<=b) return dat[k];
        else{
            V vl = recursion(a, b, 2*k+1, l, (l+r)/2);
            V vr = recursion(a, b, 2*k+2, (l+r)/2, r);
            return min(vl, vr);
        }
    }

    V minimum(int a, int b){
        //区間[a, b)の最小値
        //rmq.minimum(0, 0) みたいに区間が空の場合は INF_INT を返す 
        return recursion(a, b, 0, 0, N);
    }
};

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

    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];
    RMQ_segtree rm;
    REP(i, N) rm.update(i, -A[i]);
    REP(i, N){
    	ll hidari, migi;
    	if(i==0) hidari = -INF_V;
    	else hidari = -rm.minimum(0, i);
    	if(i==N-1) migi = -INF_V;
    	else migi = -rm.minimum(i+1, N);
    	cout << max(hidari, migi) << endl;
    }
    return 0;
}

Measured memory_bytes: 7296
#include<stdio.h>
int main()
{
    int n,sum1=0,sum2=0,a[100],i,j,t;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n-1;i++)
        for(j=0;j<n-1-i;j++)
        {
            if(a[j]<a[j+1])
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    for(i=0;i<n;i++)
    {
        if(i%2==0)
            sum1+=a[i];
        else
            sum2+=a[i];
    }
    printf("%d\n",sum1-sum2);
    return 0;
}


Measured memory_bytes: 256
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	A := make([]int, n+1)
	sa := strings.Fields(sc.Text())
	for i := 0; i < n; i++ {
		A[i], _ = strconv.Atoi(sa[i])
	}
	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	count := 0
	st := strings.Fields(sc.Text())
	for j := 0; j < q; j++ {
		key, _ := strconv.Atoi(st[j])
		if !search(A, n, key) {
			continue
		}
		count++
	}
	fmt.Println(count)
}

func search(A []int, n, key int) bool {
	A = append(A, key)
	i := 0
	for A[i] != key {
		i++
	}
	return i != n+1
}



Measured memory_bytes: 6728
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;

int main(void) {
	int a,b;
	cin >> a >> b;
	int suma = 0, sumb = 1;
	for (int i = 1;i <= 499500;i++) {
		suma += i;
		sumb += (i + 1);
		if ((suma > a) && (sumb > b)) {
			if ((suma - a) == (sumb - b)) {
				cout << suma - a << endl;
				return 0;
			}
		}
		
	}
	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val S = readLine()!!
    val ac = S.count { it == 'a' }
    val bc = S.count { it == 'b' }
    val cc = S.count { it == 'c' }
    val aa = listOf(ac, bc, cc).sorted()

    if (aa.last() - aa.first() > 1) {
        println("NO")
    } else {
        println("YES")
    }
}


Measured memory_bytes: 39364
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

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

int main(){
    ll h,w;
    cin >> h >> w;
    ll res = h*w;
    if(h==1||w==1){
        cout << 1 << endl;
    }else if(res%2==0){
        cout << res/2 << endl;
    }else{
        cout << res/2 + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 888
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x1 = sc.nextInt();
    int y1 = sc.nextInt();
    int x2 = sc.nextInt();
    int y2 = sc.nextInt();
    int x3 = x2 - (y2 - y1);
    int y3 = y2 + (x2 - x1);
    int x4 = x1 - (y2 - y1);
    int y4 = y1 + (x2 - x1);
    System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);
  }
}

Measured memory_bytes: 23124
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (size_t i = 0; i < size_t(n); i++)
#define forn1(i,n) for (size_t i = 1; i <= size_t(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int h, w;
string maze[20];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
int d[20][20];

bool ok(int i, int j) {
    return 0 <= i && i < h && 0 <= j && j < w && maze[i][j] != '#';
}

int bfs(int i, int j) {
    que<pii> q({ mp(i, j) });
    forn(i, h) forn(j, w) d[i][j] = 10000000;
    d[i][j] = 0;

    int mx = 0;
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int i, j;
        tie(i, j) = p;

        forn(k, 4) {
            int newi = i + dx[k];
            int newj = j + dy[k];

            if (ok(newi, newj) && d[newi][newj] > d[i][j] + 1) {
                d[newi][newj] = d[i][j] + 1;
                chmax(mx, d[newi][newj]);
                q.emplace(newi, newj);
            }
        }
    }

    return mx;
}

int main() {
    fastio();

    cin >> h >> w;
    forn(i, h) cin >> maze[i];

    int ans = 0;
    forn(i, h) forn(j, w) {
        if (maze[i][j] == '#') continue;
        chmax(ans, bfs(i, j));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#if defined(DAIJOBU)
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}

const int maxn = 1e5 + 100;

struct UnionFind{
	vector<int> par;
	vector<int> rank;
	vector<int> Size;
	UnionFind(int n = 1){
		init(n);
	}
	void init(int n = 1){
		par.resize(n + 1);rank.resize(n + 1);Size.resize(n + 1);
		for(int i = 0; i <= n; ++i)par[i] = i, rank[i] = 0, Size[i] = 1;
	}
	
	int root(int x){
		if(par[x] == x)return x;
		return par[x] = root(par[x]);
	}
	bool isSame(int u, int v){
		return root(u) == root(v);
	}
	bool merge(int u, int v){
		u = root(u); v = root(v);
		if(u == v)return false;
		if(rank[u] < rank[v])swap(u, v);
		par[v] = u;
		Size[u] += Size[v];
		if(rank[u] == rank[v])rank[u]++;
		return true;
	}
	long long size(int u){
		return Size[root(u)];
	} 
};

int N, M, K;
int A[maxn], B[maxn], C[maxn], D[maxn], ans[maxn];

int main(){
	FIO
	
	cin >> N >> M >> K;
	UnionFind dsu(N + 1);
	for(int i = 0; i < M; ++i){
		cin >> A[i] >> B[i];
		dsu.merge(A[i], B[i]);
	}
	for(int i = 1; i <= N; i++){
		ans[i] = dsu.size(dsu.root(i)) - 1;
	}
	for(int i = 0; i < M; i++){
		if(!dsu.isSame(A[i], B[i]))continue;
		ans[A[i]]--;
		ans[B[i]]--;
	}
	for(int i = 0; i < K; i++){
		cin >> C[i] >>  D[i];
	}
	for(int i = 0; i < K; i++){
		if(!dsu.isSame(C[i], D[i]))continue;
		ans[C[i]]--;
		ans[D[i]]--;
	}
	for(int i = 1; i <= N; i++)cout << ans[i] << " ";
	return 0;
}


Measured memory_bytes: 3968
//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

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

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=300010;
int n,m;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>n>>m;
	cout<<6-n-m;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define PI 3.14159265358979323846
using namespace std;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   /// https://ideone.com/Fd5s8n

  int r;
  cin>>r;
  cout << fixed << setprecision(20) << 2*PI*r << endl;
}


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

s = [0] * M
c = [0] * M

for i in range(M):
    s[i], c[i] = map(int, input().split())

ans = -1

for n in range(10 ** N):
    num = str(n)
    if len(num) != N:
        continue
    if all([num[s[i] - 1] == str(c[i]) for i in range(M)]):
        ans = num
        break

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	int w, h, n, a, b;
	while(cin >> w >> h) {
		if(w == 0 && h == 0) break;

		ll dp[50][50];
		memset(dp, 0, sizeof(dp));

		cin >> n;
		rep(i, n) {
			cin >> a >> b;
			dp[b][a] = -1;
		}

		REP(i, 1, w + 1) {
			if(dp[1][i] == -1) break;
			dp[1][i] = 1;
		}

		REP(i, 1, h + 1) {
			if(dp[i][1] == -1) break;
			dp[i][1] = 1;
		}

		REP(i, 2, h + 1) {
			REP(j, 2, w + 1) {
				if(dp[i][j] == -1) continue;

				if(dp[i-1][j] != -1) dp[i][j] += dp[i-1][j];
				if(dp[i][j-1] != -1) dp[i][j] += dp[i][j-1];
			}
		}

		cout << dp[h][w] << endl;
	}

	return 0;
}

Measured memory_bytes: 1180
inp=list(map(int,input().split()))
x=inp[0]
y=inp[1]
if (x+y)%3!=0:
  print (0)
else:
  flag=0
  z=(x+y)//3
  n=x-z
  m=y-z
  if m<0 or n<0:
    print (0)
    flag=1
  else:
    arr=[1]
    v=pow(10,9)+7
    for i in range(1,m+n+1):
      arr.append((arr[-1]*i)%v)
    a=arr[m+n]
    b=(arr[m]*arr[n])%v
    print ((a*pow(b,v-2,v))%v)

Measured memory_bytes: 35260
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=1e5+10;
int Begin[maxn],Next[maxn],to[maxn],e;
int num[maxn],tmp,f[maxn];
inline void add_edge(int x,int y){
	to[++e]=y;
	Next[e]=Begin[x];
	Begin[x]=e;
}
void dfs(int x){
	for(int i=Begin[x];i;i=Next[i]) dfs(to[i]);
	tmp=0;
	for(int i=Begin[x];i;i=Next[i]) num[++tmp]=f[to[i]];
	sort(num+1,num+tmp+1);
	REP(i,1,tmp) chkmax(f[x],num[i]+tmp-i+1);
}
int main(){
	int n=read();
	REP(i,2,n){
		int x=read();
		add_edge(x,i);
	}
	dfs(1);
	printf("%d\n",f[1]);
	return 0;
}


Measured memory_bytes: 4992
from sys import stdin
from itertools import repeat
def main():
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n - 2))
    la = [None] * (n + 1)
    xt = [None] * len(dat)
    j = 0
    for i in xrange(n - 1):
        x, y = dat[j], dat[j+1]
        xt[j] = la[y]
        la[y] = j
        j += 1
        xt[j] = la[x]
        la[x] = j
        j += 1
    g = [None] * (n + 1)
    st = [1]
    pu = st.append
    po = st.pop
    while st:
        x = po()
        if g[x] is None:
            g[x] = -1
            pu(x)
            y = la[x]
            while y is not None:
                if g[dat[y]] is None:
                    pu(dat[y])
                y = xt[y]
        else:
            f = 0
            y = la[x]
            while y is not None:
                if g[dat[y]] != -1:
                    f ^= g[dat[y]] + 1
                y = xt[y]
            g[x] = f
    print "Alice" if g[1] else "Bob"
main()


Measured memory_bytes: 20080
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; i ++) {
                scanf("%d", &a[i]);
        }
        int sum = 0;
        for (int i = 0; i < n; i ++) {
                sum += a[i];
        }
        sort(a.begin(), a.end());
        const int N = 8080808;
        vector<bitset<N>> dp(2);
        const int zero = N / 2;
        dp[0][zero] = 1;
        bool f = 1;
        for (int i = 0; i < n; i ++) {
                dp[f].reset();
                dp[f] |= dp[!f] << a[i];
                dp[f] |= dp[!f] >> a[i];
                f = !f;
        }
        f = !f;
        int x = 100000000;
        int res = 0;
        int p = N / 2;
        while (!dp[f][p] && p < N + 1) {
                res ++;
                p ++;
        }
        x = min(x, res);
        res = 0;
        p = N / 2;
        while(!dp[f][p] && p >= 0) {
                res ++;
                p --;
        }
        x = min(x, res);
        int suma = (sum - x) / 2;
        printf("%d\n", sum - suma);
        return 0;
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1e9+7;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

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

struct BinaryIndexedTree{
    private:
    int n;
    vector<int> dat;
    public:
    BinaryIndexedTree(int n_){
        n=1;
        while(n<n_){
            n*=2;
        }
        dat.resize(n,0);
    }
    void add(int a,int w){
        for (int i=a;i<=n;i+=i&-i){
            dat[i]+=w;
        }
    }
    int sum(int a){
        int res=0;
        for (int i=a;i>0;i-=i&-i){
            res+=dat[i];
        }
        return res;
    }
    int binarysearch(int w){
        if (w<=0){
            return 0;
        }
        int x=0;
        for (int k=n;k>0;k/=2){
            if (x+k<=n&&dat[x+k]<w){
                w-=dat[x+k];
                x+=k;
            }
        }
        return x;
    }
};

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N),B(N);
    rep(i,N){
        cin >> A[i];
        B[i]=A[i];
    }
    sort(B.begin(),B.end());
    BinaryIndexedTree BIT(2010);
    ll ans=0;
    for (int i=N-1;i>=0;--i){
        BIT.add(A[i],1);
        ans+=K*(K-1)/2%MOD*(lower_bound(B.begin(),B.end(),A[i])-B.begin())%MOD;
        ans+=K*BIT.sum(A[i]-1)%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
int main()
{
    string s;
    cin >> s;
    if (s.size() < 4) {
        cout << "No" << endl;
    } else {
        string a = "YAKI";
        rep(i, 4)
        {
            if (s[i] != a[i]) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>

int main(){

	int n;
	std::cin >> n;

	int sum = 0, sum2 = 0;

	for (int i = 0; i < n; i++){
		std::string str, str2;
		std::cin >> str >> str2;

		if (str>str2)sum += 3;
		else if (str < str2)sum2 += 3;
		else sum++, sum2++;
	}

	std::cout << sum << " " << sum2 << std::endl;

	return 0;
}

Measured memory_bytes: 1212
Scanf.scanf "%d %s" (fun n s ->
    let rec loop i cur mx =
        if i = n then Printf.printf "%d\n" mx else
            let cur = if s.[i] = 'I' then cur + 1 else cur - 1 in
            loop (i + 1) cur (max mx cur)
    in
    loop 0 0 0
)

Measured memory_bytes: 3804
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

struct mint {
    ll v;
    ll mod;
    mint() : v(0) {}
    mint(signed v, ll mod = MOD) : v(v), mod(mod) {}
    mint(ll t, ll mod = MOD) : mod(mod) {
        v = t % mod;
        if (v < 0)
            v += mod;
    }

    mint pow(ll k) {
        mint res(1), tmp(v);
        while (k) {
            if (k & 1)
                res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static mint add_identity() { return mint(0); }
    static mint mul_identity() { return mint(1); }

    mint inv() { return pow(mod - 2); }

    mint &operator+=(mint a) {
        v += a.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mint &operator-=(mint a) {
        v += mod - a.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mint &operator*=(mint a) {
        v = 1LL * v * a.v % mod;
        return *this;
    }
    mint &operator/=(mint a) { return (*this) *= a.inv(); }

    mint operator+(mint a) const { return mint(v) += a; };
    mint operator-(mint a) const { return mint(v) -= a; };
    mint operator*(mint a) const { return mint(v) *= a; };
    mint operator/(mint a) const { return mint(v) /= a; };

    mint operator-() const { return v ? mint(MOD - v) : mint(v); }

    bool operator==(const mint a) const { return v == a.v; }
    bool operator!=(const mint a) const { return v != a.v; }
    bool operator<(const mint a) const { return v < a.v; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vi s(n), t(m);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> t[i];
    }
    vector<vector<mint>> dp(n + 1, vector<mint>(m + 1, mint(0)));
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }
    for (int i = 0; i <= m; ++i) {
        dp[0][i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1])
                dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
            dp[i][j] -= dp[i - 1][j - 1];
        }
    }
    cout << dp[n][m].v << "\n";
    return 0;
}

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

using namespace std;

template <class T>
inline T updmax(T &a, T b) { return a = max(a, b); }
template <class T>
inline T updmin(T &a, T b) { return a = min(a, b); }

int main()
{
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	printf("%d\n", min(a * n, b));
	return 0;
}

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

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


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int n,ni[7],i,to;
	while(0<=scanf("%d",&n)){
		if(n==0)break;
		
		for(i=0;i<7;i++)ni[i]=0;
		
		for(i=0;i<n;i++){
			scanf("%d",&to);
			if(to<10){
				++ni[0];
			}else if(to<20){
				++ni[1];
			}else if(to<30){
				++ni[2];
			}else if(to<40){
				++ni[3];
			}else if(to<50){
				++ni[4];
			}else if(to<60){
				++ni[5];
			}else{
				++ni[6];
			}
		}
		for(i=0;i<7;i++)printf("%d\n",ni[i]);
	}
	return 0;
}

Measured memory_bytes: 760
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

using namespace std;
const int INF = 1e8;

//0:up, 1:right, 2:down, 3:left
vector<pair<int, int>> direction(4);

//距離を計算する
int f( vector<pair<int, int>> vec){
    sort(vec.begin(), vec.end());
    int dist = INF;
    for(int i=0; i<vec.size()-1; ++i){
        if(vec[i].second == 0 && vec[i+1].second != 0){
            int tmp = vec[i+1].first - vec[i].first; 
            dist = min(dist, tmp);
        }
    }
    return dist;
}

int main(){
    int N; cin >> N ;
    vector<int> x(N), y(N), dir(N);

    for(int i=0; i<N; ++i){
        int X, Y;
        char U;
        cin  >> x[i] >> y[i];
        cin  >> U;

        if( U == 'U') dir[i] = 0;
        if( U == 'R') dir[i] = 1;
        if( U == 'D') dir[i] = 2;
        if( U == 'L') dir[i] = 3;
    }

    int ans = INF;

    //四回分ですべてをカバー
    for(int i=0; i<4; ++i){
        
        //すべてのx座標を独立に考える
        // x座標: [{y座標1, 方向1}, {y座標2, 方向2}]　みたいな感じ 
        {
            map<int, vector<pair<int, int>>> mp;
            //180度パターン、上と下でぶつかる場合を考える
            for(int i=0; i<N; ++i){
                if (dir[i] != 0 && dir[i] !=2) continue;
                mp[x[i]].emplace_back( y[i], dir[i] );
            }

            for(auto y_dir : mp){
                int res = f(y_dir.second);
                if(res == INF)continue;
                ans = min(ans, res*5);
            }
        }
        //90度パターン、直角にぶつかる。ここではUとRでぶつかるを想定
        {
            map<int, vector<pair<int, int>>> mp;
            //この場合x+y座標の和が一致する
            for(int i=0; i<N; ++i){
                if (dir[i] != 0 && dir[i] !=1) continue;
                mp[ x[i] + y[i] ].emplace_back(y[i], dir[i]); 
            }
            for(auto y_dir : mp){
                int res = f(y_dir.second);
                if(res == INF)continue;
                ans = min(ans, res*10);
            }
        }

        //時計回りに回転
        for(int i=0; i<N; ++i){
            int px = y[i];
            int py = -x[i];
            x[i] = px;
            y[i] = py;
            dir[i] = (dir[i] + 1)%4;
        }
    }

    if(ans == INF){
        cout << "SAFE" << endl;
    }else{
        cout << ans << endl;
    }

}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    string S;
    cin >> S;
    bool flag = false;
    REP(i, 3) if(S[i] == S[i+1]) flag = true;
    cout << (flag ? "Bad" : "Good") << endl;
    return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            C[i][j] = sum(A[i][k] * B[k][j] for k in range(K)) % MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)


Measured memory_bytes: 71132