akhauriyash/Code-Regression huggingface dataset:
n,q = map(int,input().split())
S = input()
ac_list = [0,0]
question_list = []
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        ac_sum = ac_list[i+1] + 1
        ac_list.append(ac_sum)
    else:
        ac_list.append(ac_list[-1])
for _ in range(q):
    l, r = map(int,input().split())
    question_list.append([l,r])
for l,r in question_list:
    print(ac_list[r]-ac_list[l])

Measured memory_bytes: 22872
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

int countN, n[20], countQ, q;

bool solve(int i, int m) {
    if (m == 0) return true;
    if (i >= countN) return false;
    return solve(i + 1, m) || solve(i + 1, m - n[i]);
}

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

    cin >> countQ;
    for (int i = 0; i < countQ; i++) {
        cin >> q;
        if (solve(0, q)) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

Measured memory_bytes: 1116
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _0047
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] cups = { 1, 0, 0 };
            string temp = "";
            while ((temp = Console.ReadLine()) != null)
            {
                string[] order = temp.Split(',');
                int a = 0;
                int b = 0;

                StringComparer cmp = StringComparer.OrdinalIgnoreCase;
                Array.Sort(order, cmp);

                if (order[0] == "A")
                {
                    a = 0;
                }
                else
                {
                    a = 1;
                }

                if (order[1] == "B")
                {
                    b = 1;
                }
                else
                {
                    b = 2;
                }

                int c = cups[a];
                cups[a] = cups[b];
                cups[b] = c;
            }

            for (int i = 0; i < 3; i++)
            {
                int answer = cups[i];
                if (answer == 1)
                {
                    if (i == 0)
                    {
                        Console.WriteLine("A");
                    }
                    else if (i == 1)
                    {
                        Console.WriteLine("B");
                    }
                    else
                    {
                        Console.WriteLine("C");
                    }
                   
                }
            }


        }
    }
}



Measured memory_bytes: 15824
#include "bits/stdc++.h"
using namespace std;
int N;
vector<int>to[100005];

int main() {
	int N;
	cin >> N;
	map<int, int>mp;
	for (int i = 0; i < N; ++i) {
		int n;
		cin >> n;
		mp[n]++;
	}
	int count = 0;
	int count2 = 0;
	for (auto p:mp) {
		int n = p.second;
		if (1 == n%2) {
			count++;
		}
		else {
			count2++;
		}
	}
	if (1 == count2%2) {
		count += count2 - 1;
		count2 = 1;
	}
	else {
		count += count2 - 2;
		count2 = 2;
	}
	if (1 == count2) {
	}
	else {
		count += 2;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 10472
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<tuple>
#include<ctime>
#include<functional>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p; 
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))

