akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
using namespace std;

constexpr int mod = 998244353;
int fac[300001], inv[300001];
int a[300000];
int minx[300000], maxx[300000];

int solve(int n) {
    int n0 = count(a, a + n, 0);
    if (n0 == 0)
        return 0;
    if (n0 == n)
        return fac[n];

    if (a[0] != 0) {
        rotate(a, find(a, a + n, 0), a + n);
    } else {
        int j = 0;
        while (a[j] == 0)
            j++;
        // a[j] != 0
        rotate(a, a + (n - (n0 - j)), a + n);
    }

    if (find(a + n0, a + n, 0) != a + n)
        return 0;

    fill_n(minx, n, n);
    fill_n(maxx, n, -1);

    for (int i = 0; i < n; i++) {
        minx[a[i]] = min(minx[a[i]], i);
        maxx[a[i]] = max(maxx[a[i]], i);
    }

    int ans = 1, num = 0;
    for (int i = n - 1; i >= 1; i--) {
        num++;
        if (maxx[i] < minx[i])
            continue;
        if (count(a + minx[i], a + maxx[i] + 1, i)
                != maxx[i] - minx[i] + 1)
            return 0;

        int l = maxx[i] - (n0 - 1), r = minx[i];
        int ll = minx[i] - (n0 - 1), rr = maxx[i];

        if (a[minx[i] - 1] > i) {
            l = max(l, minx[i]);
            ll = max(ll, minx[i]);
        }
        if (maxx[i] + 1 < n && a[maxx[i] + 1] > i) {
            r = min(r, maxx[i] - (n0 - 1));
            rr = min(rr, maxx[i] - (n0 - 1));
        }

        if (l > r)
            return 0;

        ans = (long) ans * (r - l + 1) % mod;
        num--;

        if (rr - ll > num)
            return 0;

        ans = (long) ans * fac[num] % mod *
                    inv[num - (rr - ll)] % mod;
        num -= rr - ll;
    }

    // fprintf(stderr, "num=%d\n", num);

    return ans;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i <= 300000; i++)
        fac[i] = (long) fac[i - 1] * i % mod;
    inv[300000] = 988693096;
    for (int i = 300000; i >= 1; i--)
        inv[i - 1] = (long) inv[i] * i % mod;

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i), a[i]--;
    printf("%d\n", solve(n));
}


Measured memory_bytes: 6016
import java.util.*;
import java.text.SimpleDateFormat;
import java.text.ParseException;
public class Main{
  public static void main(String[] args)throws ParseException{
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    SimpleDateFormat f = new SimpleDateFormat("yyyy/MM/dd");
    Date d = f.parse(s);
    Date dh = f.parse("2019/04/30");
    if(d.getTime() > dh.getTime()){
      System.out.println("TBD");
    }else{
      System.out.println("Heisei");
    }
  }
}


Measured memory_bytes: 23632
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
a=[-1,0,1]
b=[-1,0,1]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            s[i][j]=0
            for c in a:
                for d in b:
                    if i+c<0 or j+d<0 or i+c>h-1 or j+d>w-1 or (a==0 and b==0) or s[i+c][j+d]!="#":
                        continue
                    else:
                        s[i][j]+=1
for i in range(h):
    print(*s[i][:],sep="")

Measured memory_bytes: 9040
#include <iostream>
#define loop(i,j) for(int i = 0;i < j;i++)

using namespace std;

int n,q,s[10000],t[500],r;

int main() {
	cin >> n;
	loop(i,n) cin >> s[i];
	cin >> q;
	loop(i,q) {
		cin >> t[i];
		loop(j,n) {
			if(s[j] == t[i]) {
				r++;
				break;
			}
		}
	}
	cout << r << endl;
}



Measured memory_bytes: 3100
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]B - Resistors in Parallel
            int N = int.Parse(Console.ReadLine());
            var A = ReadLine();

            double sum = 0;

            foreach(var a in A)
            {
                sum += 1 / a;
            }

            Console.WriteLine(1 / sum);
        }

        static List<double> ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => double.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 13396
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    r,s,p=map(int,input().split())
    T=input()
    T_lis=[False]*n
    ans=0
    for i,t in enumerate(T):
        if i-k>=0:
            if T[i-k]==t and T_lis[i-k]:
                continue
        if t=='r':
            ans+=p
        elif t=='s':
            ans+=r
        else:
            ans+=s
        T_lis[i]=True
    print(ans)


if __name__=='__main__':
    main()

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x;
    cin >> x;
    vector<int> dp(x + 1, false);
    dp[0] = true;
    for (int i = 0; i < 6; ++i) {
        for (int j = 100 + i; j <= x; j++) {
            if (dp[j - 100 - i]) dp[j] = true;
        }
    }
    cout << (dp[x] > 0) << endl;
    return 0;
}


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

