akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;

    vector<ll> a(3*N);
    rep (i, 3*N) {
        cin >> a[i];
    }

    sort(a.rbegin(), a.rend());

    ll ans = 0;
    for (ll i = 0; i < N; i++) {
        ans += a[2*i+1];
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define  mem(a,x) memset(a,x,sizeof(a));
#define  ft  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define  ll  long long
#define  pi  pair<int,int>
#define  pb  push_back
#define  F   first
#define  S   second
#define  B   begin()
#define  E   end()
const int N=1e5+3;
vector<int>v[N];
int vis[N];
void dfs(int f)
{
    vis[f]=1;
    for(int x:v[f])
    {
        if(vis[x]==-1)
        {
            dfs(x);
        }
    }
}
int main()
{
    ft
    int t,i,j,n,m,l,r;
    cin>>n>>m;
    mem(vis,-1);
    for(i=0;i<m;i++)
    {
        cin>>l>>r;
        v[l].pb(r);
        v[r].pb(l);
    }
    l=0;
    for(i=1;i<=n;i++)
    {
        if(vis[i]==-1)
        {
            l++;
            dfs(i);
        }
    }
    cout<<l-1<<"\n";
    return 0;
}



Measured memory_bytes: 9956
n, x, y = map(int, input().split())
x, y = x-1, y-1

dist = [0] * n

for i in range(n):
    for j in range(i+1, n):
        dist[min(j-i, abs(y-j) + abs(x-i) + 1)] += 1

for k in range(1, n):
    print(dist[k])


Measured memory_bytes: 3444
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
 
using namespace std;
 
 
 
int main() {
    
    long long int n, k;
    map<long long int, long long int> dic;
    cin >> n >> k;
    long long int temp;
    long long int dbl;//ダブり
    vector<long long int> a;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        a.push_back(temp);
    }
    vector<long long int> arr;
    vector<long long int> mloop;
    dic[1]++;
    arr.push_back(1);
    temp = 1;
    while (true)
    {
        temp = a[temp-1];
        
        auto itr = dic.find(temp);        // "xyz" が設定されているか？
        if (itr != dic.end()) {
            dbl = temp;
 
            while (true)
            {
                mloop.push_back(temp);
                temp = a[temp - 1];
                if (temp == dbl)break;
            }
 
            break;
        } else {
            dic[temp]++;
            arr.push_back(temp);
        }
 
        //dic[temp]++;
    }
    //cout << arr.size() << "\n";
    //cout << mloop.size();
    long long int sa = arr.size() - mloop.size();
 
 
    if (sa == 0) {
        cout << arr[k % arr.size()];
        return 0;
    }
 
    long long int temp2 = (k - sa) % mloop.size();
    temp2 %= mloop.size();
    if (k-1 <= arr.size() - mloop.size()) {
        cout << arr[k];
    } else {
        cout << mloop[temp2];
    }
    
    
 
 
 
 
    return 0;
}

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

int main(){
	int x,y;
	cin >> x >> y;
	while(!(x==0&&y==0)){
		if(x<y) cout << x << " " << y << endl;
		else cout << y << " " << x << endl;
		cin >> x >> y;
	}
	return 0;
}


Measured memory_bytes: 3084
fun main(args: Array<String>){
    val N = readLine()!!.split(" ").map(String::toInt)
    val n = N[0]
    val d = N[1]
    if (n % (2*d + 1) == 0) println(n / (2*d + 1)) else println(n/(2*d + 1) + 1)
}

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

public class Main {