int main(){
 int l,r,d,ans=0;
 cin>>l>>r>>d;
 ans=(r-l)/d;
 if(l%d==0 || r%d==0) ans++;
    p(ans);
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX_N = 201010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dx[8] = { 1,-1,0,0,1,1,-1,-1 };
ll dy[8] = { 0,0,1,-1,1,-1,1,-1 };
string dir[8] = { "R","L","D","U","RD","RU","LD","LU" };
bool flag[201010];
ll ans[201010];

vector<vector<ll>>to;

void dfs(ll v) {
	flag[v] = true;
	for (auto nv : to[v]) {
		if (flag[nv] == false) {
			ans[nv] += ans[v];
			dfs(nv);
		}
	}
}

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	ll n, q;
	cin >> n >> q;
	to.resize(n);
	rep(i, n-1) {
		ll a, b;
		cin >> a >> b;
		a--, b--;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	rep(i, q) {
		ll p, x;
		cin >> p >> x;
		p--;
		ans[p] += x;
	}
	dfs(0);
	rep(i, n) {
		cout << ans[i];
		cout << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 25256
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.time.LocalTime;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;


public class Main {

    public static void main(String[] args) {
    
    	FastScanner scan = new FastScanner();
    	
    	String s = scan.next();
    	char [] ch = s.toCharArray();
    	
    	if(ch[ch.length-1] != 's') {
    		System.out.println(s + "s");
    	} else {
    		System.out.println(s + "es");
    	}
    	
    }

    static class FastScanner{
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
    	String next() {
    		while(!st.hasMoreTokens())
    			try {
    				st = new StringTokenizer(br.readLine());
    			} catch (IOException e){
    				e.printStackTrace();
    			}
    		return st.nextToken();
    	}
    	
    	int nextInt() {
    		return Integer.parseInt(next());
    	}
    	
    	int [] readArray(int n) {
    		int [] a = new int[n];
    		for(int i=0; i<n ; i++) a[i] = nextInt();
    		return a;
    	}
    	
    	long nextLong() {
    		return Long.parseLong(next());
    	}
    	
    	
    }
    
   
}



Measured memory_bytes: 36680
#include <iostream>
#include <stdlib.h>
#include <utility>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <stdio.h>
#define   FOR(i,n) for(int i=0;i<n;i++)

using namespace std;
int int_sort(const void*a,const void *b) {
    return *(  int *) b - *(int *) a;
    //qsort(b, a, sizeof(long long int), int_sort);
}

int main() {

   int a,N;

       cin>>N>>a;
   if(N%500-a<=0)
       cout<<"Yes";
   else
       cout<<"No";

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  char x;
  scanf("%s", &x);
  if(x == 'A'){
    printf("T");
  }
  else if(x == 'T'){
    printf("A");
  }
  else if(x == 'C'){
    printf("G");
  }
  else{
    printf("C");
  }
  return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll ,ll> pll;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
#define REP(i,x,y) for(ll i = x;i <= y;++i)
vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z))
        ;
    return res;
}
void debug_out(vector<string> args, int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
void localTest() {
    #ifndef ONLINE_JUDGE
        freopen("inp", "r", stdin);
        freopen("out", "w", stdout);
    #endif      
}
const ll N = 2e6 + 5, MOD = 1e9 + 7;
ll fac[N], ifac[N];
ll C(ll n, ll r) {
	if(n < r) return 0;
	ll ret = fac[n];
	ret = (ret * ifac[r]) % MOD;
	ret = (ret * ifac[n - r]) % MOD;
	return ret;
}
ll power(ll a, ll b, ll c) {
	ll ret = 1;
	while(b) {
		if(b & 1) ret = (ret * a) % c;
		b >>= 1LL;
		a = (a * a) % c;
	}
	return ret;
}
int main() {

    localTest();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    fac[0] = ifac[0] = 1;
    for(ll i = 1;i < N;++i) {
    	fac[i] = (i * fac[i - 1]) % MOD;
    	ifac[i] = power(fac[i], MOD - 2, MOD);
    }
 	ll n, k;
 	string s;
 	cin >> k >> s;
 	n = k + s.size();
 	ll ans = power(26, n, MOD);
 	for(ll i = 0;i < (ll)s.size();++i) {
 		ans -= (C(n, i) * power(25, n - i, MOD)) % MOD;
 		ans += MOD;
 		ans %= MOD;
 	}  
 	cout << ans << "\n";

    
    return 0;
}

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

#define op operator
struct poi {
	int x, y;
	void r() { cin >> x >> y; }
	poi op -(poi p) {
		return {x - p.x, y - p.y};
	}
	int len2() { return x * x + y * y; }
};
int sqr(int x) { return x * x; }

int solve(poi o1, int r1, poi o2, int r2) {
	int d = (o1 - o2).len2();
	if(d > sqr(r1 + r2)) return 4;
	if(d == sqr(r1 + r2)) return 3;
	if(d > sqr(r1 - r2)) return 2;
	if(d == sqr(r1 - r2)) return 1;
	return 0;
}

int main() {
	poi o1, o2; int r1, r2;
	o1.r(); cin >> r1;
	o2.r(); cin >> r2;
	cout << solve(o1, r1, o2, r2) << '\n';
	return 0;
}

Measured memory_bytes: 3112
#include <cstdio>

#define fin stdin
#define fout stdout

#define MOD (1000 * 1000 * 1000 + 7)

int r[5009][5009];

inline int lgput(int a, int n){
    int r = 1;
    while(n > 0){
        if(n % 2) r = 1LL * r * a % MOD;
        a = 1LL * a * a % MOD;
        n /= 2;
    }
    return r;
}

int main(){
    int n;
    fscanf(fin, "%d ", &n);

    int m = 0;
    char ch = fgetc(fin);

    while(ch != '\n'){
        m ++;
        ch = fgetc(fin);
    }

    /*fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = (1LL * fact[i-1] * i)%MOD;
    invFact[i] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i --)
        invFact[i] = 1LL * invFact[i+1] * (i+1) % MOD;

    int ajut = 1;
    for(int i = 0;  i <= n/2; i++){
        cat[i] = 1LL * fact[2 * i] * invFact[i] % MOD * invFact[i+1] % MOD * ajut % MOD;
        ajut *= 2;
        if(ajut >= MOD)
            ajut -= MOD;
    }*/

    r[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        r[i][0] = r[i-1][0] + r[i-1][1];
        if(r[i][0] >= MOD)
            r[i][0] -= MOD;
        for(int j = 1; j <= i; j++){
            r[i][j] = 2 * r[i-1][j-1];
            if(r[i][j] >= MOD)
                r[i][j] -= MOD;
            r[i][j] += r[i-1][j+1];
            if(r[i][j] >= MOD)
                r[i][j] -= MOD;
        }
    }

    int ans = 1;
    for(int i = 0; i < m; i++)
        ans = 2 * ans % MOD;
    ans = lgput(ans, MOD-2);

    ans = 1LL * ans * r[n][m] % MOD;

    fprintf(fout, "%d\n", ans);

    return 0;
}


Measured memory_bytes: 96384
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
		//Implement solution here.
		int N = ni();
		int[] A = na(N);
		int[] trends = new int[N];
		long result = 1000;
		long stocks = 0;
		
		for(int i = 1; i < N; i++) {
			if(A[i] < A[i - 1]) {
				trends[i] = - 1;
			} else if(A[i] == A[i - 1]) {
				trends[i] = trends[i - 1];
			} else {
				trends[i] = 1;
			}
		}
		
		for(int i = N - 2; i >= 0; i--) {
			if(trends[i] == 0)trends[i] = trends[i + 1];
		}
		
		if(trends[1] > 0) {			
			stocks = result / A[0];
			result = result % A[0];			
		}
		
		for(int i = 1; i < N - 1; i++) {
			if(trends[i] > 0 && trends[i + 1] < 0) {
				//sell
				result += A[i] * stocks;
				stocks = 0;
			} else if (trends[i] < 0 && trends[i + 1] > 0) {
				//buy
				stocks = result / A[i];
				result = result % A[i];				
			}
		}
		
		result += A[N - 1] * stocks;
		stocks = 0;
		System.out.println(result);
//		for(int i:trends)System.out.print(i + " ");
//		System.out.println();
	}


	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		boolean hasNext = true;
		while(hasNext){
			solve();	
			try{
				br.mark(1);
				if(br.read() > 0){
					br.reset();			
					System.out.println("---");
				} else {
					hasNext = false;
				}
			}catch(Exception e){
				throw new RuntimeException(e);
			} 
		}
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 25332
use std::io::*;
use std::str::FromStr;
   
fn read<T: FromStr>() -> T {
	let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
	let n: u32 = read();
	let mut a: Vec<u32> = Vec::new();
	for _i in 0..n {
		a.push(read());
	}
	let mut r: Vec<u32> = vec![0; n as usize];
	for i in 0..n {
		r[(a[i as usize]-1)  as usize] = i+1;
	}
	for ri in r.iter() {
		println!("{}", ri);
	}
}


Measured memory_bytes: 4860
N=int(input())
A = list(map(int, input().split()))
ans=0
tmp=0
hoge=0
li=[]

for i in range(N):
    li.append(abs(A[i]))
    ans+=abs(A[i])
    if A[i]<0:
        tmp+=1
    if A[i]==0:
        hoge=1

if tmp%2==0 or hoge==1:
    ans=ans
else:
    ans=ans-2*min(li)

print(ans)

Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
bool A[6];
int main() {
  int X[5];
  for (int i = 0; i < 5; i++) cin >> X[i];
  for (int i = 0; i < 5; i++) A[X[i]] = true;
  for (int i = 1; i <= 5; i++) {
    if (A[i] == false) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

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

int main() {
	int A, B;
	cin >> A >> B;
	int x = A + B;
	if (x % 2 == 0) {
		cout << x / 2;
	}
	else {
		cout << "IMPOSSIBLE";
	}
	cout << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main(void) {
	int a, b, c, d;
	int p, q;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	switch (c%b)
	{
		case 0:
			p = c / b;
			break;
		default:
			p = c / b + 1;
			break;
	}
	switch (a%d)
	{
		case 0:
			q = a / d;
			break;
		default:
			q = a / d + 1;
			break;
	}
	if (p <= q) puts("Yes");
	else puts("No");
	return 0;
}



Measured memory_bytes: 1644
def acinput():
    return list(map(int, input().split(" ")))

import bisect
import numpy as np

N=int(input())
L=acinput()
L=sorted(L)

count=0
for i in range(N-2):
    for j in range(i+1,N-1):
        #l=bisect.bisect_right(L,1+L[j]-L[i])
        r=bisect.bisect_left(L,L[i]+L[j])
        #print(L)
        #print(i,j)
        #r=min(r,N-1)
        #print(r)

        #print((r-j-1))

        count+=(r-j-1)



print(count)


Measured memory_bytes: 14284
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k; cin>>n>>k;
  int arr[n];
  for(int i=0;i<n;i++) cin>>arr[i];
  int ans[n]; ans[0]=0; ans[1]=abs(arr[1]-arr[0]);
  for(int i=2;i<n;i++){
      ans[i]=INT_MAX;
      for(int j=i-1;j>=max(0,i-k);j--)
        ans[i]=min(ans[j]+abs(arr[i]-arr[j]),ans[i]);
  }
  cout<<ans[n-1];
  return 0;
}

Measured memory_bytes: 1024
import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

void main() {
  long[][] matrix;
  bool[long] numbers;
  foreach(i; 0..3) {
    auto line = readln.split.to!(long[]);
    matrix ~= line;
    foreach(l; line) numbers[l] = false;
  }

  foreach(i; 0..readln.chomp.to!long) {
    auto n = readln.chomp.to!long;
    numbers[n] = true;
  }

  bool solve() {
    bool[][] comb;
    foreach(i; 0..3) {
      comb ~= [numbers[matrix[0][i]], numbers[matrix[1][i]], numbers[matrix[2][i]]];
      comb ~= [numbers[matrix[i][0]], numbers[matrix[i][1]], numbers[matrix[i][2]]];
    }
    comb ~= [numbers[matrix[0][0]], numbers[matrix[1][1]], numbers[matrix[2][2]]];
    comb ~= [numbers[matrix[0][2]], numbers[matrix[1][1]], numbers[matrix[2][0]]];

    foreach(c; comb) {
      if (c.all!(x => x == true)) return true;
    }
    return false;
  }

  writeln(solve() ? "Yes" : "No");
}


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

int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  sort(a,a+n);
  int count=0;
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]) count++;
  }
  if(count%2) count++;
  cout << n-count << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include<bitset>