void dfs(const long n, const long W, const long value, const long weight, long &opt, const long index, const vector<long> &rsumw, const vector<long> &rminw, const vector<pair<long, long>> &v) {
  if (index == n) {
    opt = max(opt, value);
    return;
  }
  if (rsumw.at(index) <= W - weight) {
    long tvalue = value;
    for (long i = index; i < n; i++) {
      tvalue += v.at(i).first;
    }
    opt = max(opt, tvalue);
    return;
  }
  if (rminw.at(index) > W - weight) return;
  if (weight + v.at(index).second <= W) {
    opt = max(opt, value + v.at(index).first);
    long tweight = weight + v.at(index).second, tvalue = value + v.at(index).first;
    for (long i = index + 1; i < n; i++) {
      if (tweight + v.at(i).second <= W) {
        tweight += v.at(i).second, tvalue += v.at(i).first;
      } else {
        tvalue += v.at(i).first * (W - tweight) / v.at(i).second;
      break;
      }
    }
    if (opt < tvalue) {
      dfs(n, W, value + v.at(index).first, weight + v.at(index).second, opt, index + 1, rsumw, rminw, v);
    }
  }
  long tweight = weight, tvalue = value;
  for (long i = index + 1; i < n; i++) {
    if (tweight + v.at(i).second <= W) {
      tweight += v.at(i).second, tvalue += v.at(i).first;
    } else {
      tvalue += v.at(i).first * (W - tweight) / v.at(i).second;
    break;
    }
  }
  if (opt < tvalue) {
    dfs(n, W, value, weight, opt, index + 1, rsumw, rminw, v);
  }
}

long solve(const long n, const long W, vector<pair<long, long>> &v) {
  sort(v.begin(), v.end(), [&](pair<long, long> &a, pair<long, long> &b) {
    return (__int128)a.first * b.second > (__int128) a.second * b.first;
  });
  vector<long> rsumw(n + 1, 0);
  vector<long> rminw(n + 1, LONG_MAX);
  for (long i = n - 1; i >= 0; --i) {
    rsumw.at(i) = rsumw.at(i + 1) + v.at(i).second, rminw.at(i) = min(rminw.at(i + 1), v.at(i).second);
  }
  long opt = 0;
  dfs(n, W, 0, 0, opt, 0, rsumw, rminw, v);
  return opt;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  long N, W;
  cin >> N >> W;
  vector<pair<long, long>> V(N);
  for (long i = 0; i < N; i++) {
    long a, b;
    cin >> a >> b;
    V.at(i) = {b, a};
  }
  cout << solve(N, W, V) << "\n";
}

Measured memory_bytes: 3684
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort(reverse=True)
    alice = sum(a[::2])
    bob = sum(a[1::2])
    print(alice - bob)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9144
#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
for tt in range(1):
    a=int(input())
    b=int(input())
    if a*b==6:
        print(1)
    elif a*b==3:
        print(2)
    else:
        print(3)
    #n= map(int, sys.stdin.readline().split(' '))
    #a=list(map(int,sys.stdin.readline().split(' ')))
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

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

using namespace std;

int pow2(int x) { return x * x; }

bool isSquare(int x) {
  int l = 0, r = 200;
  while (r - l > 1) {
    int m = (l + r) / 2;
    (m * m > x ? r : l) = m;
  }
  return l * l == x;
}

int main() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> pos(n,vector<int>(d));
  for (int i = 0; i < n; ++i) for (int j = 0; j < d; ++j) cin >> pos[i][j];
  int cnt = 0;
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      int sum = 0;
      for (int k = 0; k < d; ++k)
        sum += pow2(pos[i][k] - pos[j][k]);
      if (isSquare(sum)) cnt++;
    }
  cout << cnt << endl;
}


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

string s;
int c[3];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    c[s[i] - 'a']++;
  }  
  sort(c, c + 3);
  cout << (c[2] - c[0] < 2 ? "YES" : "NO") << endl;

  return 0;
}