    private static Scanner sc;
    private static int[][] neg8 = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
    private static int[][] neg4 = new int[][]{{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

    public static void main(String[] args) {
        Main instance = new Main();
        sc = instance.new Scanner();
        instance.solve();
    }

    private void solve() {
        try {
            int M = sc.nextInt();
            int D = sc.nextInt();
            int ans = M - 1;
            if (D >= M) ans++;
            System.out.println(ans);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private class Scanner {
        String[] s;
        int i;
        BufferedReader br;
        String regex = " ";

        public Scanner() {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        @Override
        protected void finalize() throws Throwable {
            try {
                super.finalize();
            } finally {
                destruction();
            }
        }

        private void destruction() throws IOException {
            if (br != null) br.close();
        }

        public String next() throws IOException {
            if (i < s.length) return s[i++];
            String st = br.readLine();
            while (st == "") st = br.readLine();
            s = st.split(regex, 0);
            i = 0;
            return s[i++];
        }

        public int nextInt() throws NumberFormatException, IOException {
            return Integer.parseInt(next());
        }

        public Long nextLong() throws NumberFormatException, IOException {
            return Long.parseLong(next());
        }

        public Double nextDouble() throws NumberFormatException, IOException {
            return Double.parseDouble(next());
        }
    }

    private static double distance(int x1, int x2, int y1, int y2) {
        return Math.sqrt((Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
    }

    private static boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        boolean swap = false;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
            swap = true;
        }
        reverse(nums, i + 1);
        return swap;
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}



Measured memory_bytes: 21076
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int main(){

  int N, R, G, B;
  cin >> R >> G >> B >> N;

  int cnt = 0;
  for(int i=0;R*i<=N;i++){
    for(int j=0;R*i+G*j<=N;j++){
      if((N-R*i-G*j)%B==0) cnt++;
    }
  }
  cout << cnt <<endl;
  
  return 0;
}

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

int main()
{	
	long long a, b, c;
	scanf("%lld %lld.%lld", &a, &b, &c);

	cout << (long long) (a * (b * 100 + c) / 100) << '\n';
	return 0;
}

Measured memory_bytes: 3772
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 0, cnt = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		cnt += x == i;
		if(x != i) {
			ans += (cnt + 1) / 2;
			cnt = 0;
		}
	}
	ans += (cnt + 1) / 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N (100010)
#define MD (1000000007)
int n,ans,a[N],f[N];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",a+i),f[a[i]]++;
	if (n&1){
		if (f[0]!=1) ans=0; else ans=1;
		for (int i=2;i<n;i+=2){
			if (f[i]!=2){
				ans=0;
				break;
			}
			else {
				ans=ans*2%MD;
			}
		}
	}
	else {
		ans=1;
		for (int i=1;i<n;i+=2){
			if (f[i]!=2){
				ans=0;
				break;
			}
			else {
				ans=ans*2%MD;
			}
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 1024
# B

N = int(input())
S = []
for _ in range(N):
    S.append(list(input()))


def is_good(S):
    # T = []
    # for j in range(N):
    #     ls = []
    #     for i in range(N):
    #         ls.append(S[i][j])
    #     T.append(ls)
    T = list(map(list, zip(*S)))

    if T == S:
        return True
    else:
        return False


ans = 0
for a in range(N):
    T = []
    for i in range(N):
        T.append(S[(i+a) % N])
    if is_good(T):
        ans += N

print(ans)


Measured memory_bytes: 4708
D, G = map(int, input().split())
cp = [[] for i in range(D)]
ans = []

for i in range(D):
    c, p = map(int, input().split())
    cp[i] = [c, p]
    
for j in range(2**D):
    check = 0
    con = 0
    rest = -1
    for i in range(D):
        p, c = cp[i]
        if (j & 1<<i):
            
            check += p * 100 * (i + 1) + c
            con += p
        else:
            rest = i

    if G <= check:
        ans.append(con)
    else:
        p1 = 100 * (rest + 1)
        pn = cp[rest][0] -1
        for i in range(pn + 1):
            if G <= check + p1 * i:
                ans.append(con + i)
                break
        
print(min(ans))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;
    // for sum of [a, b), just calc sum[a]-sum[b]
    vector<long long> as(N);
    vector<long long> sum(N+1, 0);
    for(int i = 0; i < N; ++i) {
        cin >> as[i];
    }
    for(int i = N-1; i >= 0; --i) {
        sum[i] = sum[i+1] + as[i];
    }

    // dp[始点][終点] = [始点, 終点)を一つにしたとき，[0,終点)での最長増加列長
    vector<vector<int> > dp(N+1, vector<int>(N+1, numeric_limits<int>::min())), prev(N+1, vector<int>(N+1, numeric_limits<int>::min()));
    for(int right = 1; right <= N; ++right) {
        dp[0][right] = 1;
    }
    for(int cur = 1; cur < N; ++cur) {
        // 点curから始まる系列[cur, next)を考える．
        vector<pair<long long,int> > nums;
        // 点curから始まる系列を与え得る直前の状態を列挙する．
        for(int prev_i = 0; prev_i < cur; ++prev_i) {
            nums.push_back(make_pair(sum[prev_i] - sum[cur], -prev_i));
        }
        // 点curから始まる系列が到達し得る状態を列挙する．
        for(int right = cur+1; right <= N; ++right) {
            nums.push_back(make_pair(sum[cur] - sum[right], -right));
        }
        sort(nums.begin(), nums.end());
        int best = numeric_limits<int>::min();
        int best_prev = -1;
        for(vector<pair<long long,int> >::iterator it = nums.begin(); it != nums.end(); ++it) {
            int pos = -it->second;
            if(pos < cur) {
                if(best < dp[pos][cur]) {
                    // これより先，[pos,cur)から接続するのが最も効率が良い．
                    best = dp[pos][cur];
                    best_prev = pos;
                }
            } else if(pos > cur) {
                if(dp[cur][pos] < best+1) {
                    dp[cur][pos] = best+1;
                    prev[cur][pos] = best_prev;
                    //cout << cur << ' ' << pos << ' ' << dp[cur][pos] << endl;
                }
            }
        }
    }
    {
        // Nを終点とするDP表から最良の始点を選ぶ．
        int cur = -1;
        int best = 0;
        for(int left = 0; left < N; ++left) {
            if(dp[left][N] > best) {
                best = dp[left][N];
                cur = left;
            }
        }
        // 経路復元
        vector<int> checkpoint;
        int prev_cur = N;
        while(cur > 0) {
            checkpoint.push_back(cur);
            int next = prev[cur][prev_cur];
            prev_cur = cur;
            cur = next;
        }
        sort(checkpoint.begin(), checkpoint.end());
        cout << checkpoint.size()+1 << endl;
        for(vector<int>::iterator it = checkpoint.begin(); it != checkpoint.end(); ++it) {
            if(it != checkpoint.begin()) cout << ' ';
            cout << *it;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 126716
import collections
from bisect import bisect_right
d=collections.defaultdict(list)
s=input()
t=input()
for i,S in enumerate(s,1):
    d[S].append(i)
k=0
ans=0
for i in t:
    l=d[i]
    if len(l)==0:
        print(-1)
        quit()
    if l[-1]<=ans:
        ans=l[0]
        k+=1
    else:
        ans=l[bisect_right(l,ans)]
print(len(s)*k+ans)

Measured memory_bytes: 7924
#include<bits/stdc++.h>
using namespace std;
int main(){
	char s[10010],t[10010];
	scanf("%s%s",s,t);
	int ls=strlen(s),lt=strlen(t);
	for(int i=ls-lt;i>=0;i--){
		if(s[i]==t[0]||s[i]=='?'){
			bool flag=true;
			for(int j=0;j<lt;j++){
				if(t[j]!=s[j+i]&&s[j+i]!='?'){
					flag=false;
					break;
				}
			}
			if(flag==true){
				for(int j=0;j<lt;j++)s[j+i]=t[j];
				for(int j=0;j<ls;j++){
					if(s[j]=='?')cout<<'a';
					else cout<<s[j];
				}
				return 0;
			}
		}
	}
	cout<<"UNRESTORABLE";
	return 0;
} 

Measured memory_bytes: 3648
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: "List[List[int]]", N: int, b: "List[int]"):
    tf = [[False, False, False], [False, False, False], [False, False, False]]
    for num in b:
        for i in range(3):
            for j in range(3):
                tf[i][j] |= A[i][j] == num

    bingo = True
    for i in range(3):
        for j in range(3):
            bingo &= tf[i][j]
        if bingo:
            print(YES)
            return
        else:
            bingo = True

    bingo = True
    for j in range(3):
        for i in range(3):
            bingo &= tf[i][j]
        if bingo:
            print(YES)
            return
        else:
            bingo = True

    bingo1 = True
    bingo2 = True
    for i in range(3):
        bingo1 &= tf[i][i]
        bingo2 &= tf[i][2-i]

    if bingo1 or bingo2:
        print(YES)
        return
    else:
        print(NO)
        return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = [[int(next(tokens)) for _ in range(3)] for _ in range(3)]  # type: "List[List[int]]"
    N = int(next(tokens))  # type: int
    b = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(A, N, b)

if __name__ == '__main__':
    main()


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

int main()
{
	string s;
	while (getline(cin, s), s != "0") {
		int res = 0;
		for (char c : s) {
			res += c - '0';
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int64_t powMod(int64_t m, int64_t n) {
    if (n == 0) return 1;
    int64_t ret = powMod(m, n / 2);
    if (n % 2 == 0) {
        return (ret * ret) % MOD;
    } else {
        return (((ret * ret) % MOD) * m) % MOD;
    }
}

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

    int64_t m, n;
    cin >> m >> n;

    cout << powMod(m % MOD, n) << endl;

    return 0;
}



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

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	
	for(int i=0;i<=b;i++){
		if(a*i%b==c){
		 cout<<"YES";
		 return 0;
		}
	}

	cout<<"NO";

}

Measured memory_bytes: 256
n, x = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
pos = -1
for i in range(0, n):
    x -= a[i]
    if x < 0:
        pos = i
        break
if pos == -1 and x > 0:
    print(n - 1)
elif x == 0:
    print(n)
else:
    print(pos)

Measured memory_bytes: 9196
import java.io.*;

class Main {
	public static void main(String[] args) {
		BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
		try {
		
			int[] nx= new int[5];
			int count=0;
			String[] tmpArray;	
			while( true ) {
				String str = kb.readLine();
				tmpArray = str.split( " " );
				if( "0".equals( tmpArray[0] ) && "0".equals( tmpArray[1] ) ) {
					break;
				}
				for( int i=0; i<2; i++ ) {
					nx[i]=Integer.parseInt( tmpArray[i] );
				}
				
				count=0;
				for( int i=1; i<=nx[0]-2; i++ ) {
					for( int j=i+1; j<=nx[0]-1; j++ ) {
						for( int k=j+1; k<=nx[0]; k++ ) {
							if( nx[1] == (i+j+k) ) {
								count++;
							}
						}
					}				
				}
				System.out.println( count );	
			}
		} catch( IOException e ) {
			System.err.println( e );
		}
	}
}

Measured memory_bytes: 19516
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000000;
const long long MOD = 1000000007;

bool f(long long N){
  string s = to_string(N);
  long long slen = s.length();
  slen--;
  for (int i = 0; i < s.length(); i++)
  {
    if(s[i]!=s[slen-i])
      return false;
  }
  return true;
}

int main()
{
  long long X;
  cin >> X;
  long long ans = 1;
  for (int i = 2; i <= X; i++)
  {
    long long N = i;
    while(N*i<=X){
      N *= i;
      ans = max(N, ans);
    }
  }
  cout << ans << endl;
}


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

int main()
{
  int N;
  cin >> N;
  
  int ret = 0, trail = 0;
  for (int i = 1;i <= N; i++) {
    	int a;
    cin >> a;
    if (a == i) {
      	trail++;
    } else {
      ret += ++trail / 2;
      	trail = 0;
    }
  }
  ret += ++trail / 2;
  cout << ret << endl;
};

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

class UnionFind {
public:
	vector <int> par;  // 各元の親を表す配列
	vector <int> rank; // 素集合のランクを表す配列(0 で初期化)

	UnionFind(int n) : par(n), rank(n) {
		init(n);
	}

	void init(int n) {
		par.resize(n); for (int i = 0; i < n; ++i) par[i] = i;
		rank.assign(n, 0);
	}

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

	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) {
			par[x] = y;
		}
		else { // rank[y] < rank[x]
			par[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
		return true;
	}

	bool isSame(int x, int y) { // 連結判定
		return root(x) == root(y);
	}

	int getRank(int x) {        // 素集合のランク
		return rank[root(x)];
	}
};

int main() {

	int n, m; cin >> n >> m;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p[i]--;
	}
	UnionFind uf(n);
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		x--;
		y--;
		uf.unite(x, y);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (uf.isSame(p[i], i)) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4168
# coding: utf-8

A, B, C = list(map(int, input().split(" ")))
K = int(input())

while not(A < B):
    B *= 2
    K -= 1

while not(B < C):
    C *= 2
    K -= 1

if K < 0:
    print("No")
else:
    print("Yes")



Measured memory_bytes: 9164
#include<stdio.h>

int main(){
int H,W,i,j;

while(1){
  scanf("%d %d",&H,&W);
  if(H == W && H == 0){
    break;
    }else{
      for(j = 0; j < H; j++){
        if(j % 2== 0){

          for(i = 0; i < W; i++){
            if(i % 2== 0){

            printf("#");
            }else{

            printf(".");
            }
          }
        printf("\n");
        }else{

          for(i = 0; i < W; i++){
            if(i % 2== 0){

            printf(".");
            }else{

            printf("#");
            }
          }
        printf("\n");
        }
        }
    }
     printf("\n");
}
return 0;
}



Measured memory_bytes: 1984
<?php
$judges = [
  'AC' => 0,
  'WA' => 0,
  'TLE' => 0,
  'RE' => 0,
];
while ( ! feof(STDIN) ) {
  $line = trim(fgets(STDIN));
  if (isset($judges[$line])) {
    $judges[$line]++;
  }
}
foreach($judges as $judge => $count) {
  echo "$judge x $count\n";
}

Measured memory_bytes: 16256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<vector<int>> color;

void dfs(int prev, int now, int remain, int c) {
    for (int i = remain; i >= 0 && color[now][i] == 0; i--) color[now][i] = c;

    if (remain == 0)return;
    for (auto next:graph[now]) {
        if (next == prev || color[next][remain - 1] != 0)continue;
        dfs(now, next, remain - 1, c);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b, a--, b--;
        graph[a].push_back(b), graph[b].push_back(a);
    }

    int q;
    cin >> q;
    vector<vector<int>> operation(q);
    for (int i = 0; i < q; i++) {
        int v, d, c;
        cin >> v >> d >> c, v--;
        operation[i] = {v, d, c};
    }
    reverse(operation.begin(), operation.end());

    color.assign(n, vector<int>(11));
    for (auto x:operation) {
        if (color[x[0]][x[1]] != 0)continue;
        dfs(-1, x[0], x[1], x[2]);
    }

    for (int i = 0; i < n; i++)cout << color[i][0] << endl;
    return 0;
}

Measured memory_bytes: 20600
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();

        int taxA = 0;
        int taxB = 0;
        long n = 1;
        while(taxA <= A && taxB <= B){
            taxA = (int) Math.floor(n * 0.08);
            taxB = (int) Math.floor(n * 0.10);
            if(taxA == A && taxB == B){
                System.out.println(n);
                return;
            }
            n++;
        }
        System.out.println(-1);
    }
}

Measured memory_bytes: 22868
from math import *
from itertools import combinations_with_replacement
ls = []
n, m, q = map(int, input().split())
for i in range(1, m+1):
	ls.append(i)
A = []
B = []
C = []
D = []
for i in range(q):
	a, b, c, d = map(int, input().split())
	A.append(a)
	B.append(b)
	C.append(c)
	D.append(d)
all_possible = list(combinations_with_replacement(ls, n))
max_score = 0
for each_comb in all_possible:
	combi = list(each_comb)
	score = 0
	for i in range(q):
		if combi[B[i]-1]-combi[A[i]-1] == C[i]:
			score += D[i]
	max_score = max(max_score, score)
print(max_score)

Measured memory_bytes: 85056
# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    a = int(lines[0])
    

    return (a, )


def solve(a):

    result = a + a*a + a*a*a

    return result
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

Measured memory_bytes: 61964
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	for (auto &t : a) {
		cin >> t;
	}
	for (auto &t : b) {
		cin >> t;
	}
	vector<int> ind(n);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.begin(), ind.end(), [&](int i, int j) {
		return make_pair(b[i], a[i]) < make_pair(b[j], a[j]);
	});
	{
		vector<int> na = a;
		for (int i = 0; i < n; i++) {
			na[i] = a[ind[i]];
		}
		a = na;
		sort(b.begin(), b.end());
	}
	// for (auto t : a) {
	// 	cerr << t << ' ';
	// }
	// cerr << endl;
	// for (auto t : b) {
	// 	cerr << t << ' ';
	// }
	// cerr << endl;
	{
		vector<int> na = a;
		sort(na.begin(), na.end());
		for (int i = 0; i < n; i++) {
			if (na[i] > b[i]) {
				cout << "No\n";
				return 0;
			}
		}
	}
	{
		vector<int> aind(n);
		iota(aind.begin(), aind.end(), 0);
		sort(aind.begin(), aind.end(), [&](int i, int j) {
			return a[i] < a[j];
		});
		vector<int> us(n);
		int c = 0;
		for (int i = 0; i < n; i++) {
			if (!us[i]) {
				c++;
				int cur = i;
				while (!us[cur]) {
					us[cur] = 1;
					cur = aind[cur];
				}
			}
		}
		if (c >= 2) {
			cout << "Yes\n";
			return 0;
		}
	}
		{
		vector<int> na = a;
		sort(na.begin(), na.end());
		for (int i = 0; i + 1 < n; i++) {
			if (na[i + 1] <= b[i]) {
				cout << "Yes\n";
				return 0;
			}
		}
	}
	cout << "No\n";
}


Measured memory_bytes: 2184
#include <iostream>

int main() {
  int a, b;
  std::cin >> a >> b;

  if (a < b) {
    std::cout << "a < b" << std::endl;
  } else if (a > b) {
    std::cout << "a > b" << std::endl;
  } else {
    std::cout << "a == b" << std::endl;
  }
}



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

const int MXN = 100005;
int arr[MXN];

int co(int a, int b) {
	return abs(arr[a] - arr[b]);
}

int main() {
	
	int n;
	cin >> n;
	
	arr[0] = 0;
	for (int i=0; i<n; i++) cin >> arr[i+1];
	arr[n+1] = 0;
	
	int tc = 0;
	for (int i=0; i<=n; i++) {
		tc += co(i, i+1);
	}
	
	for (int skip=1; skip<=n; skip++) {
		
		int br = co(skip-1, skip+1);
		int at = co(skip-1, skip) + co(skip, skip+1);
		cout << tc - at + br << endl;
		
	}
	
}


Measured memory_bytes: 1664
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
What do you think? What do you think?
1st on Billboard, what do you think of it
Next is a Grammy, what do you think of it
However you think, I’m sorry, but shit, I have no fcking interest
*******************************
I'm standing on top of my Monopoly board
That means I'm on top of my game and it don't stop
til my hip don't hop anymore
https://www.a2oj.com/Ladder16.html
*******************************
Shining through the city with a little funk and soul
*******************************
300iq as writer = Sad!
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      static final long MOD = 1000000007L;
      public static void main(String hi[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         long[] fac = new long[N+1];
         long[] invfac = new long[N+1];
         fac[0] = invfac[0] = 1L;
         for(int i=1; i <= N; i++)
            fac[i] = (fac[i-1]*i)%MOD;
         invfac[N] = power(fac[N], MOD-2, MOD);
         for(int i=N-1; i >= 1; i--)
            invfac[i] = (invfac[i+1]*(i+1))%MOD;
         long res = 0L;
         long temp = power(8, N-2, MOD);
         long over8 = power(8, MOD-2, MOD);
         for(int i=2; i <= N; i++)
         {
            long choice = power(2, i, MOD)-2;
            if(choice < 0)
               choice += MOD;
            choice = (choice*fac[N])%MOD;
            choice = (choice*invfac[i])%MOD;
            choice = (choice*invfac[N-i])%MOD;
            res += (temp*choice)%MOD;
            if(res >= MOD)
               res -= MOD;
            temp = (temp*over8)%MOD;
         }
         System.out.println(res);
      }
      public static long power(long x, long y, long p) 
      { 
         //0^0 = 1
         long res = 1L;      
         x = x%p;  
         while(y > 0) 
         { 
            if((y&1)==1) 
               res = (res*x)%p;
            y >>= 1;
            x = (x*x)%p;  
         } 
         return res; 
      } 
   }

Measured memory_bytes: 49448
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    int d, n;
    cin >> d >> n;
    if(d == 0) {
        if(n==100) cout << 101 << endl;
        else cout << n << endl;
    }else if(d == 1){
        if(n==100) cout << 10100 << endl;
        else cout << 100*n << endl;
    }else { //d==2
        if(n==100) cout << 1010000 << endl;
        else cout << 10000*n << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define LEN 20005

typedef struct {
    int idx;
    int area;
} S2;

int s1[LEN];
S2 s2[LEN];
int top1 = 0;
int top2 = 0;

void push1(int x) {
    s1[top1] = x;
    top1++;
}

int pop1(void) {
    top1--;
    return s1[top1];
}

void push2(int idx, int area) {
    s2[top2].idx = idx;
    s2[top2].area = area;
    top2++;
}

S2 pop2(void) {
    top2--;
    return s2[top2];
}

int main(void) {
    int i, j, a, tmp;
    char S[LEN];
    int sum = 0;
    scanf("%s", S);
    int n = strlen(S);
    for (i = 0; i < n; i++) {
        if (S[i] == '\\') push1(i);
        else if (S[i] == '/' && top1 > 0) {
            j = pop1();
            sum += i - j;
            a = i - j;
            while (top2 > 0 && s2[top2-1].idx > j) {
                a += pop2().area;
            }
            push2(j, a);
        }
    }
    tmp = top2;
    int ans[top2];
    for (i = top2 - 1; top2 > 0; i--) ans[i] = pop2().area;
    
    printf("%d\n%d", sum, tmp);
    for (i = 0; i < tmp; i++) printf(" %d", ans[i]);
    printf("\n");
    return 0;
}


Measured memory_bytes: 2112
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      h: usize,
      w: usize,
      mut aa: [[usize; w]; h]
    }


    let mut ans = vec![];
    for i in 0..h {
        for j in 0..w-1 {
            if aa[i][j]%2 == 1 {
                aa[i][j] -= 1;
                aa[i][j+1] += 1;
                ans.push( ((i,j), (i,j+1)) );
            }
        }
    }

    let j = w-1;
    for i in 0..h-1 {
        if aa[i][j]%2 == 1 {
            aa[i][j] -= 1;
            aa[i+1][j] += 1;
            ans.push( ((i,j), (i+1,j)) );
        }
    }
    puts!("{}\n", ans.len());
    for a in ans {
        puts!("{} {} {} {}\n", (a.0).0+1, (a.0).1+1, (a.1).0+1, (a.1).1+1);
    }
}


Measured memory_bytes: 13304
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>
#include <bitset>
#include <stack>

using namespace std;
typedef long long ll;

vector<vector<bool>> dpx, dpy;

int main() {
  string s;
  int x, y;
  cin >> s >> x >> y;
  vector<int> m;
  int n = 0;
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == 'T') {
      m.push_back(n);
      n = 0;
    } else {
      n++;
    }
  }
  if (n > 0) {
    m.push_back(n);
  }
  int l = (int)s.length();
  vector<int> mx, my;
  for (int i = 0; i < m.size(); i++) {
    if (i % 2) my.push_back(m[i]);
    else mx.push_back(m[i]);
  }
  
  dpy = vector<vector<bool>>(my.size() + 1, vector<bool>(l * 2 + 1, false));
  dpy[0][l] = true;
  for (int i = 0; i < my.size(); i++) {
    for (int j = 0; j <= 2 * l; j++) {
      if (dpy[i][j]) {
        dpy[i + 1][j + my[i]] = true;
        dpy[i + 1][j - my[i]] = true;
      }
    }
  }
  dpx = vector<vector<bool> >(mx.size() + 1, vector<bool> (2 * l + 1, false));
  dpx[1][l + mx[0]] = true;
  for (int i = 1; i < mx.size(); i++) {
    for (int p = 0; p <= 2 * l; p++) {
      if (dpx[i][p]) {
        dpx[i + 1][p + mx[i]] = true;
        dpx[i + 1][p - mx[i]] = true;
      }
    }
  }
  
  if (dpx[mx.size()][x + l] && dpy[my.size()][y + l]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 16128
matches:: Int -> Int -> [String]
matches a b = match 0 0
  where
    isDecided::Int -> Int -> Bool
    isDecided 6 4 = True
    isDecided 4 6 = True
    isDecided 5 5 = True
    isDecided n m
      |(n <= 3) && (m >= 5) = True
      |(m <= 3) && (n >= 5) = True
      |otherwise = False

    match :: Int -> Int -> [String]
    match n m
      |(n == a) && (m == b) = [""]
      |isDecided n m = []
      |(n > a) || (m > b) = []
      |otherwise = (map ('A':) (match (n + 1) m)) ++ (map ('B':) (match n (m + 1)))

main = do
  j:y:_ <- fmap (map read . words) getLine :: IO [Int]
  mapM_ putStrLn $ matches j y


Measured memory_bytes: 4072
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
 
ll line = (ll)pow(10, 18);
 
int main(){
  ll N;
  cin >> N;
  vl A(N);
  rep(i, N) cin >> A[i];
 
  stable_sort(A.begin(), A.end());
 
  if(A[0] == 0){
    cout << 0 << endl;
    return 0;
  }
 
  ll ans = 1;
  ll tmp;
 
  rep(i, N){
    if(ans > line / A[i]){
      cout << -1 << endl;
      return 0;
    }
 
    ans *= A[i];
  }
 
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; i++)
#define all(a) (a).begin(), (a).end()

int K;

const int INF = 1e9;
struct edge { int to, cost; };
struct node {
  int id, distance;
  node(int id, int distance): id(id), distance(distance) {}
  bool operator <(const node &theOther) const { return distance < theOther.distance; }
  bool operator >(const node &theOther) const { return distance > theOther.distance; }
};

vector<int> dijkstra(vector<vector<edge> > &G, int source) {
  int V = G.size();
  vector<int> distance(V, INF);
  priority_queue<node, vector<node>, greater<node> > que;
  distance[source] = 0;
  que.push(node(source, 0));

  while(!que.empty()) {
    node n = que.top(); que.pop();
    if(distance[n.id] < n.distance) continue;
    for(edge e : G[n.id]) {
      if (distance[e.to] > distance[n.id] + e.cost) {
        distance[e.to] = distance[n.id] + e.cost;
        que.push(node(e.to, distance[e.to]));
      }
    }
  }
  return distance;
}

int main () {
  cin >> K;

  vector<vector<edge>> G(K);
  rep(i,K) {
    G[i].push_back(edge{(i+1) % K, 1});
    G[i].push_back(edge{(i*10) % K, 0});
  }

  auto res = dijkstra(G, 1);
  cout << res[0] + 1 << endl;

  return 0;
}


Measured memory_bytes: 6780
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
#define SZ(v) int((v).size())
#define ALL(vec) (vec).begin(),(vec).end()
template<typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}
template<typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}
 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string>) {}
template<typename T1,typename T2> ostream& operator<<(ostream& os, pair<T1,T2> buf) {
  return os << "(" << buf.first << ": " << buf.second << ")"; }
#define DefOut(Con) template<typename T>ostream&operator<<(ostream&os,Con<T>&A){ bool f = false; os << "{"; \
  for (const auto e: A) { if (f) os << ", "; os << e; f = true; } return os << "}"; }