#include<stdio.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

bool isOK(int a[],int index,int key){
    if(a[index] >= key){
        return true;
    }else{
        return false;
    }
}

int binary_search(int a[],int n,int key){
    int left = -1;
    int right = n;

    while(right-left>1){
        int mid = left + (right - left)/2;
        if(isOK(a,mid,key)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}



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

    if(n%10==3){
        cout << "bon" << endl;
    }else if(n%10==0 || n%10==1 || n%10==6 || n%10==8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
D,G=map(int,input().split())
# bit全探索で、全問解く問題の組み合わせをすべて試す

scores=[None]*D
for i in range(D):
  p,c=map(int,input().split())
  # 一問の得点、問題数、ボーナス、全てといたときの得点
  scores[i]=[(i+1)*100,p,c,((i+1)*100)*p+c]

# あとあとのために点数高い順に並べる
scores=sorted(scores,key=lambda x:x[0])[::-1]

# 全問とく組み合わせに対して、最小の問題数
ans=D*100
for i in range(2**D):
  total=0
  solve=0
  for j in range(D):
    if (i>>j)&1:
      # 全問とく問題のボーナスを足していく
      total+=scores[j][3]
      solve+=scores[j][1]
  if total>=G:
    if ans>solve:
      ans=solve
    continue
  rest=G-total
  for j in range(D):
    if (i>>j)&1==0:
      point=scores[j][0]
      num=scores[j][1]-1 # 全問とかないので1減らす
      if point*num<rest:
        rest-=point*num
        solve+=num
      else:
        solve+=(rest//point+(rest%point>0))
        rest=0
    if rest<=0 and ans>solve:
      ans=solve
  
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<int >    vecint;
typedef vector<string > vecstr;
int main()
{
  ll n, k;
  cin >> n >> k;
  cout << k*(ll)pow(k - 1,n - 1) << endl;
} 


Measured memory_bytes: 256
// Problem : F - Pond Skater
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_f
// Memory Limit : 1024 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}
vector<vi> dis;
void solve()
{
int n,m,k;cin>>n>>m>>k;
incd(dis,n);
for(int i=0;i<n;i++)
inc(dis[i],m,INT_MAX);
int sx,sy,ex,ey;
cin>>sx>>sy>>ex>>ey;
sx--;sy--;ex--;ey--;
vs v(n);
cin>>v;
set<pair<int,pii>> s;
s.insert({0,{sx,sy}});
dis[sx][sy]=0;
while(!s.empty())
{
	pair<int,pii> p=*s.begin();
	pii t=p.se;
	if(t==m_p(ex,ey))
	{
		cout<<p.f;
		return;
	}
	s.erase(s.begin());
	for(int i=t.f+1;i<min2(n,t.f+k+1);i++)
	{
		if(v[i][t.se]=='@')break;
		if(dis[i][t.se]>=p.f+1)
		{
			dis[i][t.se]=p.f+1;
			s.insert({p.f+1,{i,t.se}});
		}
		else
		break;
	}
	for(int j=t.se+1;j<min2(m,t.se+k+1);j++)
	{
		if(v[t.f][j]=='@')break;
		if(dis[t.f][j]>=p.f+1)
		{
			dis[t.f][j]=p.f+1;
			s.insert({p.f+1,{t.f,j}});
		}
		else
		break;
	}
	for(int i=t.f-1;i>=max2(0LL,t.f-k);i--)
	{
		if(v[i][t.se]=='@')break;
		if(dis[i][t.se]>=p.f+1)
		{
			dis[i][t.se]=p.f+1;
			s.insert({p.f+1,{i,t.se}});
		}
		else
		break;
	}
	for(int j=t.se-1;j>=max2(0LL,t.se-k);j--)
	{
		if(v[t.f][j]=='@')break;
		if(dis[t.f][j]>=p.f+1)
		{
			dis[t.f][j]=p.f+1;
			s.insert({p.f+1,{t.f,j}});
		}
		else
		break;
	}
}
cout<<-1;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 19456
import sys

import numpy as np

sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


def ii(t: type = int):
    return t(input())


def il(t: type = int):
    return list(map(t, input().split()))


def imi(N: int, t: type = int):
    return [ii(t) for _ in range(N)]


def iml(N: int, t: type = int):
    return [il(t) for _ in range(N)]


def solve():
    N = ii()
    AB = iml(N)
    ll = []
    for a, b in AB:
        ll.append(a + b)
    ind = np.argsort(ll)[::-1]
    t = [AB[i][0] for i in ind[::2]]
    a = [AB[i][1] for i in ind[1::2]]
    return sum(t) - sum(a)


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 42136
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n, m;
    cin >> n >> m;

    vector<ll> value(m);

    rep(i,m){
        cin >> value[i];
    }

    vector<vector<ll>> dp(m+1, vector<ll>(n+1, INF));
    dp[0][0] = 0;
    rep(i,m){
        for(ll j = 0; j <= n; j++){
            if(j - value[i] >= 0){
                dp[i+1][j] = min(dp[i][j], dp[i+1][j - value[i]] + 1);
            }else{
                dp[i+1][j] = dp[i][j];
            }
            
        }
    }

    cout << dp[m][n] << endl;


}


Measured memory_bytes: 11616
#include <bits/stdc++.h>
using namespace std;
long long N, M;
vector<vector<int>> G;
vector<int> a;
bool f(int p, int q, int r) {
	if (a[p] != 0) return a[p] == r;
	a[p] = r;
	for (int v : G[p]) if (v != q) {
		if (!f(v, p, r ^ 3)) return false;
	}
	return true;
}
int main() {
	cin >> N >> M;
	G.resize(N);
	for (int i = 0; i < M; ++ i) {
		int x, y;
		cin >> x >> y;
		-- x; -- y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	a.resize(N);
	if (f(0, -1, 1)) {
		vector<long long> b(3);
		for (int x : a) ++ b[x];
		cout << b[1] * b[2] - M << endl;
	} else {
		cout << N * (N-1) / 2 - M << endl;
	}
}


Measured memory_bytes: 6528
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num::clamp;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize, m: usize,
        p: [Usize1; n],
        xy: [(Usize1, Usize1); m]
    }

    let mut uft = UFT::new(n);
    for (x, y) in xy {
        uft.merge(x, y);
    }

    let mut ans = 0usize;
    for &v in &p {
        if uft.root(v) == uft.root(p[v]) {
            ans += 1;
        }
    }
    println!("{}", ans);
}

#[allow(dead_code)]
/// Union Find Tree
pub struct UFT {
    pub par: Vec<usize>,
    pub rank: Vec<usize>,
}
impl UFT {
    #[allow(dead_code)]
    pub fn new(n: usize) -> Self {
        UFT {
            par: (0..n).collect(),
            rank: vec![0; n],
        }
    }
    #[allow(dead_code)]
    pub fn root(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            let p = self.par[x];
            let pp = self.root(p);
            self.par[x] = pp;
            pp
        }
    }
    #[allow(dead_code)]
    pub fn merge(&mut self, x: usize, y: usize) {
        let x = self.root(x);
        let y = self.root(y);
        if x == y {
            return;
        }
        if self.rank[x] < self.rank[y] {
            self.par[x] = y;
        } else {
            self.par[y] = x;
            if self.rank[x] == self.rank[y] {
                self.rank[x] += 1;
            }
        }
    }
}

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

using namespace std;

void Main() {
    int A, B, X;
    cin >> A >> B >> X;
    bool yes = false;
    if (A <= X && X <= A + B) {
        yes = true;
    }
    cout << (yes ? "YES" : "NO") << endl;
}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 1234;
const LL MOD = (LL)1e9 + 7;
struct edge {
       int s, t;
       LL w;
       edge(int a, int b, LL c) : s(a), t(b), w(c) {}
       bool operator < (const edge &t) const {
            return w < t.w;
       }
};
vector<pii> G[MAXN];
vector<edge> edges;
vector<int> cand;
int par[MAXN];

void init(int n) {
     for (int i = 1; i <= n; i++) par[i] = i;
}

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

bool merge(int x, int y) {
     x = find(x);
     y = find(y);
     if (x == y) return false;
     par[x] = y;
     return true;
}

bool dfs(int cur, int tg, int par) {
     if (cur == tg) return true;
     bool OK = false;
     for (auto &i : G[cur]) {
         if (i.first != par && dfs(i.first, tg, cur)) {
            OK = true;
            cand.push_back(i.second);
         }
     }
     return OK;
}
LL q_pow(LL n) {
   if (n == 0) return 1;
   if (n == 1) return 2;
   LL tmp = q_pow(n / 2);
   if (n % 2) return (((tmp * tmp) % MOD) * 2) % MOD;
   else return ((tmp * tmp) % MOD);
}

int solve(edge &i, int N, LL sum, LL X) {
    cand.clear();
    dfs(i.s, i.t, i.s);
    sort(cand.begin(), cand.end());
    LL tmp = sum - cand.back() + i.w;
    if (tmp == X) return 1;
    else if (tmp > X) return 2;
    return 0;
}

int main() {
    int N, M;
    LL X;
    scanf("%d %d", &N, &M);
    scanf("%lld", &X);
    init(N);
    for (int i = 0; i < M; i++) {
        int s, t;
        LL w;
        scanf("%d %d %lld", &s, &t, &w);
        edges.push_back(edge(s, t, w));
    }
    sort(edges.begin(), edges.end());
    LL sum = 0, cnt = 0;
    for (auto &i : edges) {
        if (merge(i.s, i.t)) {
           sum += i.w;
           cnt++;
           G[i.s].push_back(make_pair(i.t, i.w));
           G[i.t].push_back(make_pair(i.s, i.w));
        }
    }
    LL cnt0 = 0, cnt1 = 0;
    for (auto &i : edges) {
        int tmp = solve(i, N, sum, X);
        if (tmp == 1) cnt0++;
        else if (tmp == 2) cnt1++;
    }
    // if (cnt0 == 0 || M < 2) puts("0");
    // else {
       LL ans = q_pow(cnt0);
       if (sum == X) {
          ans -= 2;
          ans = (ans * q_pow(cnt1)) % MOD;
       } else {
          ans = ((2 * (ans - 1) % MOD) * q_pow(cnt1)) % MOD;
       }
       printf("%lld\n", ans);
    // }
    return 0;
}


Measured memory_bytes: 384
from collections import deque

S = deque(input())
Q = int(input())

d = 1
c = 1
for i in range(Q):
    que = list(input().split())
    if que[0] == str(1):
        d += c
        c *= -1
    else:
        if (int(que[1]) ^ d) == 0:
            S.appendleft(que[2])
        else:
            S.append(que[2])

print(''.join(S) if d == 1 else ''.join(S)[::-1])


Measured memory_bytes: 8436
from bisect import bisect
n = int(input())
P = [list(map(int, input().split())) for i in range(n)]

M = 10**5+1

def policy1(P):
    A = [a for a, b in P]
    B = [b for a, b in P]
    A.sort(); B.sort()
    ans = 1
    for a, b in P:
        left = bisect(B, a)
        right = n - bisect(A, b-1)
        ans = max(ans, n - (left + right))
    return ans

def policy2(P):
    D = [0]*M
    for a, b in P:
        D[a] += 1
        D[b] -= 1
    for i in range(1, M):
        D[i] += D[i-1]
    return max(D)

print(policy1(P), policy2(P))

Measured memory_bytes: 44344
n = int(input())
a = list(map(int,input().split()))
ans = "YNeos"
for i in range(n):
  a[i] = (2 if a[i] % 4 == 0 else
          1 if a[i] % 2 == 0 else
          0)
a0 = a.count(0)
a1 = a.count(1)
a2 = a.count(2)
if a0-a2 >= 2:
  print(ans[1::2])
elif a0-a2 == 1:
  if a1 == 0:
    print(ans[::2])
  else:
    print(ans[1::2])
else:
  print(ans[::2])

Measured memory_bytes: 62576
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> monsters(n);
    for(int i=0;i<monsters.size();i++){
        cin>>monsters[i];
    }
    int min=monsters[0];
    
    for(int i=0;i<monsters.size();i++){
        min=__gcd(min,monsters[i]);
    }
    cout<<min<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N), F(N);
    cin >> A >> F;
    sort(all(A));
    sort(all(F));
    
    auto check = [&](int L) -> bool {
        int r = K;
        int idx = 0;
        rrep(i, 0, N) {
            int a = A[idx++];
            int f = F[i];
            if (a * f > L) {
                int d = (a * f - L + f - 1) / f;
                r -= d;
            }
        }
        if (r < 0) {
            return false;
        }
        return true;
    };

    int ok = A.back() * F.back();
    int ng = -1;
    while (abs(ok - ng) > 1) {
        int k = (ok + ng) / 2;
        if (check(k)) ok = k;
        else ng = k;
    }
    cout << ok << endl;
    return (0^_^0);
}