Measured memory_bytes: 512
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func floatSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n, k := iScan(), iScan()
	p := iSScan(n)
	for i, _ := range p {
		p[i]--
	}
	c := iSScan(n)
	ans := max(c)
	for i := 0; i < n; i++ {
		d := make([]int, n)
		for j, _ := range d {
			d[j] = -1
		}
		x := i
		d[x] = 0
		l := -1
		log := make([]int, n+1)
		f := true
		for j := 1; ; j++ {
			log[j] = log[j-1] + c[p[x]]
			ans = larger(ans, log[j])
			if j == k {
				f = false
				break
			}
			if d[p[x]] >= 0 {
				l = j
				break
			} else {
				d[p[x]] = j
				x = p[x]
			}
		}
		if f {
			if k > l && log[l] > 0 {
				z := log[l] * ((k - 1) / l)
				fin := (k-1)%l + 1
				ans = larger(ans, z+max(log[:fin+1]))
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 6344
from sys import stdin, stdout
def readAll_int(): return list(map(int, stdin))

def gcd(a, b):
	while b:
	    a, b = b, a % b
	return a
	
def lcm(a, b):
    return a * b // gcd (a, b)

def main():
    n = int(input())
    t = list(set(readAll_int()))
    if len(t)>1:
        for i in range(len(t) - 1):
            a = lcm(t[i], t[i+1])
            t[i+1] = a
    else:
        a = t[0]
    print(a)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "KMULT"
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 998244353;
using namespace std;
const int N = 3e5+5;
ll m, n, k, t, T, ans, u, v, tong;
ll a[N], b[N], st[N*4], lazy[N*4];
string s;
vector<ll> kq;
void build(ll id, ll l, ll r)
{
    if(l > u || r < u)return;
    if(l == r)
    {
        st[id] = max(st[id], t);
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= u)build(id*2, l, mid);
    else build(id*2+1, mid+1, r);
    st[id] = max(st[id*2], st[id*2+1]);
}
ll get(ll id, ll l, ll r)
{
    if(l > v || u > r)return 0;
    if(u <= l && r <= v)return st[id];
    ll mid = (l + r)/2;
    return max(get(id*2, l, mid), get(id*2+1, mid+1, r));
}
void sol()
{
    cin >> n >> k;
    for(int i =1 ; i <= n; i ++)
    {
        cin >> a[i];
        u = max((ll) 1, a[i] - k + 1), v = min((ll)N, a[i] + 1 + k);
        t = get(1, 1, N) + 1;
        u = a[i]+1;
        build(1, 1, N);
        ans = max(ans, t);
    }
    cout << ans;

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".INP", "r"))
    {
		freopen(task".INP","r",stdin);
		freopen(task".OUT","w",stdout);
    }
    sol();
    //cout << chap(4, 3);
}


Measured memory_bytes: 14180
#include <stdio.h>

int main(void)
{
    int i, j, h, w; 

    while(1){
        scanf("%d %d", &h, &w);

        if (h ==0 && w ==0)
            break;

        for (i = 1; i <= h; ++i){
            if (i % 2){
                for (j = 1; j <= w ;++j){
                    if (j % 2)
                        printf("#");
                    else 
                        printf(".");
                }
                printf("\n");
            }

            else {
                for (j = 1; j <= w; ++j){
                    if (j % 2)
                        printf(".");
                    else 
                        printf("#");
                }
                printf("\n");
            } 
                
        }

        printf("\n");
            
    }

    return 0;

}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	int32 N;
	cin >> N;
	vector<int32> A(N);
	REP(i, N) cin >> A[i];
	sort(all(A));
	reverse(all(A));
	int32 res = 0;
	REP(i, N){
		res = max(res, min((int32)i+1, A[i]));
	}
	cout << res << endl;
}



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

