akhauriyash/Code-Regression huggingface dataset:
package main

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

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()
	for i := 0; i < 3; i++ {
		s := readString()
		printf("%s", s[i:i+1])
	}
	println()
}


Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000;
ll d[10][10];

void init(){
	rep(i,10){
		rep(j,10) d[i][j] = INF;
		d[i][i] = 0;
	}
}

void warshall_floyd(int n){
	for(int k = 0; k < n; k++){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if( d[i][k] == INF || d[k][j] == INF){
					// do nothing
				}else{
					d[i][j] = min(d[i][j],d[i][k] + d[k][j]);	
				}
			}
		}
	}
}


int main()
{
	init();
	int h,w;
	cin>>h>>w;
	rep(i,10){
		rep(j,10){
			cin>>d[i][j];
		}
	}
	warshall_floyd(10);
	ll ans = 0;
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			int c;
			cin>>c;
			if( c == -1 || c == 1){
				continue;
			}else{
				ans += d[c][1];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <time.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <cmath>
#include <memory.h>
#include <deque>
using namespace std;

#define lightkuriboh
#define mp make_pair
#define X first
#define Y second
#define pb push_back
#define CL(x) (x << 1)
#define CR(x) ((x << 1) + 1)
#define sqr(x) ((x) * (x))
#define Task ""

const bool OnLineJudge = 1;

typedef long long cc;
typedef long double ld;
typedef pair <int, int> pt;
const int N = 102;
int n, W;
int w[N], v[N];
int f[N][N][3 * N];
int res;

int main()
{
    if (!OnLineJudge)
    {
        freopen("input.inp", "r", stdin);
        //freopen(Task".inp", "r",  stdin);
        //freopen(Task".out", "w", stdout);
    }
    //-------------------------------------------------------------------------------------------------------
    std :: ios_base :: sync_with_stdio(false); cin.tie(0);
    //-------------------------------------------------------------------------------------------------------
    cin >> n >> W;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    f[1][0][0] = 0;
    if (w[1] <= W) f[1][1][0] = v[1];
    res = f[1][1][0];
    for (int i = 2; i <= n; i++) {
        f[i][1][w[i] - w[1]] = v[i];
        for (int sl = 1; sl <= n; sl++)
            for (int sw = 0; sw < 3 * N; sw++)
                if (1ll * sl * w[1] + sw <= W) {
                    f[i][sl][sw] = max(max(f[i][sl][sw], f[i - 1][sl][sw]), f[i][sl - 1][sw]);
                    if (sw >= w[i] - w[1])
                        f[i][sl][sw] = max(f[i][sl][sw], f[i - 1][sl - 1][sw - w[i] + w[1]] + v[i]);
                    res = max(res, f[i][sl][sw]);
                }
    }
    cout << res;
    //-------------------------------------------------------------------------------------------------------
    return 0;
}


Measured memory_bytes: 12288
/******************************************************************************

                            Online C Compiler.
                Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <stdio.h>
int A[100000]={};

int main()
{
    int n;
    scanf("%d",&n);
    int i;
    int mc = 0;
    long long sum = 0;
    long long lmin = -1000000000;
    long long rmin = 1000000000;
    long long min = 0;
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
        if(A[i]<0){
            mc++;
            if(lmin<A[i]){
                lmin = A[i];
            }
        }
        else{
            if(rmin>A[i]){
                rmin = A[i];
            }
        }
    }
    if(lmin==0 || rmin ==0)min = 0;
    else if((-lmin)>rmin)min = rmin;
    else min = -lmin;
    //printf("%d %d\n",lmin,rmin);
    for(i=0;i<n;i++){
        if(A[i]>0)
            sum+=A[i];
        else
            sum+=(-A[i]);
    //printf("%lld\n",sum);
    }
    if(mc%2 != 0){
        
        sum = sum-2*min;
    }
    printf("%lld",sum);
    return 0;
}


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

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

#define x first
#define y second
#define pb push_back
#define MX 100007

int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
int n,m;


int main()
{
	int a,b,c;
	cin >>a>>b>>c;
	if(c>=a&&c<=b)puts("Yes");
	else if(c>=b&&c<=a)puts("Yes");
	else puts("No");
}

Measured memory_bytes: 256
n=int(input())
b=[input() for _ in range(n)]
m=int(input())
r=[input() for _ in range(m)]
d={}
for i in range(n):
  if b[i] in d:
    d[b[i]]+=1
  else:
    d[b[i]]=1
for i in range(m):
  if r[i] in d:
    d[r[i]]-=1
  else:
    d[r[i]]=-1
ans=max(d.values())
if ans<0:
  print(0)
else:
  print(ans)

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

typedef long long ll;

const ll mod=1000000000+7;


ll dp[2*100005];
ll ager[2*100005];
ll last[2*100005];

int main() {
    int n,c;

    cin>>n;

    
    ll ans=0;

    for(int i=1;i<=n;i++){
        cin>>c;
        if(last[c]!=0 && i-last[c]>1){
            dp[i]=(ager[last[c]-1]%mod+1%mod+dp[last[c]]%mod)%mod;
            ans=(ans%mod+dp[i]%mod)%mod;
            ager[i]=ans;
        }else{
            ager[i]=ans;
        }
        last[c]=i;
    }

    cout<<(ans+1ll)%mod<<endl;

    


}

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

#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())

#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false
#define LL long long
#define Dev 1000000007

//cout << (c)?"Yay!":":(" << endl;

// sort(a.begin(), a.end(), std::greater<int>());
using namespace std;

int main()
{
    long long int a, b;
    cin >> a >> b;
    long long int amari = a % b;
    cout << min(amari, abs(b-amari)) << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
N = int(input())
ans = 0
li = [0]*N
for i in range(N):
    s = list(input())
    s.sort()
    li[i] = ''.join(s)
c = Counter(li)
key = c.keys()
for i in key:
    if c[i] >= 2:
        ans += c[i]*(c[i]-1)//2
print(ans)

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

template <std::uint_fast64_t Modulus> class modint {
    using u64 = std::uint_fast64_t;
    
public:
    u64 a;
    
    modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    u64 &value() { return a; }
    const u64 &value() const { return a; }
    modint operator+(const modint rhs) const  {
        return modint(*this) += rhs;
    }
    modint operator-(const modint rhs) const {
        return modint(*this) -= rhs;
    }
    modint operator*(const modint rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator/(const modint rhs) const {
        return modint(*this) /= rhs;
    }
    modint &operator+=(const modint rhs) {
        a += rhs.a;
        if (a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    modint &operator-=(const modint rhs) {
        if (a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    modint &operator*=(const modint rhs) {
        a = a * rhs.a % Modulus;
        return *this;
    }
    modint &operator/=(modint rhs) {
        u64 exp = Modulus - 2;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};

const int prime = 1000000007;

modint<prime> modcom (int x, int y)
{
    modint<prime> a;
    a.a = 1;
    for (int i=0; i<y; i++) {
        modint<prime> m, n;
        m.a = x-i;
        n.a = i+1;
        a = a*m/n;
    }
    return a;
}

modint<prime> f (int r, int c)
{
    
    int min;
    if (r<c) { min = r; }
    else { min = c; }
    
    return modcom(r+c+2, min+1);
}

int main(){
    
    modint<prime> ans;
    
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    r1 -= 1;
    c1 -= 1;
    ans = f(r2, c2) - f(r2, c1) - f(r1, c2) + f(r1, c1);
    cout << ans.a << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
  int A,B,H,M;
  cin >> A >> B >> H >> M;

  double Hrad = 360.0/12.0*(H+static_cast<double>(M)/60.0);
  double Mrad = 360.0/60.0*M;
  double diffRad = min(abs(Hrad-Mrad),360-abs(Hrad-Mrad));
  cout << fixed;
  cout << setprecision(12) << sqrt(A*A+B*B-2*A*B*cos(M_PI*diffRad/180.0)) << endl;
}


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

using namespace std;

int main() {
  int N;
  int K;
  string S;
  cin >> N;
  cin >> K;
  cin >> S;
  
  int count = 0;
  int couhukudo = 0;
  for (int i=0; i<N-1; i++) {
    if (S[i] != S[i+1]) {
      count++;
    }
    
    if (i == 0) {
      if (S[i] == 'R' && S[i+1] == 'R'){
        couhukudo++;
      }
    } else if (i == N-2) {
      if ((S[i] == 'L' && S[i-1] == 'L') ||(S[i] == 'R' && S[i+1] == 'R')) {
        couhukudo++;
      }
      if (S[i+1] == 'L' && S[i] == 'L') {
        couhukudo++;
      }
    } else {
      if ((S[i] == 'L' && S[i-1] == 'L') ||(S[i] == 'R' && S[i+1] == 'R')) {
        couhukudo++;
      }
        
    }
  }
  
  //cout << couhukudo << endl;
  //cout << count << endl;
  
  if (count <= K*2) {
    couhukudo += count;
  } else {
    couhukudo += (K*2);
  }
  
  cout << couhukudo << endl;
}

Measured memory_bytes: 512
# coding: utf-8
# Your code here!

import queue

WHITE = 0
GRAY = 1
BLACK= 2

def topologicalSort(s):
    Q.put(s)
    color[s] = GRAY
    while not Q.empty():
        u = Q.get()
        out.append(u)
        
        for v in G[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and color[v] == WHITE:
                color[v] = GRAY
                Q.put(v)
            



nums=list(map(int,input().split()))
n = nums[0]
e = nums[1]

color = [WHITE] * n
G = [[] for i in range(n)]
indeg = [0] * n

for i in range(e):
    nums=list(map(int,input().split()))
    G[nums[0]].append(nums[1])
    indeg[nums[1]] += 1

Q = queue.Queue()
out = []

for i in range(n):
    if indeg[i] == 0 and color[i] == WHITE:
        topologicalSort(i)

for i in range(n):
    print(out[i])















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

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

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

int main() {
	ll n, a, b;
	cin >> n >> a >> b;
	if ((b-a) % 2 == 0) {
		cout << (b-a)/2;
	}
	else {
		ll opt1 = a + (b-a-1)/2;
		ll opt2 = (n-b) + 1 + (n-(a+n-b+1))/2;
		cout << min(opt1,opt2);
	}
	cout << "\n";
	return 0;
}

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

const long long int INF = 1e18L + 5;
int main(void)
{
	int n;
	cin >> n;

	vector<int> arr;

	for(int i = 0;i < n;i++)
	{
		int u;
		cin >> u;

		arr.push_back(u);
	}

	long long int dp[arr.size()][arr.size()];

	for(int i = 0;i < arr.size();i++)
	{
		for(int j = 0;j < arr.size();j++)
			dp[i][j] = INF;
	}

	for(int i = 0;i < arr.size();i++)
		dp[i][i] = 0;

	auto sum = [&] (int l,int r)
	{
		long long int s = 0;
		for(int i = l;i <= r;i++)
			s += arr[i];
		return s;
	};

	for(int len = 1;len <= n;len++)
	{
		for(int i = 0;i <= n-len;i++)
		{
			int j = i + len - 1;

			for(int k = i;k < j;k++)
			{
				long long int s = sum(i,j);
				dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j] + s);
			}
		}
	}


	cout << dp[0][n-1];

	return 0;
}

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

using namespace std;

int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;
  if (A + B < 2 * C) {
    cout << A * X + B * Y << endl;
  } else {
    int value = 2 * C * min(X, Y);
    if (X - Y > 0) {
      value += (X - Y) * min(2 * C, A);
    }
    if (Y - X > 0) {
      value += (Y - X) * min(2 * C, B);
    }
    cout << value << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
#define N_MAX 80
string s,s_copy;
int ans=0;
int point=0;

char ch(int i){
	if(i==0)
		return '0';
	else if(i==1)
		return '1';
	else return '2';
}

void set(int i,int j,int z){
	s_copy=s;
	int c=s.size();
	for(int k=0;k<c;k++){
		if(s_copy[k]=='P') s_copy[k]=ch(i);
		if(s_copy[k]=='Q') s_copy[k]=ch(j);
		if(s_copy[k]=='R') s_copy[k]=ch(z);
	}
}

int mainus(int i){
	switch (i){
	case 0: return 2;
	case 1: return 1;
	case 2: return 0;
	}
}

int kakeru(int x,int y){
	return x>y ? y:x;
}

int tasu(int x,int y){
	return x>y ? x:y;
}

int calc(){ 
	switch(s_copy[point++]){
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '-': return mainus(calc());
		case '(': 
			int left=calc();
			char temp=s_copy[point++];
			int right=calc();
			point++;
			if(temp=='+')return tasu(left,right);
			else return kakeru(left,right);
	}
}



int main()
{
		while(true){
			cin>>s;
			if(s==".") break;
			for(int i=0;i<=2;i++)
				for(int j=0;j<=2;j++)
					for(int z=0;z<=2;z++){
						set(i,j,z);
						point=0;
						if(calc()==2)
							ans++;
					}
				cout<<ans<<"\n";
				ans=0;
		}
	return 0;
}

Measured memory_bytes: 0
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import math
    a,b,c,x,y=map(int, input().split())
    # ABピザを奇数枚買っても1枚無駄になるから、ABピザは2枚を1枚だと考える
    # cの値段を2倍にして枚数を半分に
    cmax=max(x,y) # ABピザの最大枚数(2枚を1枚と考えたとき)
    c=2*c
    l=[]
    for i in range(cmax+1):
        amai = max(x - i,0)
        bmai = max(y - i,0)
        l.append(amai*a+bmai*b+i*c)
    print(min(l))
resolve()

Measured memory_bytes: 7064
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <numeric>
#include <deque>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <limits>
#include <cassert>
#include <bitset>
#include <list>
#include <iomanip>
#include <cctype>

#define for0(i, N)    for (long long i = 0  ; i <  (N); ++i)
#define for1n(i, N)   for (long long i = 1  ; i <= (N); ++i)
#define for1(i, N)    for (long long i = 1  ; i <  (N); ++i)
#define forn(i, N)    for (long long i = 0  ; i <= (N); ++i)
#define forx(i, N, x) for (long long i = (x); i <  (N); ++i)
#define forl(i, N, x, a) for (long long i = (x), a = 0; a < (N);    \
                              i = (i + 1) % (N), ++a)
#define int long long

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b + 1;
}

template<size_t i>
std::bitset<i> operator++(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b++;
    return temp;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b, signed){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    return b = (unsigned long long)b - 1;
}

template<size_t i>
std::bitset<i> operator--(std::bitset<i> b){
    static_assert(i <= 64, "Cannot cast 64bit int.");
    auto temp = b;
    b--;
    return temp;
}

long long constexpr inf = std::numeric_limits<long long>::max();

using namespace std;

typedef long long ll;
typedef long double ld;
typedef priority_queue<ll> pq;
typedef priority_queue<ll,vector<ll>, greater<ll>> pql;
typedef stack<ll> stk;
typedef queue<ll> qu;
typedef pair<ll, ll> pll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
typedef set<ll> sll;
typedef unordered_set<ll> usll;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<vector<ll>> vvll;


signed main(void){
    cin.tie(0); ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);
    ll h, w;
    cin >> h >> w;

    if (h == 1 || w == 1) {
        cout << 1;
    } else if (h % 2 == 0 && w % 2 == 0) {
        cout << h * w / 2;
    } else if (h % 2 == 1 && w % 2 == 0) {
        cout << (h - 1) * w / 2 + w / 2;
    } else if (w % 2 == 1 && h % 2 == 0) {
        cout << (w - 1) * h / 2 + h / 2;
    } else {
        cout << (h - 1) * (w - 1) / 2 + (w + h - 1 + 1) / 2;
    }

    return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

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)*}
    };
}

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)*}
    };
}

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, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn divisors(n: usize) -> Vec<usize> {
    let mut divisors = Vec::new();
    // n := i * x とおくと、 i が i > root(n) の時、　i はすでに ある x に探索されているから
    // i <= root(n) まで探索すればよい
    for i in 1..(f64::sqrt(n as f64) + 1e-9) as usize +1 {

        // i で n が割り切れた場合
        if n % i == 0 {
            // 約数リストに格納
            divisors.push(i);

            // n := i * x の x を格納。ただし x := i の時は除く
            if i != n / i {
                divisors.push(n / i);
            }
        }
    }
    divisors.sort();
    divisors
}

fn main() {
    input!{
        n: usize,
        k: usize,
        a: [usize; n],
    }
    let a_sum: usize = a.iter().sum();
    let mut divs = divisors(a_sum);
    divs.reverse();

    for div in divs {
        let mut diffs: Vec<usize> = a.iter().map(|&x| x % div).collect();
        diffs.sort();
        let diffs_sum: usize = diffs.iter().sum();
        let mut acc = 0;
        for i in 0..(n - diffs_sum/div) {
            acc += diffs[i];
        }
        if acc <= k {
            return println!("{}", div)
        }
    }
}


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

int main(){
	int n,x,sum=0;
	cin>>n;
	x=n;
	while(x){
		sum+=x%10;
		x/=10;
	}
	cout<<((n%sum==0)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N+1);
    vector<ll> sum(N+1);
    for(int i=1;i<=N;i++){
        cin >> A[i];
        sum[i]=sum[i-1]+A[i];
    }
    ll half;
    ll min_dif = sum[N];
    for(int i=1;i<N;i++){
        min_dif = min(min_dif,abs(sum[N]-2*sum[i]));
    }
    cout << min_dif << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    vector<int> a(n+1), b(n);
    int i;
    for(i=0; i<n+1; i++) {
        scanf("%d", &a[i]);
    }
    for(i=0; i<n; i++) {
        scanf("%d", &b[i]);
    }

    ll sum=0;
    for(i=0; i<n; i++) {
        int tmp = MIN(a[i], b[i]);
        a[i]-=tmp;
        b[i]-=tmp;
        sum+=tmp;

        tmp = MIN(a[i+1], b[i]);
        a[i+1]-=tmp;
        b[i]-=tmp;
        sum+=tmp;
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 1024
str1 = input()
table = list(str1)
count = 0
ans = 0
for i in range(len(str1)):
    if table[i] == 'A' or table[i] =='T' or table[i] =='C' or table[i] == 'G':
        count += 1
        if ans < count:
            ans = count
    else:
        count = 0
print(ans)

Measured memory_bytes: 9116
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a, b, N, s, f, re=0;
    cin>>a>>b;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>s>>f;
        if(s<=a&&f>=b){
            re=1;
            break;
        }if(s<=a&&a<f){
            re=1;
            break;
        }
        if(i==(N-1)&&a>s&&a<f&&f<b&&a!=f){
            re=1;
            break;
        }
        for(int j=a;j<b;j++){
            if(j==s){
                re=1;
                break;
            }
        }
    }
    if(re==0){
        cout<<"0"<<endl;
    }else{
        cout<<"1"<<endl;
    }
    
}



Measured memory_bytes: 3088
H,W = list(map(int,input().split()))
MAP = [input() for i in range(H)]
  
DP = [[0 for w in range(W)]for h in range(H)]

for w in range(W):
  for h in range(H):
    if h + w == 0:
      if MAP[0][0] == "#":
        DP[0][0] = 1
      continue
    elif h == 0:
      if MAP[h][w-1]+MAP[h][w]==".#": 
        DP[h][w] = DP[h][w-1] +1
      else:
        DP[h][w] = DP[h][w-1]
    elif w == 0:
      if MAP[h-1][w]+MAP[h][w] ==".#": 
        DP[h][w] = DP[h-1][w]+1
      else:
        DP[h][w] = DP[h-1][w]
    else:
      DP[h][w] = min(
        DP[h-1][w] + (1 if MAP[h-1][w]+MAP[h][w] == ".#" else 0),
        DP[h][w-1] + (1 if MAP[h][w-1]+MAP[h][w] == ".#" else 0)
      )

print(DP[-1][-1])  

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

#define rep(i,n) for (int i=0; i<(n); i++)
const int INF =1001001001;
const ll BIG = 1000000007;
const double PI = 3.141592653589793;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> s(m);
    vector<char> c(m);
    rep(i,m){
        cin >> s[i] >> c[i];
    }
    rep(i, 1000){
        string str = to_string(i);
        bool match = true;
        if(str.size()!=n) continue;
        rep(j, m){
            if(str[s[j]-1]!=c[j]) match = false;
        }
        if(match){
            cout << str << endl;
            return 0;
        }
    }
    cout << "-1" << endl;
    return 0;
}

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

int main() {
    int16_t h, w;
    cin >> h >> w;
    char c[h + 2][w + 2];

    for (int16_t i = 0; i < h + 2; i++) {
        c[i][0] = c[i][w + 1] = '.';
    }
    for (int16_t j = 0; j < w + 2; j++) {
        c[0][j] = c[h + 1][j] = '.';
    }
    for (int16_t i = 1; i <= h; i++) {
        for (int16_t j = 1; j <= w; j++) {
            cin >> c[i][j];
        }
    }
    for (int16_t i = 1; i <= h; i++) {
        for (int16_t j = 1; j <= w; j++) {
            if (c[i][j] == '#') {
                if (c[i][j + 1] == '.' && c[i + 1][j] == '.' && c[i][j - 1] == '.' && c[i - 1][j] == '.') {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type Item struct {
	value    int64
	priority int64
	index    int // index of the item in the heap
}

type priorityQueue []*Item

func (pq priorityQueue) Len() int { return len(pq) }
func (pq priorityQueue) Less(i, j int) bool {
	// Pop returns items in ascending order
	return pq[i].priority < pq[j].priority
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *priorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

func max(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func main() {
	n := 0
	fmt.Scan(&n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	a := make([]int64, 3*n)
	for i := range a {
		sc.Scan()
		v, err := strconv.Atoi(sc.Text())
		if err != nil {
			panic("invalid format")
		}
		a[i] = int64(v)
	}

	// priority queue in ascending order
	left := make([]int64, n+1)
	{
		pq := make(priorityQueue, n)
		for i := 0; i < n; i++ {
			left[0] += a[i]
			pq[i] = &Item{value: a[i], priority: a[i], index: i}
		}
		heap.Init(&pq)
		for k := n; k < 2*n; k++ {
			heap.Push(&pq, &Item{value: a[k], priority: a[k], index: k})
			top := heap.Pop(&pq).(*Item)
			left[k+1-n] = left[k-n] + a[k] - top.value
		}
	}

	// priority queue in descending order
	right := make([]int64, n+1)
	{
		pq := make(priorityQueue, 0, n)
		for i := 3*n - 1; i >= 2*n; i-- {
			right[n] += a[i]
			pq = append(pq, &Item{value: a[i], priority: -a[i], index: i})
		}
		heap.Init(&pq)
		for k := 2*n - 1; k >= n; k-- {
			heap.Push(&pq, &Item{value: a[k], priority: -a[k], index: k})
			top := heap.Pop(&pq).(*Item)
			right[k-n] = right[k+1-n] + a[k] - top.value
		}
	}

	ans := int64(-(1 << 63))
	for i := 0; i <= n; i++ {
		ans = max(ans, left[i]-right[i])
	}
	fmt.Println(ans)
}


Measured memory_bytes: 15496
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N, K, n, count=0;
  std::cin >> N >> K;
  std::vector<int> A(N);
  range(i, N) std::cin >> A[i];
  n = N;
  while(true){
    n-=K;
    count++;
    if(n<=0)break;
    n++;
  }
  std::cout << count << '\n';
  return 0;
}


Measured memory_bytes: 640
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;

public class Main implements Runnable {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
    }

    public void run() {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void solve() throws IOException {
        char[] s = in.nextToken().toCharArray();
        System.out.println(s[0] + "" + (s.length - 2) + "" + s[s.length - 1]);
    }
}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException {super(System.out);}
}
class ContestScanner implements Closeable {
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}

Measured memory_bytes: 21460
N = int(input())
h = list(map(int,input().split()))

INF = float('inf')

DP = [INF]*N

DP[0] = 0

for i in range(N-1):
    if i>0:
        DP[i+1] = min(DP[i-1] + abs(h[i+1]-h[i-1]), DP[i] + abs(h[i+1]-h[i]))
    else:
        DP[i+1] = DP[i] + abs(h[i+1]-h[i])

print(DP[N-1])

Measured memory_bytes: 52208
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
#define ub(a,x) (upper_bound(ALL(a),x)-a.begin())
#define lb(a,x) (lower_bound(ALL(a),x)-a.begin())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int N;string S;
    cin>>N>>S;
    vi wpos(0),rpos(0);
    for(int i=0;i<N;i++){
        if(S[i]=='W'){
            wpos.push_back(i);
        }else{
            rpos.push_back(i);
        }
    }
    reverse(ALL(rpos));
    int ans=0;
    int wL=wpos.size(),rL=rpos.size();
    for(int i=0;i<N;i++){
        if(i>=wL || i>=rL)break;
        if(wpos[i]<rpos[i]){
            S[wpos[i]]='R';
            S[rpos[i]]='W';
            ans++;
            //cout<<S<<endl;
        }else{
            break;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4868
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	string s;
	int q;

	cin >> s;
	cin >> q;

	string op, p;
	int a, b;

	while(q--) {
		cin >> op >> a >> b;

		if(op == "print") {
			cout << s.substr(a, b - a + 1) << endl;
		} else if(op == "reverse") {
			reverse(s.begin() + a, s.begin() + b + 1);
		} else {
			cin >> p;
			s.replace(a, b - a + 1, p);
		}
	}
}



Measured memory_bytes: 3228
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
using ll = long long;
using p_i = pair<int, int>;
int main() {
	int A, B, C, D, E, F;	cin >> A >> B >> C >> D >> E >> F;
	ll water, sugar, ANSwater = 0, ANSsugar = 0;
	long double concen, ANSconcen = 0;
	rep(i, 31) {
		rep(j, 31) {
			rep(k, 101) {
				rep(l, 101) {
					water = (i*A + j * B) * 100;
					sugar = k * C + l * D;
					if (water + sugar > F)continue;
					if (!(water + sugar))continue;
					if (water / 100 * E < sugar)continue;
					concen = (long double)(100 * sugar) / (water + sugar);
					if (concen >= ANSconcen) {
						ANSwater = water;
						ANSsugar = sugar;
						ANSconcen = concen;
					}

				}
			}
		}
	}
	cout << ANSwater + ANSsugar << " " << ANSsugar << endl;
	cin >> A;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  long long X=1;
  
  for (int i=1; i<=N; i++) {
    X *= i;
    X %= 1000000007;
  }
    cout << X;
  return 0;
}

  
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll a[100010];
int main() {
	ll n;
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	ll mi=2,ma=2;
	for(ll i=n-1;i>=0;i--){
		mi=(mi+a[i]-1)/a[i]*a[i];
		ma=(ma/a[i]+1)*a[i]-1;
		if(mi>ma){
			cout <<-1<<endl;
			return 0;
		}
		//cout << mi<<" "<<ma<<endl;
	}
	cout << mi<<" "<<ma;
	// your code goes here
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <random>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
int calc(VI x){
	int n = x.size();
	if (n <= 1) return 0;
 
	// for (int p : x) cout << p << " ";
	// cout << endl;
 
	VVI dp(n, VI(5));
	dp[0][1] = x[0];
	dp[0][2] = x[1] - 1;
	dp[0][3] = x[1];
	REP(i,n-2){
		if (x[i+1] > 1){
			dp[i+1][0] = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
			dp[i+1][1] = max({dp[i][0] + x[i+1], dp[i][1] + x[i+1] - 1});
			dp[i+1][2] = max({dp[i][0], dp[i][1], dp[i][2]}) + x[i+2] - 1;
			dp[i+1][3] = max({dp[i][0], dp[i][1], dp[i][2]}) + x[i+2];
		}else{
			dp[i+1][0] = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
			dp[i+1][1] = max({dp[i][0] + x[i+1]});
			dp[i+1][2] = max({dp[i][0]}) + x[i+2] - 1;
			dp[i+1][3] = max({dp[i][0]}) + x[i+2];
		}
	}
	int ret = *max_element(ALL(dp[n-2]));
	// cout << ret << endl;
	return ret;
}
 
int main() {
	int n;
	string s;
	cin >> n >> s;
 
	int ans = 0;
	VI one;
	int x = 0;
	REP(i,n){
		int p = s[i] - '0';
		if (p == 1){
			x++;
		}else{
			if (x){
				one.push_back(x);
				x = 0;
			}else{
				ans += calc(one);
				one.clear();
			}
		}
	}
 
	if (x) one.push_back(x);
	ans += calc(one);
 
	cout << ans << endl;
 
    
    return 0;
}

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

int main(){
	int n,d,x;scanf("%d%d%d",&n,&d,&x);
	rep(i,n){
		int a;scanf("%d",&a);
		x+=(d-1)/a+1;
	}
	cout<<x<<endl;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

ll N,K;
ll i, j, k;
int main(){
    scanf("%lld%lld", &N, &K);
    i = 0;
    while(N){
        ++i;
        N /= K;
    }
    printf("%lld", i);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,(n)-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,(n)-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int main(){
    ll x,k,d;
    cin >> x >> k >> d;
    x = abs(x);
    ll ans;
    if(k <= x/d){
        ans = x - k*d;
    }else{
        ll nokori = k - x/d;
        if(nokori%2 == 0)ans = x%d;
        else ans = d-x%d;
        // ans = min(x%d,d-x%d);
    }

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

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

set<vector<int>> S;
int P,Q,A,N;

struct Frac{
    int p,q;//frac{p}{q}
    Frac(int P, int Q){
        p=P; q=Q;
    }
    int gcd(int a, int b){
        if(b==0) return a;
        return gcd(b,a%b);
    }
    void reduce(){
        int d=gcd(p,q);
        if(d<0)d=-d;
        p/=d; q/=d;
    }
    Frac operator*(const Frac& F){
        Frac ret(p*F.p,q*F.q);
        ret.reduce();
        return ret;
    }
    Frac operator*(int d){
        Frac ret(p*d,q);
        ret.reduce();
        return ret;
    }
    Frac operator/(const Frac& F){
        Frac ret(p*F.q,q*F.p);
        ret.reduce();
        return ret;
    }
    Frac operator/(int d){
        Frac ret(p,q*d);
        ret.reduce();
        return ret;
    }
    Frac operator+(const Frac& F){
        Frac ret(p*F.q+q*F.p,q*F.q);
        ret.reduce();
        return ret;
    }
    Frac operator+(int d){
        Frac ret(p+q*d,q);
        ret.reduce();
        return ret;
    }
    Frac operator-(const Frac& F){
        Frac ret(p*F.q-q*F.p,q*F.q);
        ret.reduce();
        return ret;
    }
    Frac operator-(int d){
        Frac ret(p-q*d,q);
        ret.reduce();
        return ret;
    }
    bool operator<(const Frac& F){
        Frac ret(p*F.q-q*F.p,q*F.q);
        ret.reduce();
        return ret.p<0;
    }
    bool operator<=(const Frac& F){
        Frac ret(p*F.q-q*F.p,q*F.q);
        ret.reduce();
        return ret.p<=0;
    }
};

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

int rec(int rmin, int p, int q, int n){
    if(p*Q==q*P) return 1;
    if(n<=0||p*Q>q*P) return 0;
    int ret=0;
    for(int r=rmin;q*r<=A;r++){
        ret+=rec(r,p*r+q,q*r,n-1);
    }
    return ret;
}

int main(){
    while(cin>>P>>Q>>A>>N,P){
        cout<<rec(1,0,1,N)<<endl;
    }
    return 0;
}

Measured memory_bytes: 2988
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    check = [[True]*n for i in range(n)]
    d =  [[min(i, n-i-1, j, n-j-1) for j in range(n)] for i in range(n)]

    ans = 0
    for t in l:
        t -=1
        x = t//n
        y = t%n
        check[x][y] = False
        ans += d[x][y]
        q = []
        q.append((x,y,d[x][y]))
        while q:
            bx,by,z = q.pop()

            if bx != 0:
                if d[bx-1][by] > z:
                    d[bx-1][by] = z
                    q.append((bx-1,by,z+check[bx-1][by]))
            if bx != n-1:
                if d[bx+1][by] > z:
                    d[bx+1][by] = z
                    q.append((bx+1,by,z+check[bx+1][by]))
            if by != 0:
                if d[bx][by-1] > z:
                    d[bx][by-1] = z
                    q.append((bx,by-1,z+check[bx][by-1]))
            if by != n-1:
                if d[bx][by+1] > z:
                    d[bx][by+1] = z
                    q.append((bx,by+1,z+check[bx][by+1]))  
    print(ans)
if __name__ =="__main__":
    main()

Measured memory_bytes: 194232
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def sol():
    N = int(input())
    A = [int(x) for x in input().split()]

    oddCount = 0
    for a in A:
        if a % 2 == 1:
            oddCount += 1

    if oddCount % 2 == 0:
        print('YES')
    else:
        print('NO')


sol()

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

#define ll long long

typedef pair< int, int > ii;
typedef vector< ii > vii;

void solve(){
	int n; cin>>n;
	int sum = 0;
	vector< int > v(n);
	for(int &i : v){
		cin>>i;
		sum += i;
	}
	sort(v.rbegin(), v.rend());
	int ans = 0;
	for(int i = 0; i<n; i+=2){
		ans += v[i];
	}
	cout<<ans - (sum - ans)<<endl;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}



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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
#define Size(n) (n).size()

typedef long long ll;

using namespace std;

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

//long long int kaizyo(long long int hh){
  //  cmp=1;
    //while(hh>1){
      //  cmp=(cmp*hh)%MOD;
        //hh--;
    //}
    //return cmp;
//}
//long long int ruizyo(long long int aa, long long int bb){
  //  if(aa==0){
    //    return 1;
    //}
    //else if(aa%2==0){
      //  long long int tt=ruizyo(aa/2,bb);
        //return (tt*tt)%MOD;
    //}
    //else{
      //  return (ruizyo(aa-1,bb)*bb)%MOD;
    //}
//}フェルマ－のア


//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

//bool f[100001];//1000000以下の素数を調べよう！
//rrep(i,2,100001){
  //      f[i]=false;
    //}
//rrep(i,2,100001){
  //      if(!f[i]){
    //        for(int j=i+i;j<=100000;j+=i){
      //          f[j]=true;
        //    }
        //}
    //}
    //for(int i=3;i<=100000;i+=2){
      //  if(!f[i]){
        //    c[i]++;
      //  }
   // }

//visited=vector<vector<bool>>(10,vector<bool>(10,false));アを全部falseに


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz");
char s[102][102];
bool fl=true;

//-------------------------↓↓↓↓↓↓----------------------------

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

       cin >> h >> w;
      rep(i,h){
          rep(j,w){
              cin>>s[i][j];
          }
      }
      rep(i,w+2){
          cout << '#' ;
      }
      cout << endl;
      rep(i,h){
          cout << '#';
          rep(j,w){
              cout<< s[i][j];
          }
          cout << '#' << endl;
      }
      rep(i,w+2){
          cout << '#' ;
      }
      cout << endl;
return 0;
}


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

template<typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  return gcd(b%a, a);
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);

  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) { cin >> a[i]; }

  vector<ll> left_gcd(n);  
  left_gcd[0] = a[0];
  for (int i = 1; i < n - 1; ++i) {
    left_gcd[i] = gcd(left_gcd[i-1], a[i]);
  }
  
  vector<ll> right_gcd(n);  
  right_gcd[n-1] = a[n-1];
  for (int i = n-2; i > 0; --i) {
    right_gcd[i] = gcd(right_gcd[i+1], a[i]);
  }
  
  ll ans = max(left_gcd[n-2], right_gcd[1]);
  for (int i = 1; i < n - 1; ++i) {
    ans = max(ans, gcd(left_gcd[i-1], right_gcd[i+1])); 
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
    ll a, v, b, w, t;
    cin >> a >> v;
    cin >> b >> w;
    cin >> t;

    if (v < w) {
        cout << "NO" << endl;
    } else if (v == w) {
        if (a == b) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    } else {
        if (a < b) {
            if ((b-a) > (v-w)*t) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        } else if (a == b) {
            cout << "YES" << endl;
        } else {
            if ((a-b) > (v-w)*t) {
                cout << "NO" << endl;
            } else {
                cout << "YES" << endl;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3620