Measured memory_bytes: 3456
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x)  ((int)x.size ())
#define all(x) (x).begin(), (x).end()
#define re return
#define mp make_pair
#define sqrt(x) sqrt (abs(x))
#define y0 y3451
#define y1 y4562
#define j0 j25624
#define j1 j45624
#define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())

typedef pair <int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef double D;
typedef long double ld;
typedef unsigned int uint;
typedef vector <string> vs;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <vi> vvi;

template <class T> using _tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

#define filename ""

const D pi = acos(-1.);
const int N = 2e5 + 20;
const int inf = 1e9 + 7;

int mod = inf;
ii a[N];
ll dp[3010];

ll power(ll x, ll y = mod - 2) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % mod;
		y /= 2;
		x = x * x % mod;
	}
	re ans;
}
ll f[N], rev[N];
int w, h;

ll cnk(int n, int k) {
    ll ans = f[n] * rev[k] % mod;
    re ans * rev[n - k] % mod;
}
int n, m;

int main() {
	cin >> w >> h >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[i] = {x - 1, y - 1};
	}
	a[n] = {w - 1, h - 1};
	n++;
	sort(a, a + n);
	f[0] = rev[0] = 1;
	for (int i = 1; i <= w + h; i++) {
		f[i] = f[i - 1] * i % mod;
		rev[i] = power(f[i]);
	}
	for (int i = 0; i < n; i++) {
		dp[i] = cnk(a[i].fi + a[i].se, a[i].fi);
		for (int j = 0; j < i; j++)
			if (a[i].fi >= a[j].fi && a[i].se >= a[j].se)
				dp[i] = (mod + dp[i] - cnk(a[i].fi - a[j].fi + a[i].se - a[j].se, a[i].fi - a[j].fi) * dp[j] % mod) % mod;
	}
	cout << dp[n - 1];
}

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

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T a, b;
  T best;

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