int main() {
	int n; cin >> n;
	vector<int>L(2 * n); for (auto&& x : L)cin >> x;
	sort(L.begin(), L.end());

	int ans = 0;
	for (int i = 0; i < 2 * n; i += 2){
		ans += min(L[i], L[i + 1]);
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;
typedef long long ll;
    
int main()
{
    int N, K;
    cin >> N >> K;
    vector<bool> H(N, false);

    for (int i = 0; i < K; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int tmp;
            cin >> tmp;
            H[tmp-1] = true;
            // cout << "i:" << i << " j:" << j << " tmp:" << tmp << endl;
        }
    }

    int count = 0;
    for (auto i : H) {
        // cout << "count:" << (bool)i << endl;
        if (i == false) {
            count++;
        }
    }
    cout << count;

    return 0;
}


Measured memory_bytes: 3624
import sys

def main(N,M,A):
    ans = []
    for i in range(N-1):
        for j in range(i+1,N):
            if A[i]+A[j] <= M:
                ans.append(A[i]+A[j])
    return max(ans) if ans else 'NONE'

while 1:
    N,M = [int(x) for x in sys.stdin.readline().split()]
    if N==M==0:
        break
    A = [int(x) for x in sys.stdin.readline().split()]
    print(main(N,M,A))


Measured memory_bytes: 29288
#include<stdio.h>
#include<algorithm>

int nextInt();

int N, i;
int A, B, C[100000];
long long int a, b;

int main(){
	N=nextInt();
	for(i=0; i<N; i++){
		A=nextInt();
		B=nextInt();
		C[i] = A + B;
		b += B;
	}
	std::sort(C, C + N, [&] (const int &a, const int &b){
        return a > b;
    });
	for(i=0; i<N; i+=2){
		a += C[i];
	}
	printf("%lld\n", a-b);
	return 0;
}

int nextInt(){
	int f=0; char c=getchar();
	while((c<'0')||('9'<c)){c=getchar();}
	while((c>='0')&&(c<='9')){f=f*10+(c-'0'); c=getchar();}
	return f;
}


Measured memory_bytes: 640
import java.util.*
data class Apple(val color:Int, val taste:Long)
fun main(args:Array<String>) {
    val (x,y,a,b,c) = readLine()!!.split(" ").map { it.toInt() }
    val reds = readLine()!!.split(" ").map { it.toLong() }
    val greens = readLine()!!.split(" ").map { it.toLong() }
    val nonColor = readLine()!!.split(" ").map { it.toLong() }

    val list = Array(a+b+c){Apple(0,0)}
    var idx = 0
    for(t in reds) {
        list[idx++] = Apple(0, t)
    }
    for(t in greens) {
        list[idx++] = Apple(1, t)
    }
    for(t in nonColor) {
        list[idx++] = Apple(2, t)
    }

    var redCnt = 0
    var greenCnt = 0
    var ans = 0L
    var cnt = 0
    var pos = 0

    list.sortByDescending { it.taste }

    while (cnt < x + y) {
        val (color, delicious) = list[pos++]
        if(color == 0 && redCnt >= x) continue
        if(color == 1 && greenCnt >= y) continue
        ans += delicious
        if(color == 0) ++redCnt
        if(color == 1) ++ greenCnt
        ++cnt
    }


    print(ans)
}

Measured memory_bytes: 157792
#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define rf(i,a,b) for(ll i=a; i>=b; i--)
typedef std::vector<long long > vi ;
#define F first
#define S second
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 998244353
#define PB push_back
#define MP make_pair
#define PI 3.14159265358979323846
#define all(a) a.begin(),a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
#define endl '\n'
#define show(a) for(auto el:a)cout<<el<<" "
const ll INF=LLONG_MAX/2;
const ll N=2e5+1;
#define yesno(f) yes(f);no(f);
#define yes(f) if(f)cout<<"YES\n";
#define no(f) if(!f)cout<<"NO\n";
using  namespace std;
ll binarySearch(ll arr[], ll l, ll r,ll x) 
{ 
    if (r >= l) 
    { 
        ll mid = l + (r - l) / 2;  
        if (arr[mid] == x) 
        return mid; 
        if (arr[mid] > x) 
        return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    }
    return -1; 
} 
int main()
{
    fast;
        ll n;
        string s;
        std::cin >> s;
        cout<<s[0]<<s[1]<<s[2]<<"\n";
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

using ll = long long;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
Bint comb(Bint, Bint);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    int h[n];
    rep(i, n) { cin >> h[i]; }
    int ans = 0;
    int temp = 0;
    repd(i, 1, n) {
        if (h[i] <= h[i - 1]) {
            temp++;
        } else {
            temp = 0;
        }
        ans = max(ans, temp);
    }

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

Bint comb(Bint a, Bint b) {
    Bint ans = 1;

    if (a < b) {
        return 0;
    }

    rep(i, b) {
        ans *= a - i;
        ans /= i + 1;
    }

    return ans;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define forloop(n) for(int i = 0; i < n; i++)
#define ll long long
#define mod 1000000007
long long exp(long long taban, long long us) {
    long long carpan = taban;
    long long temp = us;
    long long res = 1;
    for(int i = 0;;i++){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
        if(temp == 0) break;
    }
    return res;
}
ll ebob(ll a, ll b){
	if(!a)return b;
	return ebob(b%a, a);
}
ll ekok(ll a, ll b){
	return (((a*b)%mod)*(exp(ebob(a,b), (ll)mod-2))) % mod;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll n, m; cin>>n>>m;
	ll w[100], v[100];
	for(ll i = 0; i < n; i++){
		cin>>w[i]>>v[i];
	}
	ll dp[100005];
	for(ll i = 0; i < 100005; i++) dp[i] = 1e9+7;
	dp[0] = 0;
	for(ll i = 0; i < n; i++){
		bool used[100005] = {};
		for(ll j = 100004; j > 0; j--){
			if(dp[max(0LL, j - v[i])] + w[i] < dp[j] && !used[max(0LL, j - v[i])]){
				dp[j] = dp[max(0LL, j - v[i])] + w[i];
				//if(i == 3) cout<<j<<endl;
				used[j] = 1;
				//used[max(0LL, j - v[i])] = 1;
			}
		}
	}
	ll res = 0;
	for(ll i = 0; i < 100005; i++){
		if(dp[i] <= m){
			res = i;
			//cout<<dp[i]<<" "<<i<<endl;
		}
		//cout<<dp[i]<<" "<<i<<endl;
	}
	cout<<res;
	return 0;
}


Measured memory_bytes: 1152
#include<iostream>
using namespace std;
 
int main(){
  int a_i=0,z_i=0;
  string str;
  cin >> str;
  for(int i = 0;i < str.size();++i){
    if(str[i]=='A'){
      a_i = i;
      break;
    }
  }
  for(int i = 0;i < str.size();++i){
    if(str[i]=='Z'){
      z_i = i;
    }
  }
  cout << z_i- a_i + 1 << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch)
{
    if (ch == 'A')
        return 1;
    else if (ch == 'C')
        return 2;
    else if (ch == 'G')
        return 3;
    else if (ch == 'T')
        return 4;
    else
        return 0;
}

long long getKey(char str[])
{
    long long sum = 0, p = 1, i;
    for (i = 0; i < strlen(str); i++)
    {
        sum += p * (getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(long long key) { return key % M; }
int h2(long long key) { return 1 + (key % (M - 1)); }

int find(char str[])
{
    long long key, i, h;
    key = getKey(str);
    for (i = 0;; i++)
    {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0)
            return 1;
        else if (strlen(H[h]) == 0)
            return 0;
    }
    return 0;
}

int insert(char str[])
{
    long long key, i, h;
    key = getKey(str);

    for (i = 0;; i++)
    {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0)
            return 1;
        else if (strlen(H[h]) == 0)
        {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main()
{
    int i, n, h;
    char str[L], com[9];
    for (i = 0; i < M; i++)
        H[i][0] = '\0';
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%s %s", com, str);
        if (com[0] == 'i')
        {
            insert(str);
        }
        else
        {
            if (find(str))
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
    }
    return 0;
}


Measured memory_bytes: 16980
n=int(input())
l=list(map(int,input().split()))
from bisect import bisect_left
l.sort()

count=0
for a in range(n-2):
    for b in range(a+1,n-1):
        idx=bisect_left(l,l[a]+l[b],lo=b)
        count+=idx-(b+1)

print(count)

Measured memory_bytes: 9292
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_S =int(1e5) +5;
int broad[MAX_S][30];

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

    int mt = 0;
    for(int i=0;i<N;i++){
        int s,t,c;
        cin >> s >> t >>c;
        c--;
        mt = max(mt,t);
        for(int j=s;j<=t;j++){
            broad[j][c]++;
        }
    }

    ll ans =0;
    for(int i=0;i<=mt;i++){
        ll temp=0;
        for(int j=0;j<C;j++){
            if(broad[i][j] >0){
                temp++;
            }
        }
        // cerr <<"i=" << i << "temp=" << temp << endl;
        ans =max(ans,temp);
    }
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 11904
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
using namespace std;
 

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define pb push_back
#define forn(i, n) for (int i = 0; i < n; ++i)
#define int long long

 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
 
const int MAXN = 1e5 + 5;
const ll MOD = 998244353;
const ll INF = 1e18;


random_device rd;
mt19937 rnd(rd());


int gcd(int a, int b) {
	return (!a ? b : gcd(b % a, a));
}


ll pw(ll a, ll x) {
	ll res = 1;
	while (x > 0) {
		if (x & 1) {
			res = (res * a) % MOD;
		}
		a = (a * a) % MOD;
		x >>= 1;
	}
	return res;
}


signed main() {
	FAST_IO;
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	forn(i, n) {
		cin >> a[i];
	}
	if (k >= n) {
		forn(i, n) {
			cout << n << " ";
		}
		cout << "\n";
		return 0;
	}
	int cnt = 0;
	bool changes = 1;
	while (changes && cnt < k) {
		bool f = 0;
		vector<int> b(n);
		for (int i = 0; i < n; ++i) {
			int l = max(0ll, i - a[i]), r = min(i + a[i], n - 1);
			b[l]++;
			if (r + 1 < n) {
				b[r + 1]--;
			}
		}
		int bal = 0;
		forn(i, n) {
			bal += b[i];
			if (bal != a[i]) {
				f = 1;
			}
			a[i] = bal;
		}
		cnt++;
		if (!f) {
			changes = 0;
		}
	}
	forn(i, n) {
		cout << a[i] << " ";
	}
	cout << "\n";
 	return 0;
}

Measured memory_bytes: 6364
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
#define debug(V) rep(i, V.size()) cout << V[i] << " ";
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, n, t, r, k, w, l, ans, i, j, u, v;
string S, T;
vl A, B;
void input() { cin >> n; }
void solve() {
    A.pb(1);
    rep(i, 10) { A.pb(A.back() * 26); }
    while(n) {
        S = (char)('a' + (n - 1) % 26) + S;
        n -= (n - 1) % 26 + 1;
        n /= 26;
    }
    cout << S << endl;
}
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    solve();
}

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

int main() {
	int  n;
	cin >> n;
	string str;
	map<string,bool>m;

	for(int i=1;i<=n;i++){
		cin >> str ;
		m[str]=1;
	}
		cout <<m.size() << '\n' ;
	}

Measured memory_bytes: 19152
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next();
        
        int count = 0;
        for(int i = 0; i < s.length()/2; i++){
            if(s.charAt(i) != s.charAt(s.length()-1 -i)){
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 23764
n = int(input())
s = input()
dp = [0 for i in range(n + 1)]
for i in range(n):
    if s[i - dp[i]:i + 1] in s[:i - dp[i]]:
        dp[i + 1] = dp[i] + 1
    else:
        dp[i + 1] = dp[i]
print(dp[n])

Measured memory_bytes: 9248
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for s in range(N):
    ### Step1
    S = []  # 累積和S. ただし, 初項は0ではなく1回目の移動後の得点とする.
    # 1回目の移動
    i = P[s] - 1
    S.append(C[i])
    # 2回目以降の移動. スタート地点に戻ってくるまで繰り返し.
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])

    ### Step2: KとSの長に応じて場合分けして, 得点の最大値を求める.
    # 1周未満しか移動できない場合:
    if K <= len(S):
        score = max(S[:K])
    # 1周以上回ることができるが, ループを1周したときに得点が減る場合:
    elif S[-1] <= 0:
        score = max(S)
    # 1週以上回ることができ, かつループを1週するごとに得点が増える場合:
    else:
        # ループを (K // len(S) - 1)回 廻る場合:
        score1 = S[-1] * (K // len(S) - 1)
        score1 += max(S)
        # ループを (K // len(S))回 廻る場合:
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        # score1 と score2 の大きい方がこの場合の得点の最大値
        score = max(score1, score2)

    ans = max(ans, score)

print(ans)

Measured memory_bytes: 80668
#include <iostream>

int main() {
    int m, d;
    std::cin >> m >> d;

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 10; j <= d; j++) {
            if (j /10 > 1 and j % 10 > 1 and i == (j / 10) * (j % 10)) {
                ans++;
            }
        }
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()

coin = [1]
sixsta = 6
while sixsta < 100000:
    coin.append(sixsta)
    sixsta *= 6

ninesta = 9
while ninesta < 100000:
    coin.append(ninesta)
    ninesta *= 9
coin.sort()

# NlogNダイクストラ
# これも最短経路を求める問題
def dijkstra(n, start):
    dist = [float('inf')] * n
    pos = [(0, start)]
    heapify(pos)
    dist[start] = 0

    while len(pos):
        cost, u = heappop(pos)

        if dist[u] < cost:
            continue
        # エッジは探索のたびに生成していく
        for i in range(len(coin)):
            if u + coin[i] >= n:
                continue
            if dist[u] + 1 < dist[u + coin[i]]:
                dist[u + coin[i]] = dist[u] + 1
                heappush(pos, (dist[u] + 1, u + coin[i]))

    return dist

print(dijkstra(N + 1, 0)[N])

Measured memory_bytes: 88928
from operator import itemgetter

N, M = map(int, raw_input().split())
request = []
for i in range(0, M):
	inpt = map(int, raw_input().split())
	request.append(inpt)
request.sort(key=itemgetter(1))
cnt = 0
tmp = -1
for i in range(0, len(request)):
	if tmp <= request[i][0]:
		cnt += 1
		tmp = request[i][1]
print cnt

Measured memory_bytes: 26356
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	rep(i,n) cin >> a[i], a[i]/=2;
	int cnt = 0;

	while(a[0]%2==0) {
		rep(i,n){
			if(a[i]&1){
				cout << 0 << endl;
				return 0;
			}
			a[i]/=2;
		}
		cnt++;
	}
	srep(i,1,n) if(a[i]%2==0){
		cout << 0 << endl;
		return 0;
	}

	ll lcm = 1;
	rep(i,cnt) lcm*=2; 
	rep(i,n){
		lcm = lcm * a[i] / __gcd(lcm, (ll)a[i]);
		if(lcm > m) {
			cout << 0 << endl;
			return 0;
		}
	}

	ll ans = 1+(m-lcm)/(2*lcm);
	cout << ans << endl;
}

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

int main()
{
	int n, m;

    string s[110], t[110];

	cin >> n;

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

	cin >> m;

	for (int i = 1; i <= m; i++)
	{
		cin >> t[i];
	}

	int sum = 0, max_s = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{
			if (s[i] == s[j]) 
			{
				sum++;
			}
		}

		for (int k = 1; k <= m; k++)
		{
			if (s[i] == t[k])
			{
				sum--;
			}
		}

		if (sum > max_s)
		{
			max_s = sum;
		}
		sum = 0;
	}
	cout << max_s << endl;
}

Measured memory_bytes: 256
n = int(input())
num_lists = list(map(int, input().split()))

index_list = list(range(1, n+1, 1))
odd_list = []
for i in index_list:
    if i % 2 != 0:
        odd_list.append(i)

answer_lists = []
for i in odd_list:
    if num_lists[i-1] % 2 != 0:
        answer_lists.append(i)
print(len(answer_lists))

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

#define ll long long
#define pb push_back

using namespace std;
const int N = 2e5 + 5;
int a[N];

string alp = "abcdefghijklmnopqrstuvwxyz";

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    n--;
    string ans = "";
    int ost = 0;
    while(n >= 26)
    {
        ost = n % 26;
        ans += alp[ost];
        n /= 26;
        n--;
    }
    ans += alp[n];
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3648
N,K = map(int,input().split())
V = list(map(int,input().split()))

sumval = 0
for l in range(min(K+1,N+1)):
    for r in range(min(K+1-l,N-l+1)):
        sV = sorted(V[:l]+ V[N-r:])
        # i_div = 0
        # for i_div in range(len(sV)):
        #     if sV[i_div] > 0:
        #         break
        # for sute in range(min(K-r-l+1,len(sV),i_div+1)):
        for sute in range(min(K-r-l+1,len(sV))):
            c = sum(sV[sute:])
            sumval = max(c,sumval)

print(sumval)

Measured memory_bytes: 3064
/**
 * Bredth first search.
 * graphs could be circular.
 * there could be a better answer later.
 */

#include <iostream>
using namespace std;
const int N = 101;
int adj[N][N] = {0};
int d[N] = {0};

void bfs(int n, int dd) {
	int s[N] = {0}; // this needs to be a stack member.
	int k = adj[n][0];
//	cout << n << ' ' << dd << ' ' << k << endl;
	int kk = 0;
	for (int j=1;j<=k;j++) {
		int nn = adj[n][j];
		if (d[nn] != -1 && d[nn] <= dd) continue; // this condition is important.
		d[nn]=dd;
		s[kk++]=nn;
	//	cout << nn << endl;
	}

	for (int j=0;j<kk;j++)
	{
		bfs(s[j], dd+1);
	}
}

int main()
{
	int n;
	cin >> n;
	for (int i=1;i<=n;i++){
		int j, k;
		cin >> j >> k;
		d[j]=-1;
		adj[j][0]=k;
		for (int m=1;m<=k;m++) {
			int a;
			cin >> a;
			adj[j][m]=a;
		}
	}

	d[1]=0;

	bfs(1, 1);

	for (int i=1;i<=n;i++){
		cout << i << ' ' << d[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 3156
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int a,b;
	cin>>a>>b;
	cout<<(a+b+1)/2<<endl;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//C - Energy Drink Collector

struct drink{
    int price;
    int count;
};

bool cmp(const drink& left,const drink& right){
    return left.price < right.price;
}

int main(void){
    
    int N,m;
    std::cin >> N >> m;
    std::vector<drink> drinks(N);
    for(int i=0;i<N;i++){
        std::cin >> drinks[i].price >> drinks[i].count;
    }
    std::sort(drinks.begin(),drinks.end(),cmp);
    long ans=0;
    for(int i=0;i<N;i++){
        if(drinks[i].count>=m){
            ans+=static_cast<long>(m)*static_cast<long>(drinks[i].price);
            break;
        }else{
            ans+=static_cast<long>(drinks[i].count)*static_cast<long>(drinks[i].price);
            m-=drinks[i].count;
        }
    }
    std::cout << ans << std::endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  int n; cin >> n;
  map<long long, long long> mp;
  int a;
  long long sum = 0;
  for(int i=0; i<n; i++) {
    cin >> a;
    mp[a]++;
    sum += a;
  }
  int q; cin >> q;
  long long b, c;
  for(int i=0; i<q; i++) {
    cin >> b >> c;
    if (mp[b] != 0) {
      sum += (c - b) * mp[b];
      mp[c] += mp[b];
      mp[b] = 0;
    }
    cout << sum << endl;
  }

 
  return 0;
}

// EOF

Measured memory_bytes: 9288
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<ll>
#define ub upper_bound
#define lb lower_bound
#define all(v) ((v).begin()),((v).end())
#define allr(v) ((v).rbegin()),((v).rend())
#define ff first
#define ss second
#define mp make_pair
#define pll pair<ll,ll> 
#define fo(i,s,e) for(ll i=s;i<e;i++)
#define Fo(i,s,e) for(ll i=(s);(s>e)?i>e:i<e;(s>e)?i--:i++)
ll mod1 = 1e9 + 7;
ll mod2 = 998244353;
ll mul(ll x,ll y){
    return (1ll* (x%mod1)*(y%mod1));
}
ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
//ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
ll gcd(ll a,ll b){if(a<b) return gcd(b,a);if(b==0) return a;return gcd(b,a%b);} 
ll min(ll a,ll b){if(a<b)return a;return b;}
ll max(ll a,ll b){if(a>b)return a;return b;}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    //freopen("error.txt" , "w" , stderr) ;
    #endif
    ll n,m,q;
    cin>>n>>m>>q;
    ll a[q],b[q],c[q],d[q];
    for(ll i = 0;i<q;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    vll v(10);
    ll ans = 0;
    fo(i,1,m+1){
        fo(i1,i,m+1){
            fo(i2,i1,m+1){
                fo(i3,i2,m+1){
                    fo(i4,i3,m+1){
                        fo(i5,i4,m+1){
                            fo(i6,i5,m+1){
                                fo(i7,i6,m+1){
                                    fo(i8,i7,m+1){
                                        fo(i9,i8,m+1){
                                            v[0] = i,v[1] = i1,v[2] = i2,v[3] = i3,v[4]=i4,v[5]=i5,v[6] =i6,v[7] = i7,v[8]=i8,v[9]=i9;
                                            ll sum = 0;
                                            for(ll j = 0;j<q;j++){
                                                if(v[b[j]-1]-v[a[j]-1]==c[j])sum+= d[j];
                                            }
                                            ans = max(ans,sum);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define ll long long
#define WEIGHTSUM weight + (it -> first)
#define VALUESUM (it -> second) + value
using namespace std;
map <int, ll> maxValue;

int main() {
    ll n, w, weight, value;

	cin >> n >> w;
	for (int i = 1; i <= n; i++) {
		cin >> weight >> value;

		for (map <int, ll> :: reverse_iterator it = maxValue.rbegin(); it != maxValue.rend(); it++)
			if (WEIGHTSUM <= w)
				maxValue[WEIGHTSUM] = max(maxValue[WEIGHTSUM], VALUESUM);

		maxValue[weight] = max(maxValue[weight], value);
	}

	ll result = 0;
    for (pair <int, ll> value : maxValue)
    	result = max(result, value.second);
	cout << result;

	return 0;
}


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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int main(){
int a, b, c, d;
cin >> a >> b >> c >> d;

cout << max(a*b, c*d) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N,M;
    cin>>N>>M;
    int H[N];
    rep(i,N) cin >>H[i];
    int A[M],B[M];
    int ans=0;
    map<int,int> m;
    rep(i,M){
        cin >>A[i]>>B[i];
        m[A[i]-1]=max(m[A[i]-1],H[B[i]-1]);
        m[B[i]-1]=max(m[B[i]-1],H[A[i]-1]);
    }
    rep(i,N){
        if(H[i]>m[i]) ans++;
    }
    cout << ans << endl;

    



}


Measured memory_bytes: 12256
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

// https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/3/GRL_3_A

fn main() {
    let (_N, _M): (usize, usize) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };
    let (_A, _B): (Vec<usize>, Vec<usize>) = {
        let (mut _A, mut _B) = (vec![], vec![]);
        for _ in 0.._M {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            _A.push(iter.next().unwrap().parse().unwrap());
            _B.push(iter.next().unwrap().parse().unwrap());
        }
        (_A, _B)
    };
    // snip
    let _G = {
        let mut _G = vec![std::collections::HashSet::new(); _N + 1];
        for i in 0.._M {
            _G[_A[i]].insert(_B[i]);
            _G[_B[i]].insert(_A[i]);
        }
        _G
    };
    // snip

    let (V, E) = (_N, _M);
    let (s, t) = (_A, _B);
    let G = _G;
    fn f(i: usize, depth: usize, G: &Vec<std::collections::HashSet<usize>>,
            order: &mut Vec<usize>, is_articulation: &mut Vec<bool>) -> usize {
        if order[i] < INF { order[i] }
        else {
            order[i] = depth;
            let mut res = depth;
            for &j in &G[i] {
                let d = f(j, depth + 1, G, order, is_articulation);
                if d == depth { is_articulation[i] = true; }
                res = std::cmp::min(res, d);
            }
            res
        }
    }

    const INF: usize = 1_000_000_000;
    let mut order = vec![INF; V];
    let mut is_articulation = vec![false; V];
    f(0, 0, &G, &mut order, &mut is_articulation);
    is_articulation[0] = (0..V).filter(|&i| order[i] == 1).count() >= 2;
    let ans = (0..V)
        .filter(|&i| is_articulation[i])
        .map(|i| i.to_string())
        .collect::<Vec<_>>()
        .join("\n");

    if ans != "" { println!("{}", ans) };
}


Measured memory_bytes: 11872
# import itertools

N = int(input())
S = []
for i in range(N):
    S.append(input())
# print(N, S)

for i in range(len(S)):
    s = S[i]
    t = list(s)
    t.sort()
    S[i] = ''.join(t)

S.sort()
# print(S)

ans = 0
i = 0
count = 0
while i < N - 1:
    si = S[i]
    sj = S[i + 1]
    if si != sj:
        # print(si, i, count)
        ans += count * (count + 1) // 2
        count = 0
    else:
        count += 1
        if i == N - 2:
            ans += count * (count + 1) // 2
    i += 1

print(ans)


Measured memory_bytes: 63320
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include <queue>
#include<algorithm>
typedef long long int ll;
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,a) for (int i=1;i<=(a);i++)
const ll MOD = (10*10*10*10*10*10*10*10*10+7);
    int ans=0,id;
    int N,M;
    int A,B,C;
    string O,E;
    ll sum=0;
int main(){
    ios_base::sync_with_stdio(false);
    cin>>O;
    A=-1;
    REP(i,(signed)O.size()){
        if(A==-1&&O[i]=='A')A=i;
        if(O[i]=='Z')B=i;
    }
    cout<<B-A+1;
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 1; i < N; i++) {
        A[i] += A[i - 1];
    }

    long long res = 1e18;
    int left = 0, mid = 1, right = 2;
    while (mid < N - 2) {

        while (left < mid - 1) {
            long long prev = abs(A[mid] - 2 * A[left]);
            long long next = abs(A[mid] - 2 * A[left + 1]);
            if (prev > next) left++;
            else break;
        }

        while (right < N - 2) {
            long long prev = abs(A[N - 1] - 2 * A[right] + A[mid]);
            long long next = abs(A[N - 1] - 2 * A[right + 1] + A[mid]);
            if (prev > next) right++;
            else break;
        }

        long long P = A[left];
        long long Q = A[mid] - A[left];
        long long R = A[right] - A[mid];
        long long S = A[N - 1] - A[right];

        res = min(res, max({P, Q, R, S}) - min({P, Q, R, S}));
        mid++;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792