akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

class Main {
  static int solve(int a, int b, int n) {
    if(n==0) {
      return 0; 
    }
    return ((a * 10) / b + solve(a * 10 % b, b, n - 1));
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()) {
      String[] arr = sc.nextLine().split(" ");
      int a = Integer.parseInt(arr[0]);
      int b = Integer.parseInt(arr[1]);
      int n = Integer.parseInt(arr[2]);
      System.out.println(solve(a % b, b, n));
    }
  }
}

Measured memory_bytes: 26336
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 203808
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int count = 0;
		long min = Long.MAX_VALUE;
		long total = 0;
		for (int i = 0; i < n; i++) {
			long a = sc.nextInt();
			if (a < 0) {
				total -= a;
				count++;
			} else {
				total += a;
			}
			min = Math.min(min, Math.abs(a));
		}
		if (count % 2 == 1) {
			total -= min * 2;
		}
		System.out.println(total);
	}
}


Measured memory_bytes: 49648
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

print(sum(A[:K]))

Measured memory_bytes: 3700
import math
count = 0
n = int(input())

def ifprime(num):
  for i in range(2,math.floor(num ** 0.5) + 1):
    if num % i:
      continue
    else:
      return False
  return True

for _ in range(n):
  a = int(input())
  if ifprime(a):
    count += 1

print(count)


Measured memory_bytes: 5764
fun main(args: Array<String>) {
    val countFood = readLine()!!.toInt()
    val eatOrder = readLine()!!.split(" ").map { it.toInt() - 1 }
    val happiness = readLine()!!.split(" ").map { it.toInt() }
    val bonus = readLine()!!.split(" ").map { it.toInt() }
    var lastEat = -99
    var current = 0

    for (element in eatOrder) {
        if (lastEat == element - 1) {
            current += happiness[element] + bonus[lastEat]
            lastEat = element
        } else {
            current += happiness[element]
            lastEat = element
        }
    }
    print(current)
}

Measured memory_bytes: 37864
#include <cstdio>

using namespace std;

const int mod = 1000000007;

int gcd(int x, int y) {
    if (x % y == 0) {
        return y;
    } else {
        return gcd(y, x % y);
    }
}

long long powmod(long long x, long long y) {
    long long ans = 1;
    
    while (y > 0) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    
    return ans;
}

int main() {
    int h, w, t;
    long long gh, gw, g, x;
    
    scanf("%d %d %d", &h, &w, &t);
    
    gh = gcd(h, t);
    gw = gcd(w, t);
    g = gcd(h / gh, w / gw);
    
    x = (powmod(2, g) + powmod(2, h / gh) + powmod(2, w / gw) - 3 + mod) % mod;
    
    printf("%lld\n", powmod(x, gh * gw));
    
    return 0;
}


Measured memory_bytes: 128
def divisors(n)
  r = []
  1.upto(n) do |i|
    break unless i <= n / i
    next unless (n % i).zero?
    r << i
    r << n / i if i != n / i
  end
  r
end
A,B=gets.split.map(&:to_i)
r=[]
(divisors(A) & divisors(B)).sort.each do |d|
  r << d if r.all?{|i| d.gcd(i)==1}
end
p r.size

Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
typedef     long long    ll;
typedef     vector<int> vi;
typedef     vector<long long> vl;
typedef     pair<int, int>pi;
typedef     pair<long long, long long>pl;
#define F   first
#define S   second
#define pb  push_back
#define     all(x)      x.begin() , x.end()
#define mp  make_pair
#define       FOR(i,a,b) for(i=a;i<=b;i++)
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)
 int main()
 {
     ll t,a,b,x,y;
     cin>>a>>b>>t;
     if(t<=a)
     {
      a=a-t;
     }else
     {
      t=t-a;
      a=0;
       b=b-t;
     }
     b=max(ll(0),b);
     cout<<a<<" "<<b<<endl;
 }