using int64 = long long;


template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(g.size(), INF);

  using Pi = pair< T, int >;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      int64 next_cost = cost + (e.b + (cost + e.a - 1)) / (cost + e.a);
      for(int64 i = max(e.best - 3, cost); i <= e.best + 3; i++) {
        next_cost = min(next_cost, i + (e.b + (i + e.a - 1)) / (i + e.a));
      }
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      que.emplace(dist[e.to], e.to);
    }
  }
  return dist;
}

int main() {
  int N, M, S, G;
  cin >> N >> M >> S >> G;
  WeightedGraph< int64 > g(N);
  for(int i = 0; i < M; i++) {
    int a, b;
    int64 c, d;
    cin >> a >> b >> c >> d;
    --a, --b;
    g[a].emplace_back((edge< int64 >) {-1, b, c, d});
    g[b].emplace_back((edge< int64 >) {-1, a, c, d});
    g[a].back().best = sqrt(d) - c;
    g[b].back().best = sqrt(d) - c;
  }
  auto s = dijkstra(g, S - 1)[G - 1];
  if(s >= numeric_limits< int64 >::max()) cout << -1 << endl;
  else cout << s << endl;
}




Measured memory_bytes: 31828
def showrooms(building,floor,rooms):
    for x in xrange(0,floor):
        for y in xrange(0,rooms):
            if y==0:
                print "",
                print building[x][y],
            elif y ==rooms-1:
                print building[x][y]
            else:
                print building[x][y],