#define DefOut2(Con) template<typename K,typename V>ostream&operator<<(ostream&os,Con<K,V>&A) \
{ bool f = false; os << "{"; for (auto &e: A) { if (f) os << ", "; os << e; f = true; } return os << "}"; }
template<typename T>ostream &operator << (ostream &os,vector<vector<T>>& A) {
  for (auto &B: A) os << '\n' << B; return os; }
DefOut(vector) DefOut(set) DefOut(multiset) DefOut2(map) 
template<typename T,typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " =: " << a << endl; err(++it, args...); }
template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}
int const MOD = 1000000007;
long long const INF = 1e18;
#define PI 3.14159265358979323846
/***********************************************************************/

int32_t main() {

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, w;
  cin >> n >> w;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> b[i] >> a[i];
  }
  const int nax = 100001;
  int ans = 0;
  vector<int> dp(nax, MOD);
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int k = nax - 1; k >= a[i]; --k) {
      uin(dp[k], dp[k - a[i]] + b[i]);
      if (dp[k] <= w) uax(ans, k);
    }
  }
  kek(ans);
  
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const double PI = acos(-1);

typedef pair<ll, ll> P;
vector<P> VP;
int N, K;

ll check(int i, int j) {
	if ((j - i + 1) < K)return -1;
	vll PY;
	ll miny = 3e9;
	FOR(a, i, j + 1) {
		PY.push_back(VP[a].second);
	}
	so(PY);
	REP(a, SZ(PY)) {
		if (a + K - 1 >= SZ(PY))break;
		miny = min(miny, PY[a + K - 1] -  PY[a]);
	}
	return (VP[j].first - VP[i].first) * miny;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N >> K;
	VP = vector<P>(N);
	REP(i, N) {
		cin >> VP[i].first >>  VP[i].second;
	}
	so(VP);
	ll ans = 5e18;
	REP(j, N) {
		REP(i, j) {
			ll v = check(i, j);
			if (v == -1)continue;
			ans = min(ans, v);
		}
	}
	cout << ans << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <functional>

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

using namespace std;


int main(void) {
    int n,k,p[101]={};
    int dp[101][4][3]={};
    cin >> n >> k;
    REP(i,k){
        int a,b;
        cin >> a >> b;
        a--;
        p[a] = b;
    }
    if (p[0]==0){
        dp[0][1][1] = 1;
        dp[0][2][1] = 1;
        dp[0][3][1] = 1;
    }else{
        dp[0][p[0]][1] = 1;
    }
    FOR(i,1,n-1){
        if (p[i]==0){
            dp[i][1][1] = dp[i-1][2][1]+dp[i-1][3][1]+dp[i-1][2][2]+dp[i-1][3][2];
            dp[i][2][1] = dp[i-1][1][1]+dp[i-1][3][1]+dp[i-1][1][2]+dp[i-1][3][2];
            dp[i][3][1] = dp[i-1][1][1]+dp[i-1][2][1]+dp[i-1][1][2]+dp[i-1][2][2];
            dp[i][1][2] = dp[i-1][1][1];
            dp[i][2][2] = dp[i-1][2][1];
            dp[i][3][2] = dp[i-1][3][1];
        }else if (p[i]==1){
            dp[i][1][1] = dp[i-1][2][1]+dp[i-1][3][1]+dp[i-1][2][2]+dp[i-1][3][2];
            dp[i][1][2] = dp[i-1][1][1];
        }else if (p[i]==2){
            dp[i][2][1] = dp[i-1][1][1]+dp[i-1][3][1]+dp[i-1][1][2]+dp[i-1][3][2];
            dp[i][2][2] = dp[i-1][2][1];
        }else{
            dp[i][3][1] = dp[i-1][1][1]+dp[i-1][2][1]+dp[i-1][1][2]+dp[i-1][2][2];
            dp[i][3][2] = dp[i-1][3][1];
        }
        FOR(k,1,3) FOR(l,1,2) dp[i][k][l]%=10000;
    }
    
    int ans = (dp[n-1][1][1]+dp[n-1][1][2]+dp[n-1][2][1]+dp[n-1][2][2]+dp[n-1][3][1]+dp[n-1][3][2])%10000;
    cout << ans << endl;
    
    
    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#define pii pair<int,int> 
#define fi first
#define pb push_back
#define si second
#define int long long int
using namespace std;
int a[200005],s,vis[200005];
vector<int> v,u;
void dfs(int v)
{
	if(vis[v])
	{	
		s=v;
		
		return ;
	}
	vis[v]=1;
	dfs(a[v]);
}
void dfs1(int v)
{
	if(v==s)
		return ;
	u.pb(v);
	dfs1(a[v]);
}

int32_t main(){
	int n,k,i;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{	cin>>a[i];
		//mp[a[i]]=i;
	}
	dfs(1);
	i=1;
	while(i!=s)
	{	v.pb(i);
		i=a[i];
	}
	u.pb(s);
	dfs1(a[s]);
	/*for(auto x:u)
		cout<<x<<" ";
	cout<<"\n";
	
	for(auto x:v)
		cout<<x<<" ";
	cout<<"\n";*/
	if(k<v.size())
		cout<<v[k]<<"\n";
	else
	{
		k-=v.size();
		int sz=u.size();
		cout<<u[k%sz]<<"\n";
	}
		
	
	
	
	

}

Measured memory_bytes: 13536
#include <cstdio>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)


char buf[2][1010];
int main(void) {
  scanf("%s%s", buf[0], buf[1]);
  for(int i1 = 0, i2 = 0; buf[i1][i2]; ) {
    putchar(buf[i1][i2]);
    if(i1) {
      ++i2;
    }
    i1 ^= 1;
  }
  putchar('\n');
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif

int dp[3005][3005][2];

signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n; cin>>n;
    int arr[n];
    For(i, 0, n){
    	cin>>arr[i];
    	dp[i][i][1]=arr[i];
    	dp[i][i][0]=0;
    }
    int pre[n];
    pre[0]=arr[0];
    For(i, 1, n){
    	pre[i]=pre[i-1]+arr[i];
    }
    for(int len=1; len<n; len++){
    	for(int i=0; i<n-len; i++){
    		int j = i+len;
    		int tot = 0;
    		if(i==0)
    			tot = pre[j];
    		else
    			tot = pre[j]-pre[i-1];
    		dp[i][j][1]=max(dp[i][j-1][0]+arr[j], dp[i+1][j][0]+arr[i]);
    		dp[i][j][0]=tot-dp[i][j][1];
    	}
    }
    cout<<dp[0][n-1][1]-dp[0][n-1][0];
    return 0;
}





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

L = []
for i in range(N):
    x = list(input())
    x.sort()
    x = "".join(x)
    L.append(x)
    
from collections import Counter
L = Counter(L)
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for i in L:
    a = L[i]
    if a > 1:
        ans += combinations_count(a,2)
print(ans)

Measured memory_bytes: 68696
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def main():
    a, b = map(int, input().split())
    logging.info("Hello!")

    if a < b:
        if int(str(a) * a) < int(str(b) * a):
            print(str(a) * b)
        else:
            print(str(b) * a)
    else:
        if int(str(a) * b) < int(str(b) * b):
            print(str(a) * b)
        else:
            print(str(b) * a)
            
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin >> a >> b;
  int n = a * b;
  if(n % 2 == 0)
  {
    cout << "Even" << endl;
  }
  else
  {
    cout << "Odd" << endl;
  }
}


Measured memory_bytes: 3436