Measured memory_bytes: 3600
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string a,b;
    cin>>a>>b;
    int count = 0;
    for( int i = 0; i < a.size(); i++ )
    {
        if(a[i]!=b[i])
        {
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3768
<?php

ini_set('error_reporting', E_ALL & ~E_NOTICE & ~E_WARNING);
ini_set('display_errors', 'Off');

// define('DEBUG', true);
define('DEBUG', false);

fscanf(STDIN, "%d", $n);
$a = explode(" ", trim(fgets(STDIN)));

$ans = array();

for ($i = 0; $i < $n; $i++) {
    $aa = $n - $i * 2;
    $bb = $i * 2 - $n + 1;
    $cc = max($aa, $bb);
    // echo "{$i} {$cc}\n";
    $ans[$i] = $a[$cc-1];
}

echo implode(" ", $ans) . PHP_EOL;


Measured memory_bytes: 33520
// Aizu Vol-2 0241: Quaternion Multiplication
// 2017.8.8

#include <stdio.h>

int main()
{
	int n;
	int x1, y1, z1, w1;
	int x2, y2, z2, w2;
	int x3, y3, z3, w3;
	
	while (1) {
		scanf("%d", &n); if (n == 0) break;
		while (n-- > 0) {
			scanf("%d%d%d%d", &x1, &y1, &z1, &w1);
			scanf("%d%d%d%d", &x2, &y2, &z2, &w2);
			x3 = x1*x2 - y1*y2 - z1*z2 - w1*w2;
			y3 = x1*y2 + y1*x2 + z1*w2 - w1*z2;
			z3 = x1*z2 - y1*w2 + z1*x2 + w1*y2;
			w3 = x1*w2 + y1*z2 - z1*y2 + w1*x2;
			printf("%d %d %d %d\n", x3, y3, z3, w3);
		}
	}
	return 0;
}

Measured memory_bytes: 600
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

A, B, K = [int(i) for i in readline().split(' ')]

j = -1
a = A
b = B
if a < b:
  a,b = b,a
while True:
  j =  a % b
  if j == 0:
    break
  a = b
  b = j

pn = list()
if K == 1:
  print(b)

j = 2
for i in range(b//2, 0, -1):
  if b % i == 0:
    if j == K:
      print(i)
    j += 1 


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

int yagi;
int ushi;
int shika;
char uma;
int hiru;
char a[100000000];
char b[100000000];
int main(){
	while (true){
		cin >> ushi;
		if (ushi == 0){
			break;
		}
		for (int i = 0; i < ushi; i++){
			cin >> a[i] >> b[i];
		}
		cin >> shika;
		for (int j = 0; j < shika; j++){
			cin >> uma;
			hiru = 0;
			for (int k = 0; k < ushi; k++){
				if (uma == a[k]){
					cout << b[k];
					hiru = 1;
				}
			}
			if (hiru == 0){
				cout << uma;
			}
		}
		cout << endl;
	}
}

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

int main(void){
    long long n,k;
    cin >> n >> k;
    
    vector<long long> v(100010,0);
    for(int i = 0;i < n;i++){
        int a,b;
        cin >> a >> b;
        v[a-1] += b;
    }
    
    for(int i = 0;i < 100000;i++){
        k -= v[i];
        if(k <= 0){
            cout << i + 1 << endl;
            break;
        }
    }
}

Measured memory_bytes: 3984
#include<stdio.h>
int main(){
  int sx,sy,tx,ty,i;
  scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
  for(i=0;i<ty-sy;i++)printf("U");
  for(i=0;i<=tx-sx;i++)printf("R");
  for(i=0;i<=ty-sy;i++)printf("D");
  for(i=0;i<=tx-sx;i++)printf("L");
  printf("UL");
  for(i=0;i<=ty-sy;i++)printf("U");
  for(i=0;i<=tx-sx;i++)printf("R");
  for(i=0;i<=ty-sy;i++)printf("D");
  for(i=0;i<tx-sx;i++)printf("L");

}


Measured memory_bytes: 128
N=int(input())
L=[]
if N==1:
    print(1)
    exit()
for i in range(N):
    x,y=map(int, input().split())
    L.append((x,y))

D={}
for i in range(N-1):
    t1=L[i]
    L2=L[i+1:]
    for t2 in L2:
        x1,y1=t1
        x2,y2=t2
        d1=(x2-x1,y2-y1)
        d2=(x1-x2,y1-y2)
        if d1 in D:
            D[(x2-x1,y2-y1)]+=1
        else:
            D[(x2-x1,y2-y1)]=1
        if d2 in D:
            D[(x1-x2,y1-y2)]+=1
        else:
            D[(x1-x2,y1-y2)]=1

print(max(N-max(D.values()),0))


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
const long long INF = 1LL << 60;

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

int main()
{
    int n,w; cin >> n >> w;
    //最大化DPのため初期化
    vector<vector<ll> > dp(w+1,vector<ll>(n+1,0));
    vector<ll> weight(n+1,0);
    vector<ll> value(n+1,0);

    for(int i=0;i<n;i++) cin >> weight[i] >> value[i];

    for(int i=0;i <= w;i++){
        for(int j=0;j<n;j++){

            //iの重さより小さくて、w以下であれば
            if(i - weight[j] >= 0)
                chmax(dp[i][j+1],dp[i-weight[j]][j] + value[j]);

            chmax(dp[i][j+1],dp[i][j]);
        }

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

Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define ll long long
int main(){
  string S;
  cin>>S;
  rep(i,3){
    if(S[i]=='1') cout<<'9';
    else if(S[i]=='9') cout<<'1';
    else cout<<S[i];
  }
  cout<<endl;
}

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

using namespace std;

const int MAXN = 1e5 + 10;

long long dp[MAXN];

int main() {
    #ifdef BLAT
        freopen("input", "r", stdin);
    #endif

    int n;
    cin >> n;
    int w;
    cin >> w;

    long long ans = 0;
    for(int i = 1; i <= n; ++i) {
    	int a, b;
    	cin >> a >> b;

    	for(int j = w - a; j >= 0; --j) {
    		dp[j + a] = max(dp[j + a], dp[j] + b);
    	}
    } 

    cout << dp[w] << '\n';
}  

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N,W;cin>>N>>W;
    vector<ll> w(N),v(N);
    rep(i,N)cin>>w[i]>>v[i];
    vector<vector<ll>> dp(N+1);//iまでで価値jにする最小の重さ
    dp[0]=vector<ll>(1000*N+1,INF);
    dp[0][0]=0;
    for(ll i=1; i<=N; i++){
        dp[i]=dp[i-1];
        for(ll j=v[i-1]; j<=1000*N; j++){
            dp[i][j]=min(dp[i][j],dp[i-1][j-v[i-1]]+w[i-1]);
        }
    }
    ll ans = 0;
    for(ll j=0; j<=1000*N; j++){
        if(dp[N][j]<=W)ans=max(ans,j);
    }
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 79488
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long
#define mod 1000000007
#define do double
#define loop(i,n) for(int i=0;i<n;i++)
#define lop(a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define mkp make_pair

typedef vector <int> vi;
typedef map <int,int> mii;
typedef set <int> si;
typedef pair <int,int> pii;
typedef unordered_map <int,int> um;
typedef unordered_set <int> us;
typedef multiset <int> ms;
typedef vector < pair <int,int> > vpii;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin>>n;
  int h[n],dp[n]={};
  loop(i,n) 
  {
    cin>>h[i];
  }
   dp[1]=abs(h[1]-h[0]);
   for(int i=1;i<n-1;i++)
   {
      dp[i+1]= min(dp[i]+abs(h[i+1]-h[i]), dp[i-1]+abs(h[i+1]-h[i-1]));
   }
  cout<<dp[n-1]<<"\n";
}

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

int calcNot(int x){
    if(x == 0){
        return 2;
    }
    if(x == 1){
        return 1;
    }
    return 0;
}

int calcAnd(int x, int y){
    if(x == 0 || y == 0){
        return 0;
    }
    if(x == 2 && y == 2){
        return 2;
    }
    return 1;
}

int calcOr(int x, int y){
    if(x == 2 || y == 2){
        return 2;
    }
    if(x == 0 && y == 0){
        return 0;
    }
    return 1;
}

int calc(string s){
    if((int)s.size() == 1){
        return stod(s);
    }

    if(s[0] == '-'){
        return calcNot(calc(s.substr(1, (int)s.size() - 1)));
    }

    int lhsStart = 0;
    int lhsLen = 0;
    int rhsStart = 0;
    int rhsLen = 0;
    int depth = 0;
    for(int i = 0; i < (int)s.size(); i++){

        char temp = s[i];
        if(temp == '('){
            depth++;
        }
        else if(temp == ')'){
            depth--;
        }
        else if(depth == 1 && temp == '+'){
            return calcOr(calc(s.substr(1, i - 1)), calc(s.substr(i + 1, (int)s.size() - i - 2)));
        }
        else if(depth == 1 && temp == '*'){
            return calcAnd(calc(s.substr(1, i - 1)), calc(s.substr(i + 1, (int)s.size() - i - 2)));
        }
    }

    return 0;
}

int main(){

    while(true){
        string s;
        cin >> s;
        if(s == "."){
            break;
        }

        int ans = 0;
        for(int p = 0; p <= 2; p++){
            for(int q = 0; q <= 2; q++){
                for(int r = 0; r <= 2; r++){
                    string tempStr = s;
                    replace(tempStr.begin(), tempStr.end(), 'P', (char)('0' + p));
                    replace(tempStr.begin(), tempStr.end(), 'Q', (char)('0' + q));
                    replace(tempStr.begin(), tempStr.end(), 'R', (char)('0' + r));

                    int temp = calc(tempStr);
                    if(temp == 2){
                        ans++;
                    }
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3260
#include<iostream>
#include<algorithm>

using namespace std;

int N;

int a[3003];

int main(void) {

	cin >> N;

	int tmp;

	for (int i = 1; i <= N; i++) {
		cin >> tmp; a[i] = tmp;
	}


	int ans = 0;

	for (int i = 1; i <= N; i++) {
		ans += a[i] - 1;
	}
	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
typedef vector<LL> vl;
typedef pair<LL, LL> pl;
typedef vector<pair<LL, LL>> VP;
typedef tuple<LL, LL, LL> tl;
const LL N=pow(10, 9)+7;
#define endl "\n"
#define REP(i, a, b) for(LL i=a; i<b; i++)
#define RREP(i, a, b) for(LL i=a; i>b; i--)
#define WE(i) while(i--)
#define PB push_back
#define PF pop_front
#define MP make_pair
#define MT make_tuple
#define F first
#define S second

LL sod(LL a)
{
    LL sum=0;
    while(a!=0)
    {
        sum=sum+a%10;
        a=a/10;
    }
    return sum;
}

LL num1(LL a)
{
    LL s=0;
    while(a!=0){
        if(a%2==1){
            s++;
        }
        a=a/2;
    }
    return s;
}

LL bmod(string s, LL a)
{
    LL res=0;
    REP(i, 0, s.length()){
        res=(10*res+(LL)s[i]-'0')%a;
    }
    return res;
}

void pd(LL n) 
{ 
    LL ans=0, x=sqrt(n);
    if(x%1==0){
        REP(i, 1, x+1){
            if(n%i==0){
                ans+=2;
            }
            if(n==i*i){
                ans--;
            }
        }
    }
    else{
        REP(i, 0, x){
            if(n%i==0){
                ans+=2;
            }
        }
    }
    cout << ans << endl;
}

LL solve()
{
    LL a;
    string s;
    cin >> a >> s;
    if(a<3200){
        cout << "red" << endl;
    }
    else{
        cout << s << endl;
    }
    return 0;
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    LL T=1;
    //cin >> T;

    WE(T){
        solve();
    }
    return 0;
}

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

void solve(long long L, long long R, long long d){
    cout << (R/d) -(L-1)/d << endl;

}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long L;
    scanf("%lld",&L);
    long long R;
    scanf("%lld",&R);
    long long d;
    scanf("%lld",&d);
    solve(L, R, d);
    return 0;
}


Measured memory_bytes: 3756
//133 B - GOod Distance 2019/07/07
#include <bits/stdc++.h>
#define rep(i ,n) for(int i=0;i<(int)(n);++i)
using namespace std;
typedef long long int int64;
typedef unsigned long long uint64;

int main(){
    int n , d; 
    cin >> n >> d;
    vector<vector<int>> x(n,vector<int>(d));
    rep(i,n){
        rep(j,d){
            cin >> x.at(i).at(j);
        }
    }
    long double dis=0;
    int ans=0;
    rep(i,n){
        for(int j=i+1;j<n;++j){
            int tmp=0;
            rep(k ,d){
            tmp+=(x.at(i).at(k)-x.at(j).at(k))*(x.at(i).at(k)-x.at(j).at(k));            
            }
        dis=sqrt(tmp);
        if(floor(dis)==dis) ++ans;
        }
    }    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        #include<iostream>
        #include<cstdio>
        #include<vector>
        #include<queue>
        #include<map>
        #include<cstring>
        #include<string>
        #include <math.h>
        #include<algorithm>
    //    #include <boost/multiprecision/cpp_int.hpp>
        #include<functional>
      #define int long long
        #define inf  1000000007
        #define pa pair<int,int>
#define ll long long
        #define pal pair<ll,ll>
        #define ppa pair<int,pa>
        #define  mp make_pair
        #define EPS (1e-10)
        #define equals(a,b) (fabs((a)-(b))<EPS)

        using namespace std;

        class Point{
        	public:
        	double x,y;
        	Point(double x=0,double y=0):x(x),y(y) {}
        	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
        	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
        	Point operator * (double a) {return Point(x*a,y*a);}
        	Point operator / (double a) {return Point(x/a,y/a);}
        	double absv() {return sqrt(norm());}
        	double norm() {return x*x+y*y;}
        	bool operator < (const Point &p) const{
        		return x != p.x ? x<p.x: y<p.y;
        	}
        	bool operator == (const Point &p) const{
        		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
        	}
        };
        typedef Point Vector;

        struct Segment{
        Point p1,p2;
        };

    double hen(Vector a){
    if(fabs(a.x)<EPS && a.y>0) return acos(0);
    else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
    else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
    else if(fabs(a.y)<EPS && a.x>0) return 0.0;
    else if(a.y>0) return acos(a.x/a.absv());
    else return 2*acos(0)+acos(-a.x/a.absv());

    }

        double dot(Vector a,Vector b){
        	return a.x*b.x+a.y*b.y;
        }
        double cross(Vector a,Vector b){
        	return a.x*b.y-a.y*b.x;
        }
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, 1, 0, -1};
        //----------------kokomade temple------------

vector<pa> ve;
int a[100002];
signed main(){
int n;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	int d=1;
	
	for(int i=1;i<=n;i++){
		if(i==1){
			ans += a[i]-1;
			a[i]=1;
			continue;
		}
		if(d>=a[i]) continue;
		if(a[i]==d+1) {
			d++;
			continue;
		}
		int k=(a[i])/(d+1);
//		if(k==0) k++;
		if((a[i])%(d+1)==0) k--;
		ans += k;
	//	cout<<d<<" "<<k<<endl;
		
	}
	
	
	cout<<ans<<endl;
	return 0;
}

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


Measured memory_bytes: 1152
a, b, c, x = 4.times.map{gets.to_i}
cnt = 0
(0..a).each do |i|
    (0..b).each do |j|
        (0..c).each do |k|
            cnt += 1 if i * 500 + j * 100 + k * 50 == x
        end
    end
end
puts cnt

Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
#define M 100005
#define P 1000000007
int tot,i,n,k,a,b,h[M],nx[M<<1],r[M<<1];
long long ans;
void add(int x,int y) {
	r[++tot]=y,nx[tot]=h[x],h[x]=tot;
}
void dfs(int x,int f) {
	int cnt=(f>0?2:1);
	for(int i=h[x]; i!=-1; i=nx[i])
		if(r[i]!=f)
			ans=ans*(k-cnt)%P,dfs(r[i],x),cnt++;
}
int main() {
	scanf("%d%d",&n,&k),memset(h,-1,sizeof(h));
	for(i=1; i<n; i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
	ans=k,dfs(1,0),printf("%lld\n",ans);
	return 0;
}

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

const int MAX_N = 3000;

int main() {
    for (int i = 0; i < MAX_N; i++) {
        int x, y;
        cin >> x >> y;
        if (x == 0 && y == 0) {
            break;
        } else {
            if (x < y) {
                cout << x << " " << y << endl;
            } else {
                cout << y << " " << x << endl;
            }
        }    
    }
    return 0;
}


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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  ll N, M;
  cin >> N >> M;
  if (N > M) swap(N, M);
  if (N == 1 && M == 1) cout << 1 << endl;
  else if (N == 1) cout << M - 2 << endl;
  else cout << N * M - 2 * (N + M) + 4 << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int main(){

	int N,M;
	scanf("%d %d",&N,&M);

	printf("%d\n",N*M);

	return 0;
}



Measured memory_bytes: 3200
n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)


Measured memory_bytes: 118072
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

char ba[1000][1000];
int dist[1000][1000];
int aku[1000][1000];
struct P {
  int x,y;
  int t;
  P(int y, int x, int t) : y(y),x(x),t(t) {}
};

bool operator<(const P &a, const P &b) {
  return a.t > b.t;
}

int main() {
  int w,h;
  cin >> w >> h;
  priority_queue<P> Q;
  REP(i,h) {
    REP(j,w) {
      cin >> ba[i][j];
    }
  }
  int n;
  cin >> n;
  memset(aku,0,sizeof(aku));
  REP(i, h) {
    REP(j, w) {
      if (ba[i][j] == '#') aku[i][j] = INF;
    }
  }
  REP(i, n) {
    int x, y;
    cin >> x >> y;
    aku[y][x] = i+1;
  }
  
  Q.push(P(0,0,0));
  REP(i,h) REP(j,w) dist[i][j] = INF;
  dist[0][0] = 0;
  int dy[] = {-1,0,1,0};
  int dx[] = {0,1,0,-1};
  int ans = -1;
  while(!Q.empty()) {
    P p = Q.top(); Q.pop();
    if (dist[p.y][p.x] < p.t) continue;
    
    if (ba[p.y][p.x] == 't') {
      ans = p.t;
      break;
    }
    
    REP(i, 4) {
      int yy = p.y+dy[i];
      int xx = p.x+dx[i];
      
      if (yy<0||yy>=h||xx<0||xx>=w) continue;
      int d = max(aku[yy][xx], dist[p.y][p.x]);
      if (d == INF) continue;
      if (dist[yy][xx] > d) {
	dist[yy][xx] = d;
	Q.push(P(yy,xx,d));
      } 
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 14000
#include <bits/stdc++.h>
#define int long long
#define H 8
#define W 8
using namespace std;
const int INF = 1LL<<55;
int Max(int &a,int b){return a=max(a,b);}
int Min(int &a,int b){return a=min(a,b);}

int mp[H][W],used[W];

bool check(int sy,int sx){
  if(used[sx]) return 0;
  int dx[] ={1,-1,1,-1};
  int dy[] ={1,-1,-1,1};
  int res = 1;
  for(int i=0;i<4;i++){
    int x = sx,y = sy;
    while(x>=0 && y>=0 && x<W && y<H){
      res &= mp[y][x] == 0;
      x += dx[i];
      y += dy[i];
    }

  }
  return res;
}

void dfs(int y){
  if(y == H){
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++)cout<< (mp[i][j]? 'Q':'.');
      cout<<endl;
    }
    exit(0);
    return;
  }

  for(int i=0;i<W;i++)if(mp[y][i] == 1){ dfs(y+1);return;}
  for(int i=0;i<W;i++){
    if(!check(y,i))continue;
    used[i] = mp[y][i] = 1;
    dfs(y+1);
    mp[y][i] =  used[i] = 0;
  }
}

signed main(){
  int n;
  cin>>n;
  for(int i=0,y,x;i<n;i++){
    cin>>y>>x;
    mp[y][x] = 1;
    used[x] = 1;
  }
  dfs(0);
  
  return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    map<char, ll> m;
    string w;
    cin >> w;
    iter(c, w) m[c]++;
    iter(i, m) {
        if(i.second % 2) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define display(v) for (auto x : v) cout << x << ", "
#define print(x) cout << (#x) << " = [ ";display(x); cout << "]\n"
#define endl '\n'
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
 
// DEBUG TEMPLATE by livw
void __print(int x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef INCLUDEWHENOFFLINE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif



int main()
{
    fastio;
    
    int n, k;
    cin >> n >> k;
    int arr[n];
    for (auto &x : arr) cin >> x;
    int dp[n];
    const int INF = 1e9;
    fill(dp, dp + n, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j <= i + k and j < n; j++)
        {
            dp[j] = min(dp[j], dp[i] + abs(arr[j] - arr[i]));
        }
    }
    cout << dp[n - 1];
    return 0;
}



Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;

int v_count;

int print_edge(int s){
    printf("%d %d\n", s, v_count);
    v_count ++;
}

int main(){ 
    string S;
    cin >> S;
    int N = S.size();
    int cur_no = 1;
    if(S[N - 1] == '1' || S[0] == '0' || S[N - 2] == '0'){
        cout << -1 << endl;
        return 0;
    }
    for(int i = 0; i < N / 2; i++){
        if(S[i] != S[N - 2 - i]){
            cout << - 1 << endl;
            return 0;
        }
    }
    int biggest = 0;
    for(int i = N / 2 - 1; i >= 0; i--){
        if(S[i] == '1'){
            biggest = i + 1;
            break;
        }
    }
    cout << 1 << " " << 2 << endl;;
    v_count = 3;
    for(int i = 0; i < N - biggest - 1; i++){
        print_edge(2);
    }

    int cur_v = 1;
    int last_component_size = biggest;
    for(int i = biggest - 2; i >= 0; i--){
        if(S[i] == '1'){
            for(int j = 0; j < last_component_size - (i + 1) - 1; j++){
                print_edge(cur_v);
            }
            int tmp = cur_v;
            cur_v = v_count;
            last_component_size = i + 1;
            print_edge(tmp);
        }
    }
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
using namespace std;
int main() {
    fast();
    // ll t;
    // cin>>t;
    // while(t--)			
    // {
        
    // }
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    ll cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                if(a[k]<a[i]+a[j]&&(a[i]!=a[j]&&a[j]!=a[k]&&a[k]!=a[i]))
                cnt++;
            }
        }
    }
    cout<<cnt;
}

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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<ll> pattern;
ll dp[MAX_N];

ll dfs(ll n) {
    if(n <= 0) { return 0; }

    ll& res = dp[n];
    if(~res) { return res; }
    res = LLINF;
    REP(i, pattern.size()) {
        if(n < pattern[i]) { continue; }
        res = min(res, dfs(n - pattern[i]));
    }
    res++;
    return res;
}

signed main()
{
    cin >> N;

    pattern.push_back(1);
    for(ll i = 6; i <= 100000; i*= 6) { pattern.push_back(i); }
    for(ll i = 9; i <= 100000; i*= 9) { pattern.push_back(i); }

    sort(pattern.begin(), pattern.end(), greater<ll>());

    MINUS(dp);
    printf("%lld\n", dfs(N));

    return 0;
}


Measured memory_bytes: 1024
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    judge = [input() for _ in range(N)]

    AC = judge.count("AC")
    WA = judge.count("WA")
    TLE = judge.count("TLE")
    RE = judge.count("RE")
    print("AC x " + str(AC))
    print("WA x " + str(WA))
    print("TLE x " + str(TLE))
    print("RE x " + str(RE))


if __name__ == "__main__":
    main()


Measured memory_bytes: 16340
#include <iostream>
#include <vector>
using namespace std;
#define WHITE 0
#define GRAY  1
#define BLACK 2

int am[8][8];
int color[8];
int n, m;

int dfs(int u) {
  color[u] = GRAY;
  bool allVisited = true;
  for (int i=0; i<n; i++) {
    if (color[i] == WHITE) {
      allVisited = false;
    }
  }
  if (allVisited) {
    return 1;
  }


  int ans = 0;
  for (int i=0; i<n; i++) {
    if (am[u][i] != 0 && color[i] == WHITE) {
      ans += dfs(i);
      color[i] = WHITE;
    }
  }
  color[u] = BLACK;
  return ans;
}
  
  
  
int main() {
  cin >> n >> m;

  for (int i=0; i<8; i++) {
    for (int j=0; j<8; j++) {
      am[i][j] = 0;
    }
    color[i] = WHITE;
  }
  int a, b;
  for (int i=0; i<m; i++) {
    cin >> a >> b;
    am[a-1][b-1] = 1;
    am[b-1][a-1] = 1;    
  }
  int ans = dfs(0);
  cout << ans << endl;
}
    


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

namespace _168A
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = Console.ReadLine()?.ToCharArray();
            var len = N.Length - 1;
            if (N[len] == '2' || N[len] == '4' || N[len] == '5' || N[len] == '7' || N[len] == '9')
            {
                Console.WriteLine("hon");
            }

            if (N[len] == '0' || N[len] == '1' || N[len] == '6' || N[len] == '8')
            {
                Console.WriteLine("pon");
            }

            if (N[len] == '3')
            {
                Console.WriteLine("bon");
            }

        }
    }
}


Measured memory_bytes: 25820
#include<bits/stdc++.h>
#define bug puts("QWQ")
#define huan putchar('\n')
#define kong putchar(' ')
using namespace std;

inline void read(int  &x)
{
	int pd=1;
	register char ch=getchar();x=0;
	while(ch<'0'||ch>'9'){if(ch=='-')pd=-pd;ch=getchar();}
 	while(ch>='0'&&ch<='9'){x=(x*10+ch-'0');ch=getchar();}
 	x*=pd;
}

void write(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}

inline void wrl(int x)
{
	write(x);
	puts("");
}

inline void wrs(int x)
{
	write(x);
	putchar(' ');
}

/*
¿¼ÂÇÃ»ÓÐÄÃ×ßÒ»¶ÑµÄ²Ù×÷£¬ÄÇÃ´ÏÈÊÖ±Ø°ÜµÄÌõ¼þÊÇMX(A[I])ÊÇÆæÊý

¿¼ÂÇÃ»ÓÐ¼õÒ»µÄ²Ù×÷£¬ÄÇÃ´ÏÈÊÖ±Ø°ÜµÄÌõ¼þÊÇNÊÇÆæÊý 
*/

const int N=1e5+233;
int n,a[N];
inline bool check()
{
    for(register int i=1;i<=n;++i)
    {
        if(a[i])return 1;
    }
    return 0;
}
bool dfs(int s)
{
    if(!check())
    {
        return 1;
    }
    
    bool flag=1;
    bool vis[20];
    memset(vis,0,sizeof(vis));
    for(register int i=1;i<=n;++i)
    {
        if(a[i])
        --a[i],vis[i]=1;
    }
    flag&=dfs(s+1);
    for(register int i=1;i<=n;++i)
    {
        if(vis[i])
        ++a[i],vis[i]=0;
    }
    int now;
    for(register int i=1;i<=n;++i)
    {
        if(a[i])
        {
            now=a[i];
            a[i]=0;
            flag&=dfs(s+1);
            a[i]=now;
            break;
        }
    }
    return flag^1;
}


int main()
{
//    freopen("t1.in","r",stdin);
//    freopen("t1.out","w",stdout);
	int T;
//	read(T);
//	while(T--)
	{
		memset(a,0,sizeof(a));
		read(n);
		for(register int i=1;i<=n;++i)
		{
			read(a[i]);
		}
		sort(a+1,a+n+1,greater<int> ());
		for(register int i=1;i<=n;++i)
		{
			if(i>=a[i+1])
			{
				int ans=0;
				for(register int j=i+1;a[j]==i;++j)ans^=1;
				if(ans||((a[i]-i)&1))puts("First");
				else puts("Second");
				break;
			}
		}
	}
    return 0;
}

Measured memory_bytes: 768
// C - Cat Snuke and a Voyage
#include <bits/stdc++.h>
using namespace std;

int main(){
	int N,M; cin>>N>>M;
	vector<bool> P(N);
	while(M--){
		int a,b; cin>>a>>b;
		if(a==1){
			if(P[b-1]) break;
			P[b-1] = true;
		}
		if(b==N){
			if(P[a-1]) break;
			P[a-1] = true;
		}
	}
	puts(M<0?"IMPOSSIBLE":"POSSIBLE");
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<string.h>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<climits>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,pos;
    cin>>n>>pos;
    string ans="";
    for(int i=0;i<n;i++){
        char a;
        cin>>a;
        if(i==pos-1){
            ans+=tolower(a);
        }else{
            ans+=a;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#include <cstdio>
#include <tuple>
#include <string>
#include <vector> 
#include <set>
#include <string.h>
#include <map>
using Graph = vector<vector<int>>;
using Graph_Wei = vector<vector<pair<int,int>>>;
using ll = long long;

//長さを記録する
Graph_Wei graph_wei;
// 二部グラフ判定
vector<int> color;
void dfs(const Graph_Wei &G, int v, int w,int cur = 0) {

    for (auto next_v : G[v]) {
        //訪問ずみならスルー
        if(color[next_v.first] != -1) continue;
        //first:頂点番号　second:長さ
        w += next_v.second;

        //距離が偶数の時、同色
        if(w % 2 == 0){
            color[next_v.first] = cur;
        }else{
            color[next_v.first] = 1 - cur;
        }
        
        dfs(G, next_v.first, w);
          
    }  
}


vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};
//昇順に並ぶ配列から目的のあたいのインデックスを見つける
//二分探索
int binarySearch(int key){
    int index;
    int left = 0;
    int right = (int)a.size() -1;
    
    while(right >= left){  
        int mid = left + (right - left)/2;     
        if(a[mid] == key) return mid;
        else if(a[mid] > key) right = mid - 1;
        else if(a[mid] < key) left = mid + 1;

    }
    return -1;
}

//indexとkeyを比較して真偽を返す
bool isOk(int index,int key){
    if(a[index] >= key) return true;
    else return false;
}

int binary_search(int key){
    int left = -1;
    int right = a.size() -1;
    while(right - left > 1){
        int mid = left + (right - left)/2;
        if (isOk(mid,key)) right = mid;
        else left = mid; 

    }



    return right;

}
int main() {

    int n;
    cin >> n;
    vector<ll> L(n);//コンストラクタ呼び出し
    for(int i=0;i < n;i++) cin >> L[i];
    sort(L.begin(),L.end());
    //a,bを固定してc < a + b (*)となる三角形を求める
    //(*)の条件を満たさないcの範囲は二分探索lower_bound呼びだしでイテレータを求める
    //a <= b <= c としても一般性を失わない
    //上記を満たすcの値の範囲が作成される三角形の個数
    int ans =0;
    for(int i = 0;i <n;i++){
        for(int j = i+1;j < n;j++){
            auto tt = lower_bound(L.begin(),L.end(),L[i] + L[j]);
            int index = tt - L.begin();
            int num = index -1 - (j + 1) + 1;
            ans += max(0,num);

        }
    }


    cout << ans << endl;


    return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct binaryHeap{
  void *h;
  size_t heapSize;
  size_t maxSize;
  size_t size;
  int (*cmp)(const void *,const void *);
} heap;

heap* newHeap(const size_t size,int (*cmpF)(const void *,const void *)){
  const size_t maxSize=1;
  heap *res=(heap *)malloc(sizeof(heap));
  res->h=malloc(size*(maxSize+1));
  res->heapSize=0;
  res->maxSize=maxSize;
  res->size=size;
  res->cmp=cmpF;
  return res;
}

int isEmpty(const heap *h){
  return h->heapSize==0;
}

void freeHeap(heap *h){
  free(h->h);
  free(h);
  return;
}

void initHeap(heap *h){
  h->heapSize=0;
  return;
}

static inline void heapFunc_swap(void * restrict a,void * restrict b,void * restrict tmp,size_t size){
  memcpy(tmp,a,size);
  memcpy(a,b,size);
  memcpy(b,tmp,size);
  return;
}

void push(heap *q,const void *p){
  if(q->heapSize==q->maxSize){
    q->maxSize*=2;
    q->h=realloc(q->h,q->size*(q->maxSize+1));
  }
  q->heapSize+=1;
  char *h=(char *)(q->h);
  int k=q->heapSize;
  const size_t size=q->size;
  int (*cmp)(const void *,const void *)=q->cmp;
  memcpy(h+k*size,p,size);
  while(k>1){
    size_t parent=k/2;
    if(cmp(h+parent*size,h+k*size)<=0) return;
    heapFunc_swap(h+parent*size,h+k*size,h,size);
    k=parent;
  }
  return;
}

void pop(heap *q,void *res){
  char *h=(char *)(q->h);
  const size_t size=q->size;
  if(res!=NULL) memcpy(res,h+size,size);
  memcpy(h+size,h+size*q->heapSize,size);
  q->heapSize-=1;
  int (*cmp)(const void *,const void *)=q->cmp;
  const size_t n=q->heapSize;
  size_t k=1;
  while(2*k+1<=n){
    size_t next=cmp(h+2*k*size,h+(2*k+1)*size)<=0?2*k:2*k+1;
    if(cmp(h+k*size,h+next*size)<=0) return;
    heapFunc_swap(h+k*size,h+next*size,h,size);
    k=next;
  }
  if(2*k<=n && cmp(h+k*size,h+2*k*size)>0) heapFunc_swap(h+k*size,h+2*k*size,h,size);
  return;
}

void top(const heap *q,void *res){
  memcpy(res,(char *)q->h+q->size,q->size);
  return;
}

typedef long long int int64;

int cmpMin(const void *a,const void *b){
  return *(int *)a-*(int *)b;
}

int cmpMax(const void *a,const void *b){
  return -cmpMin(a,b);
}

void run(void){
  int n;
  scanf("%d",&n);
  int *a=(int *)calloc(3*n,sizeof(int));
  int i;
  for(i=0;i<3*n;i++) scanf("%d",a+i);
  heap *h=newHeap(sizeof(int),cmpMin);
  int64 sum=0;
  for(i=0;i<n;i++){
    sum+=a[i];
    push(h,a+i);
  }
  int64 *front=(int64 *)calloc(n+1,sizeof(int64));
  front[0]=sum;
  for(i=0;i<n;i++){
    sum+=a[n+i];
    push(h,a+n+i);
    int v;
    pop(h,&v);
    sum-=v;
    front[i+1]=sum;
  }
  sum=0;
  freeHeap(h);
  h=newHeap(sizeof(int),cmpMax);
  for(i=n-1;i>=0;i--){
    sum+=a[2*n+i];
    push(h,a+2*n+i);
  }
  int64 *back=(int64 *)calloc(n+1,sizeof(int64));
  back[0]=sum;
  for(i=n-1;i>=0;i--){
    sum+=a[n+i];
    push(h,a+n+i);
    int v;
    pop(h,&v);
    sum-=v;
    back[n-i]=sum;
  }
  freeHeap(h);
  int64 max=-1000000000LL*n;
  for(i=0;i<=n;i++){
    int64 t=front[i]-back[n-i];
    if(t>max) max=t;
  }
  printf("%lld\n",max);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 3324
//author : Brijesh1in
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define endl '\n'
#define boost ios::sync_with_stdio(false);
typedef long long li;

const int N = 1010;
const int mod = 1e9 + 7;
li dp[N][N];
string a[1010];
int main(){

	int h,w;
	cin>>h>>w;
	for(int i = 1 ; i <= h ; ++i){
		cin>>a[i];
	}

	dp[1][0] = 1;

	for(int i = 1 ; i<= h ; ++i)
		for(int j = 0 ; j < w ; ++j){
			if(a[i][j]=='#'){
				//cout<<0<<" \n"[j==w-1];
				continue;
			}

			if(j==0)
				dp[i][j] = (max(dp[i][j] , dp[i-1][j]))%mod;
			else dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;

			//cout<<dp[i][j]<<" \n"[j==w-1];
				
		}

	cout<<dp[h][w-1]<<endl;

}

Measured memory_bytes: 9216
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <iomanip>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int a,b,c,d,e,f;
    int i1,i2,i3,i4,tot,sug;
    cin>>a>>b>>c>>d>>e>>f;
    a*=100;
    b*=100;
    tot=a;
    sug=0;
    for(i1=0;i1<=100;i1++)for(i2=0;i2<=100;i2++)for(i3=0;i3<=100;i3++)for(i4=0;i4<=100;i4++){
        int totwat=i1*a+i2*b;
        int totsug=i3*c+i4*d;
        if(totwat+totsug<=f){
            if(totsug*100<=totwat*e){
                if(sug*(totsug+totwat)<=tot*totsug){
                    sug=totsug;
                    tot=totwat+totsug;
                }
            }
        }
    }
    cout<<tot<<" "<<sug<<endl;
    return 0;
 
 
}

Measured memory_bytes: 256
/*
Problem : Atcoder Beginner Contest 122 D
Algorithm :
Status :
*/
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAXN = 105;
const char ch[] = {'A','C','G','T'};

int n,ans;
int f[MAXN][4][4][4];

bool check(int a,int b,int c){
	return !(ch[a] == 'A' && ch[b] == 'G' && ch[c] == 'C');
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 4;j++){
			for(int k = 0;k < 4;k++){
				if(check(i,j,k) && check(j,i,k) && check(i,k,j))
				    f[3][i][j][k] = 1;
			}
		}
	}
	for(int l = 4;l <= n;l++){
		for(int i = 0;i < 4;i++){
			for(int j = 0;j < 4;j++){
				for(int k = 0;k < 4;k++){
					for(int x = 0;x < 4;x++){
						if(check(i,j,k) && check(x,i,k) && check(x,j,k) && check(j,i,k) && check(i,k,j))
						    f[l][i][j][k] = (f[l][i][j][k] + f[l - 1][x][i][j]) % MOD;
					}
				}
			}
		}
	}
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 4;j++){
			for(int k = 0;k < 4;k++)
			    ans = (ans + f[n][i][j][k]) % MOD;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int INT_INF = 500000000;
const long long LONG_LONG_INF = (long long)pow(10, 18);
const int MOD = pow(10, 9) + 7;
/* contest template */
long long N, C;
long long x[100005];
long long v[100005];
long long rb[100005];
long long lb[100005];
long long lc, lmax, lx, rc, rmax, rx, ans, rc1, lc1;
long long rbc, lbc;

int main() {
  rc = 0;
  lc = 0;
  cin >> N >> C;
  for (int i = 1; i <= N; i++) {
    cin >> x[i] >> v[i];
  }
  x[N + 1] = C;
  lb[N + 1] = 0;
  for (int i = 1; i <= N; i++) {
    rc = rc + v[i] - (x[i] - x[i - 1]);
    rbc = rc - x[i];
    rb[i] = max(rb[i - 1], rbc);
    if (rmax < rc) {
      rmax = rc;
      rx = x[i];
    }
  }
  for (int i = N; i >= 1; i--) {
    lc = lc + v[i] - (x[i + 1] - x[i]);
    lbc = lc - (C - x[i]);
    lb[i] = max(lb[i + 1], lbc);
    if (lmax < lc) {
      lmax = lc;
      lx = x[i];
    }
  }
  ans = max(rmax, lmax);
  rc = 0;
  lc = 0;
  for (int i = 1; i <= N; i++) {
    rc = rc + v[i] - (x[i] - x[i - 1]);
    rc1 = rc + lb[i + 1];
    if (ans < rc1) {
      ans = rc1;
    }
  }
  for (int i = N; i >= 1; i--) {
    lc = lc + v[i] - (x[i + 1] - x[i]);
    lc1 = lc + rb[i - 1];
    if (ans < lc1) {
      ans = lc1;
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3328