FLOOR = 3
ROOMS = 10
n = input()
building1 = [[0 for i in range(ROOMS)] for j in range(FLOOR)]
building2 = [[0 for i in range(ROOMS)] for j in range(FLOOR)]
building3 = [[0 for i in range(ROOMS)] for j in range(FLOOR)]
building4 = [[0 for i in range(ROOMS)] for j in range(FLOOR)]
# for x in xrange(0,n):
for x in xrange(0,n):
    b,f,r,v = map(int,raw_input().split())
    f=f-1
    r=r-1
    if b==1:
        building1[f][r] += v
    elif b==2:
        building2[f][r] += v
    elif b==3:
        building3[f][r] += v
    elif b==4:
        building4[f][r] += v
    else:
        print "your input is invalid format."
        break
showrooms(building1,FLOOR,ROOMS)
print "####################"
showrooms(building2,FLOOR,ROOMS)
print "####################"
showrooms(building3,FLOOR,ROOMS)
print "####################"
showrooms(building4,FLOOR,ROOMS)

Measured memory_bytes: 6484
#include <stdio.h>
#include <string.h>
#define max(a,b) ((a)>(b)?(a):(b))

int main() {
  int n;
  scanf("%d", &n);
  while(n--) {
    int ls, lt;
    char s[1006], t[1006];
    int dp[1006][1006];
    int i, j;
    scanf("%s", s);
    scanf("%s", t);
    ls = strlen(s);
    lt = strlen(t);
    for(i = 0; i <= ls; ++i) {
      for(j = 0; j <= lt; ++j) {
        dp[i][j] = 0;
        if(i) dp[i][j] = max(dp[i][j], dp[i-1][j]);
        if(j) dp[i][j] = max(dp[i][j], dp[i][j-1]);
        if(i && j)
          dp[i][j] = max(dp[i][j], dp[i-1][j-1] + (s[i-1]==t[j-1]));
      }
    }
    printf("%d\n", dp[ls][lt]);
  }
}

Measured memory_bytes: 4356
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Long n;
        HashSet<String> sName = new HashSet<String>();  
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        for(int i = 0; i < n; i++){
            sName.add(sc.next());
        }
        System.out.println(sName.size());
    }
}

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


int main() {
  int N,M;
  while(true){
      cin>>N>>M;
      if(N==0&&M==0)break;
      pair<bool,int> use[N+1][722];
      rep(i,N+1){rep(j,722){use[i][j]={false,0};}}

      int r;
      cin>>r;

      rep(i,r){
          int t,a,b,c;
          cin>>t>>a>>b>>c;
          t-=540;
          if(c==1){
              use[a][t]={true,b};
          }else {
              int k = t;
              k--;
              while (k >= 0 && (use[a][k].first != true && use[a][k].second != b)) {
                  use[a][k] = {true, b};
                  k--;
              }
          }
      }
      int q;
      cin>>q;

      rep(i,q){
          bool aaa[722];
          rep(i,722)aaa[i]=false;
          int str,las,cl;
          cin>>str>>las>>cl;
          int ans=0;
          str-=540;las-=540;
          for(int j=1;j<=N;j++){
              for(int kk=str;kk<las;kk++){
                  if(use[j][kk].first==true&&use[j][kk].second==cl)aaa[kk]=true;
              }
          }
          for(int l=str;l<las;l++){if(aaa[l]==true)ans++;}
      cout<<ans<<endl;
      }



  }
    return 0;

}


Measured memory_bytes: 8556
#include <iostream>
#include <string>
using namespace std;
void RunLength(string s) {
  int i = 0;
  while(i < (int)s.length()) {
	if(s[i] == '@') {
	  for(int j = 0; j < (s[i + 1] - '0'); ++j) {
		cout << s[i + 2];
	  }
	  i += 3;
	}
	else {
	  cout << s[i++];
	}
  }
  cout << endl;
}
int main() {
  string buf;
  while(cin >> buf) {
	RunLength(buf);
  }
  return 0;
}

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

int main() {
vector<char> S(4);
  int A=0;
  for(int i=0; i<4; i++){
    cin>>S.at(i);
    if(S.at(i)=='+')
      A++;
      else  A--;
  }
  cout<<A<<endl;
}
  

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

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define __ fflush(stdout)
#define FILENAME ""

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef LOCAL
		freopen(".in", "r", stdin);
		freopen("1.out", "w", stdout);
	#else
		//freopen(FILENAME".in", "r", stdin);
		//freopen(FILENAME".out", "w", stdout);
	#endif
}

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 200500, inf = 1e9 * 2;

const ll MOD = 1e9 + 7ll, INF = 1e18;

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

int dp[N][2];

vector<int> g[N];

void add(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

void dfs(int v, int pr = 0) {
	for (auto u : g[v]) {
		if (u == pr) continue;
		dfs(u, v);
	}
	dp[v][0] = dp[v][1] = 1;
	for (auto u : g[v]) {
		if (u == pr) continue;
		dp[v][0] = (dp[v][0] * 1ll * (dp[u][1] + dp[u][0])) % MOD;
		dp[v][1] = (dp[v][1] * 1ll * dp[u][0]) % MOD;
	}
}

int main() {
	FREOPEN();
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1);
	add(dp[1][0], dp[1][1]);
	printf("%d", dp[1][0]);
	return 0;
}


Measured memory_bytes: 16512
/* be name khoda */

#define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

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

const ll maxn = 200010;

ll n;
ll A[maxn], B[maxn];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // ifstream cin(".in");

    cin >> n;
    fori (i, n - 1) {
        cin >> A[i] >> B[i];
    }
    ll ans = 0;
    fori (i, n) {
        ans += (n - i) * (i + 1);
    }
    fori (i, n - 1) {
        if (A[i] > B[i]) swap(A[i], B[i]);
        ans -= A[i] * (n - B[i] + 1);
    }
    cout << ans << '\n';

}


Measured memory_bytes: 6756
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <math.h>

#define ll long long
#define ull unsigned long long

using namespace std;

const int inf = 1000000000;
const double eps = 1e-7;

void solve() {
	int r;
	cin >> r;
	cout << fixed << setprecision(7) << 2 * acos(-1.0) * r << endl;
}

int main() {
	int t = 1;
	//cin >> t;
	for (int i = 0; i < t; ++i)
		solve();
	return 0;
}

Measured memory_bytes: 3784
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
        sc.close();

        long firstDivisible;
        if(a % x == 0){
            firstDivisible = a;
        }else{
            firstDivisible = a + x - (a % x);
        }

        long lastDivisible = b - (b % x);
        if(b % x == 0){
            lastDivisible = b;
        }else{
            lastDivisible = b - (b % x);
        }

        long count = 0L;
        if(firstDivisible <= lastDivisible){
            count = (lastDivisible - firstDivisible) / x + 1;
        }
        System.out.println(count);
    }

}


Measured memory_bytes: 23124