akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define VSORT(v) sort(v.begin(), v.end());
#define pb(a) push_back(a)


typedef long long ll;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;

#define ARRAY_MAX 100005

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


int n, ma, mb;

struct goods {

	int a;
	int b;
	int c;

};


void build(int bg, int en, vector<goods>& t, map<pii,int>& ans) {

	int m = en - bg;
	for (int i = 0; i < (1 << m); i++) {
		int aa = 0, bb = 0, cc = 0;

		for (int j = 0; j < m; j++) {
			if ((i >> j) & 1) {
				aa += t[bg + j].a;
				bb += t[bg + j].b;
				cc += t[bg + j].c;
			}
		}
		if (ans.count({ aa,bb }) == 0 || ans[{aa,bb}] > cc)
		{
			ans[{aa, bb}] = cc;
		}
	}
}

int main() {

	
	cin >> n >> ma >> mb;


	vector<goods> vec(n);
	for (int i = 0; i < n; i++)
	{
		cin >> vec[i].a >> vec[i].b >> vec[i].c;
	}

	map<pii,int> ans1, ans2;

	build(0, n / 2, vec, ans1);
	build(n / 2, n, vec, ans2);

	int mini = INF;

	for (auto itr: ans1)
	{
		for (auto itr2 : ans2)
		{
			int aa = itr.first.first + itr2.first.first;
			int bb = itr.first.second + itr2.first.second;
			
			if (aa * mb == bb * ma && itr.second + itr2.second != 0)
			{
				mini = min(mini, itr.second + itr2.second);
			}
		}
	}
	if (mini == INF)
	{
		cout << "-1" << endl;
	}
	else
	{
		cout << mini << endl;
	}

	return 0;
}

Measured memory_bytes: 896
//@@@@@@@@@@ JAI BAJRANG BALI @@@@@@@@@

// COMPILE BY:) NAMAN


#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define maxn 10000001
#define endl "\n"
#define inf INT_MAX
#define vec vector <ll>
#define mps map <ll,ll>
#define ppl vector<pair<ll,ll>> 
#define fi first
#define si second
#define pr pair<ll,ll> 
#define mvec map<ll,vector <ll>>
#define all(v) v.begin(),v.end()
#define infi LLONG_MAX
#define pi 3.141592653
#define ninf INT_MIN
#define ninfi LLONG_MIN
#define lbn lower_bound
#define ubn upper_bound
#define memset(a,b) memset(a,(b),sizeof(a))
  
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll k,a,b;
    cin>>k>>a>>b;
    ll flg=0;
    for(ll i=a;i<=b;i++)
    {
    	if(i%k==0)
    	{
    		flg=1;
    		break;
    	}
    }
    if(flg==0)
    	cout<<"NG"<<endl;
    else
    	cout<<"OK"<<endl;

return 0;
}


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

int main() {
    ll k;
    std::cin >> k;
    ll now = 7;
    for (int i = 0; i < 10000000; i++) {
        if(now%k==0){
            std::cout << i+1 << std::endl;
            return 0;
        }
        now = now*10+7;
        now %= k;
    }
    std::cout << -1 << std::endl;
    
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(i=0;i<n;i++)
#define test(a) cout << "*" << a << endl;
int main (){
  int i;
  int k;
  string s;
  cin >> k;
  cin >> s;
  
  if(s.size()<=k){
    cout << s; 
  }
  else{
    rep0(i,k){
      cout << s[i];  
    }
    cout << "..." << endl; 
  }
   
}

Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority queue
#include<deque>//double_ended queue
using namespace std;
int main()
{ 
    int h,w;
    cin>>h>>w;
    int n[w+1];//繰り下がり
    for(int i=0;i<w+1;i++){//初期化
        n[i]=0;
    }
    vector<int> y;
    vector<int> x;
    vector<int> y_;
    vector<int> x_; 

    int a=0;//計算中のコインの枚数
    for(int i=1;i<=h-1;i++){
        for(int j=1;j<=w;j++){
            cin>>a;
            a=a+n[j];
            if(a%2==1){
                y.push_back(i);
                x.push_back(j);
                y_.push_back(i+1);
                x_.push_back(j);
                n[j]=1;
            }
            else{n[j]=0;}
        }
    }
    int b=0;
    for(int j=1;j<w;j++){
        cin>>a;
        a=a+n[j]+b;
        if(a%2==1){
            y.push_back(h);
            x.push_back(j);
            y_.push_back(h);
            x_.push_back(j+1);
            b=1;
        }
        else{b=0;}
    }
    b=y.size();
    cout<<b<<endl;
    for(int i=0;i<b;i++){
        cout<<y.back()<<' '<<x.back()<<' '<<y_.back()<<' '<<x_.back()<<endl;
        y.pop_back();
        x.pop_back();
        y_.pop_back();
        x_.pop_back();
    }
    return 0;
}

Measured memory_bytes: 4196
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <math.h>
using namespace std;
int a,b;
int main(){
    cin >> a >> b;
    if((a*b)%2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
int N, P, A, B, C, D, E, F, S, M; pair<long double, string> G[50];
int main() {
	while (true) {
		scanf("%d", &N);
		if (N == 0) break;
		for (int i = 0; i < N; i++) {
			cin >> G[i].second; cin >> P >> A >> B >> C >> D >> E >> F >> S >> M;
			G[i].first = -1.0L * ((F * S * M) - P) / (A + B + C + M * (D + E));
		}
		sort(G, G + N);
		for (int i = 0; i < N; i++) printf("%s\n", G[i].second.c_str());
		printf("#\n");
	}
	return 0;
}

Measured memory_bytes: 3220
n = int(input())
a1 = list(map(int,input().split()))
a2 = list(map(int,input().split()))

sa1 = [a1[0]]
sa2 = [a2[-1]]
for i in range(n-1):
    b = sa1[i] + a1[i+1]
    c = sa2[i] + a2[-i-2]
    sa1.append(b)
    sa2.append(c)

ans = 0
for i in range(n):
     ans = max(ans, sa1[i]+sa2[n-i-1]) 
print(ans)  

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            long N = sc.nextLong();
            long K = sc.nextLong();

            long min = N;
            min = Math.min(min, N % K);
            min = Math.min(min, (N % K) + K);
            min = Math.min(min, Math.abs((N % K) - K));
            System.out.println(min);
        }
    }
}


Measured memory_bytes: 27116
#include <iostream>

using namespace std;
char a;
int main()
{
	cin >> a;
	if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u'){
		cout << "vowel";
	}else {
		cout << "consonant";
	}
    return 0;
}


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

int main() {
 int n,m,cnt=0;
  int lmax=-1,rmin=100001;
 cin >> n >> m;
  vector<int> l(m),r(m);
  for(int i=0;i<m;i++){
  cin >> l[i] >>r[i];
    lmax=max(lmax,l[i]);
    rmin=min(rmin,r[i]);
  }
 if(lmax>rmin){
 cout << '0' << endl;
 }

  else if(rmin>=lmax){
  cout << rmin-lmax+1 << endl;
  }

}


  

Measured memory_bytes: 1024
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def largestRectangInHistgram(heights):
    stack = [-1]
    maxArea = 0

    for i in range(len(heights)):
        # we are saving indexes in stack that is why we comparing last element in stack
        # with current height to check if last element in stack not bigger then
        # current element
        while stack[-1] != -1 and heights[stack[-1]] > heights[i]:
            lastElementIndex = stack.pop()
            maxArea = max(maxArea, heights[lastElementIndex] * (i - stack[-1] - 1))
        stack.append(i)

    # we went through all elements of heights array
    # let's check if we have something left in stack
    while stack[-1] != -1:
        lastElementIndex = stack.pop()
        maxArea = max(maxArea, heights[lastElementIndex] * (len(heights) - stack[-1] - 1))

    return maxArea


def main():
    n, k, l, r = ns()
    a = na()

    pair1 = a[:n // 2]
    pair2 = a[n // 2:]
    ans = 0

    res1 = [[0, 0]]
    res2 = [[0, 0]]

    for p1 in pair1:
        tmp = [[cnt + 1, r + p1] for cnt, r in res1]
        res1 += tmp

    for p2 in pair2:
        tmp = [[cnt + 1, r + p2] for cnt, r in res2]
        res2 += tmp

    res2dic = {}
    for cnt, p2 in res2:
        if cnt not in res2dic.keys():
            res2dic[cnt] = [p2]
        else:
            res2dic[cnt].append(p2)
    for key in res2dic.keys():
        res2dic[key].sort()

    for cnt, r1 in res1:
        tmpk = k - cnt
        if tmpk < 0 or tmpk not in res2dic.keys():
            continue

        lnum = l - r1
        rnum = r - r1
        lidx = bisect.bisect_left(res2dic[tmpk], lnum)
        ridx = bisect.bisect_right(res2dic[tmpk], rnum)
        ans += ridx - lidx

    print(ans)



if __name__ == '__main__':
    main()



Measured memory_bytes: 290372
#include <bits/stdc++.h>
using namespace std;
int l,r,d,s;
int main()
{ cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin>>l>>r>>d;
  for(int i=d;i<=r;i+=d)
    if(i>=l)
       s++;
  cout<<s<<'\n';
  return 0;
}


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

using namespace std;

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

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

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

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

    string S, T;
    cin >> S >> T;

    int A, B;
    cin >> A >> B;

    string U;
    cin >> U;
    if (S == U) {
        cout << A-1 << " " << B << endl;
    } else {
        cout << A << " " << B-1 << endl;
    }
    return 0;
}

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

int main(void){
  int N, M;
  cin >> N >> M;
  vector<pair<long long, long long>> AB(N);
  for(int i = 0; i < N; i++){
    long long A, B;
    cin >> A >> B;
    AB[i] = make_pair(A, B);
  }
  sort(AB.begin(), AB.end());
  long long sum = 0;
  int step = 0;
  long long B = AB[step].second;
  while(M > B){
   sum += AB[step].first * AB[step].second;
    M -= B;
    B = AB[step + 1].second;
    step++;
  }
  sum += AB[step].first * M; 
  cout << sum;
  
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string.h>
#include <string>
#include <vector>
#include <limits.h>
#define maxn 10000000
#define pi acos(-1)
using namespace std;
double aabs(double x)
{
	if(x<0)return -x;
	return x;
}
int gcd(int a,int b)
{
	if(a%b==0)return b;
	return gcd(b,a%b);
}
int main()
{
	int n,ans=0;
	int a[107];
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)
	{
		int minj=i,t;
		for(int j=i;j<n;j++)
			if(a[j]<a[minj])
				minj=j;	
		if(minj!=i){t=a[i];
		a[i]=a[minj];
		a[minj]=t;
		ans++;}
	}
	for(int i=0;i<n;i++)
	{
		if(i!=n-1)cout<<a[i]<<" ";
		else cout<<a[i]<<endl;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3116
n=int(input())
A=[0]+list(map(int,input().split()))+[0]
B=[abs(A[i+1]-A[i]) for i in range(n+1)]
cost=sum(B)
for i in range(1,n+1):
    print(cost-abs(A[i-1]-A[i])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))

    

Measured memory_bytes: 13920
#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
int a[107];
int main(){
	int n=read(),s=0;
	for(int i=1;i<=n;i++)a[i]=read(),s+=a[i];
	int m=read();
	while(m--){
		int p=read();
		printf("%d\n",s+read()-a[p]);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>

using namespace std;

int main(){
	long long a,b,c,x,y;
	cin >> a >> b >> c >> x >> y;

	long long pt1 = x*a+b*y;
	long long pt2 = c * max(x,y) * 2;
	long long pt3 = 0;
	if(x < y){
		pt3 = c * x * 2;
		pt3 += b * (y-x);
	}else{
		pt3 = c * y * 2;
		pt3 += a * (x-y);
	}

	cout << min(pt1,min(pt2,pt3)) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<double,int>;
const ll M = 998244353;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}

int main() {
  int n; cin>>n;
  string a,b,c; cin>>a>>b>>c;
  int an=0;
  for(int i=0;i<n;i++) {
    if (a[i]==b[i]&&a[i]==c[i]) continue;
    if (a[i]==b[i]||b[i]==c[i]||c[i]==a[i]) an++;
    else an+=2;
  }
  cout<<an<<endl;
}

Measured memory_bytes: 256
# 入力
N,X=map(int,input().split())

l=[]
for i in range(N):
  l.append(int(input()))

# 金額
a=0

# 個数
c=0

# 全種類一つずつ
a=sum(l)
c=len(l)

# 残金で一番安いものをできるだけ買う
c+=(X-a)//min(l)

# 出力
print(c)

Measured memory_bytes: 3060
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N = 0
K = 0
A, B = [], []
C, D = [], []

def set_inputs():
    global N, K, A, B, C, D
    N = get_int()
    K = get_int()
    A, B = get_data(K, [int, int])
    C = [min(a, N - a + 1) for a in A]
    D = [min(b, N - b + 1) for b in B]
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    for c, d in zip(C, D):
        ans = min(c, d) % 3
        if ans == 0:
            ans = 3
        print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()



Measured memory_bytes: 7216
N, M = map(int, input().split())

food = [0] * (M+1)

for _ in range(N):
    L = list(map(int, input().split()))
    L = L[1:]
    for l in L:
        food[l] += 1

ans = 0
for f in food:
    if f == N:
        ans += 1
print(ans)



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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 200010;
int N;
int p[MC];
vector<int> V[MC];
vector<int> d[MC];
int a[MC];
bool b[MC];
bool c[MC];
int r;

int dfs(int q){
	for(auto u : V[q]){
		if(c[u]) continue;
		d[q].PB(dfs(u));
	}
	sort(d[q].begin(),d[q].end());
	a[q] = -1;
	for(auto u : d[q]){
		if(u > a[q]+1) break;
		a[q] = u;
	}
	return ++a[q];
}

int main(){
	scanf("%d" , &N);
	repp(i,1,N+1){
		scanf("%d" , p + i);
		V[p[i]].PB(i);
	}
	r = 1;
	while(!b[r]){
		b[r] = 1;
		r = p[r];
	}
	while(!c[r]){
		c[r] = 1;
		r = p[r];
	}
	repp(i,1,N+1){
		if(c[i]) dfs(i);
	}
	bool t = 0;
	int y = 0;
	while(c[r]){
		c[r] = 0;
		if(a[r] != a[p[r]]) t = 1;
		r = p[r];
		++y;
	}
	printf("%s\n" , t || y%2==0 ? "POSSIBLE" : "IMPOSSIBLE");
	return 0;
}


Measured memory_bytes: 17664
using System;
using System.Linq;

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    public void Do()
    {
        cin = new Scanner();

        var s = cin.nextInt();
        var isCalced = new bool[1000000];
        var a = new int[1000000];

        for (int i = 0; i < 1000000; i++)
        {
            isCalced[i] = false;
        }

        a[0] = s;
        isCalced[a[0]] = true;
        for (int i = 1; i < 1000000; i++)
        {
            a[i] = f(a[i - 1]);
            if (isCalced[a[i]] == false)
            {
                isCalced[a[i]] = true;
            }
            else
            {
                Console.WriteLine(i + 1);
                return;
            }
        }
    }

    int f(int n)
    {
        if (n % 2 == 0)
        {
            return n / 2;
        }
        else
        {
            return 3 * n + 1;
        }
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }


    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}


Measured memory_bytes: 11872
#include <iostream>
#include <cmath>
#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 (a*x, a*y); }
  double abs(){ 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 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;
}
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2){
  Vector a=p1-p0;
  Vector b=p2-p0;
  if(cross(a, b) > EPS) return COUNTER_CLOCKWISE;
  if(cross(a, b) < -EPS) return CLOCKWISE;
  if(dot(a, b) < -EPS) return ONLINE_BACK;
  if(a.norm() < b.norm()) return ONLINE_FRONT;
  return ON_SEGMENT;
}
bool isIntersect(Point p1, Point p2, Point p3, Point p4){
  return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
	   ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}
bool isIntersect(Segment s1, Segment s2){
  return isIntersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

main(){
  double xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2;
  while(cin >> xa1 >> ya1 >> xa2 >> ya2 >> xb1 >> yb1 >> xb2 >> yb2){
    Segment a[4], b[4];
    Point pa[4], pb[4];
    pa[0].x=xa1;
    pa[0].y=ya2;
    pa[1].x=xa2;
    pa[1].y=ya2;
    pa[2].x=xa2;
    pa[2].y=ya1;
    pa[3].x=xa1;
    pa[3].y=ya1;

    pb[0].x=xb1;
    pb[0].y=yb2;
    pb[1].x=xb2;
    pb[1].y=yb2;
    pb[2].x=xb2;
    pb[2].y=yb1;
    pb[3].x=xb1;
    pb[3].y=yb1;

    a[0].p1=pa[0];
    a[0].p2=pa[1];

    a[1].p1=pa[1];
    a[1].p2=pa[2];

    a[2].p1=pa[2];
    a[2].p2=pa[3];

    a[3].p1=pa[3];
    a[3].p2=pa[0];

    b[0].p1=pb[0];
    b[0].p2=pb[1];

    b[1].p1=pb[1];
    b[1].p2=pb[2];

    b[2].p1=pb[2];
    b[2].p2=pb[3];

    b[3].p1=pb[3];
    b[3].p2=pb[0];

    bool ans=false;
    for(int i=0;i<4;i++){
      for(int j=0;j<4;j++){
	if(isIntersect(a[i], b[j])){
	  ans=true;
	}
      }
    }
    if(ans){
      cout << "YES" << endl;
      continue;
    }
    ans=false;
    for(int i=0;i<4;i++){
      if(pb[i].x>=xa1 && pb[i].x<=xa2){
	if(pb[i].y>=ya1 && pb[i].y<=ya2){
	  ans=true;
	  break;
	}
      }
    }
    if(ans){
      cout << "YES" << endl;
      continue;
    }
    ans=false;
    for(int i=0;i<4;i++){
      if(pa[i].x>=xb1 && pa[i].x<=xb2){
	if(pa[i].y>=yb1 && pa[i].y<=yb2){
	  ans=true;
	  break;
	}
      }
    }
    if(ans){
      cout << "YES" << endl;
      continue;
    }
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}

//INSERT ABOVE HERE
Int dp[2][5][101]={};
signed main(){
  string s;
  cin>>s;
  Int k;
  cin>>k;
  Int n=s.size();
  dp[0][0][0]=1;
  for(Int i=0;i<n;i++){
    for(Int f=0;f<2;f++){
      for(Int c=0;c<4;c++){
        for(Int k=0;k<=(f?9:s[i]-'0');k++){
          Int nf=f||(k<s[i]-'0');
          Int nc=c+(k!=0);
          dp[nf][nc][i+1]+=dp[f][c][i];
        }
      }
    }
  }
  cout<<dp[0][k][n]+dp[1][k][n]<<endl;
  return 0;
}


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

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}


bool checker(string s) {
    int len = s.length();
    for(int i=0;i<len/2;i++){
        if(s[i] != s[len-i-1]) return false;
    }
    return true;

}

int main(){
    string s;
    cin >> s;
    string bef,af;
    int len = s.length();
    for(int i=0;i<len/2;i++) {
        bef = bef + s[i];
    }

    for(int i=(len+2)/2;i<len;i++) {
        af = af + s[i];
    }

    if(checker(s) && checker(bef) && checker(af)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}

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

using namespace std;
typedef long long int ll;

int main()
{
   int n,m;
   cin >> n >> m;
   vector<vector<int>>v(m);
   for(int i = 0; i < m; i++)
   {
       int k;
       cin >> k;
       v[i].resize(k);
       for(int j = 0; j < k; j++)
       {
           cin >> v[i][j];
           v[i][j]--;
       }
       sort(v[i].begin(),v[i].end());
   }
   vector<int>p(m);
   for(int i = 0; i < m; i++) cin >> p[i];
   int answer = 0;
   for(int bit=0;bit<(1<<n);bit++)
   {
       vector<int>sum(m,0);
       for(int i=0;i<n;i++)
       {
           if(bit&(1<<i))
           {
               for(int j = 0; j < m; j++)
               {
                   if(binary_search(v[j].begin(),v[j].end(),i)) sum[j]++;
               }
           }
       }
       bool f = true;
       for(int i = 0; i < m; i++) if(sum[i]%2 != p[i]) f = false;
       if(f) answer++;
   }
   cout << answer << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define why(n,x) int n;while(cin >>n,n!=x)
#define iFOR(i,x,n)for(int i=x;i<n;i++)
#define unless(flg) if ( !(flg) )
#define read cin<<
#define echo cout<<
#define fin <<'\n'
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
#define SWAP(a,b) ((a != b) && (a += b,b = a - b,a -= b))
#define cinf(n,x) for(int UNCH=0;UNCH<(n);UNCH++) cin >> x[UNCH];
#define fcin(n,x) for(int UNCH=1;UNCH<=(n);UNCH++) cin>> x[UNCH];
#define memmin(x) memset((x),-1,sizeof((x)))
#define memzer(x) memset((x), 0,sizeof((x)))
#define meminf(x) memset((x),0x3f,sizeof((x)))
#define int long long
typedef long long ll;
typedef pair < int , int >  pii;
typedef vector < int > vit;
typedef map < string , int > mstit;
typedef vector < pii > vpi ;
typedef greater < pii > gpi;
typedef priority_queue < pii , vpi , gpi > dijk ;
static const signed int INF = 0x3f3f3f3f;
static const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static const signed int SMOD = 1000000007;
static const signed int NMOD = 1000000009;
static const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static const signed int dy[]={0,-1,0,1,-1,1,-1,1};

bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>T abs(T &x){return x<0 ? -x : x;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}



signed main(){
    int n;
    cin >> n;
    if(n<1000) cout <<"ABC\n";
    else cout <<"ABD\n";
  
  return 0;
}



struct xyz{ xyz(){ cin.tie(0), ios::sync_with_stdio(false); cout <<fixed<<setprecision(12);};}xyzzy;



Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
 int i,j,a[3],b;
	cin>>a[0]>>a[1]>>a[2];
		for(i=0;i<3;i++){
			for(j=i+1;j<3;j++){
				if(a[i]>a[j]){					
					b=a[i];
					a[i]=a[j];				
					a[j]=b;
				}
			}
		}
	cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
return 0;
}

Measured memory_bytes: 1164
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let q: usize = read();
    let mut ab: Vec<(usize, usize)> = (0..n - 1).map(|_| (read(), read())).collect();
    let px: Vec<(usize, i32)> = (0..q).map(|_| (read(), read())).collect();

    ab.sort();
    let mut sum = vec![0; n];
    for &(p, x) in px.iter() {
        sum[p - 1] += x;
    }

    for &(a, b) in ab.iter() {
        sum[b - 1] += sum[a - 1];
    }

    for i in 0..sum.len() - 1 {
        print!("{} ", sum[i]);
    }
    println!("{}", sum[sum.len() - 1]);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 16636
#include<stdio.h>
#include <stdlib.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n;
	scanf("%d",&n);
	char *si = (char *)malloc(sizeof(char)*n);
	scanf("%s",si);

	int *s = (int *)malloc(sizeof(int)*n);
	FOR(i,0,n){									//o→1,x→-1
		if(si[i] == 'o') s[i] = 1;
		else s[i] = -1;
	}

	int *ans = (int *)malloc(sizeof(int)*n);
	FOR(i,0,2){
		FOR(j,0,2){

			if(i == 0)	ans[0] = 1;			//S→1,W→-1
			else		ans[0] = -1;
			if(j == 0)	ans[1] = 1;
			else		ans[1] = -1;

			FOR(k,1,n-1){
				if(ans[k] * s[k] == 1) ans[k+1] = ans[k-1];
				if(ans[k] * s[k] != 1) ans[k+1] = -ans[k-1];
			}

			int a=0,b=0;
			if(ans[0] * s[0] == 1 && ans[1] == ans[n-1]) a = 1;
			if(ans[0] * s[0] != 1 && ans[1] != ans[n-1]) a = 1;
			if(ans[n-1] * s[n-1] == 1 && ans[0] == ans[n-2]) b = 1;
			if(ans[n-1] * s[n-1] != 1 && ans[0] != ans[n-2]) b = 1;

			if(a*b != 0){
				FOR(l,0,n){
					if(ans[l] == 1) printf("S");
					else printf("W");
				}
				return 0;
			}
		}
	}
	printf("-1\n");
}


Measured memory_bytes: 1152
#include <stdio.h>

int main()
{
int a[4][13]={0};//これで全てゼロクリアされます
int i, j, k, x, n;
char m;

scanf("%d", &n);

for(k = 0; k < n; k++){
scanf(" %c%d", &m, &x);//先頭にスペースを入れておくと、スペースや改行をパスできる
if(m == 'S')
a[0][x - 1] = 1;
else if(m == 'H')
a[1][x - 1] = 1;
else if(m == 'C')
a[2][x - 1] = 1;
else if(m == 'D')
a[3][x - 1] = 1;
}


for(i = 0; i < 4; i++){
for(j = 0; j < 13; j++){
if(a[i][j] == 0){
if(i == 0)
printf("S %d\n", j + 1);
else if(i == 1)
printf("H %d\n", j + 1);
else if(i == 2)
printf("C %d\n", j + 1);
else if(i == 3)
printf("D %d\n", j + 1);
}
}
}
return 0;
}


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

int main() {
  vector<int> xs(100, 0);
  for (int i = 0; i < 2; ++i) {
    int left, right;
    cin >> left >> right;
    ++xs[left];
    --xs[right];
  }
  for (int i = 1; i < 100; ++i) {
    xs[i] += xs[i - 1];
  }
  int sum = 0;
  for (int i = 0; i < 100; ++i) {
    if (xs[i] == 2) ++sum;
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		long x = 1;
		long n = 0;
		while(true) {
			n = a * x;
			if(n % b == 0) {
				break;
			}
			x++;
		}

		System.out.println(n);

		sc.close();

	}

}


Measured memory_bytes: 23764
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    a,b=INTM()
    print(max(a+b,a-b,a*b))
if __name__ == '__main__':
    do()

Measured memory_bytes: 3060
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int main(){
  int a,b,c,x;
  cin>>a>>b>>c>>x;
  int count=0;
  for(int i=0;i<=a;i++){
    for(int j=0;j<=b;j++){
      for(int k=0;k<=c;k++){
        if(500*i+100*j+50*k==x)count++;
      }
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	int N, Y; cin >> N >> Y;

	repe(x, 0, 2000) {
		repe(y, 0, 2000) {
			if (x + y <= N) {
				if (Y == 10000 * x + 5000 * y + 1000 * (N - x - y)) {
					cout << x << " " << y << " " << N - x - y << endl;
					return 0;
				}
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io._
import scala.io.StdIn.{readInt, readLine}

object Main {
  val out:BufferedWriter =
    new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512)
  var count = 0
  class Node(var key:Int, var left:Node = null, var right:Node = null) { }

  def insert(tree:Node, key:Node) = {
    val keyNode = key
    def loop(node:Node):Node =
      if(node.key > keyNode.key) {
        if(node.left == null) node
        else loop(node.left)
      } else {
        if(node.right == null) node
        else loop(node.right)
      }

    val target = loop(tree)

    if(keyNode.key < target.key) target.left = keyNode
    else target.right = keyNode
  }

  def inOrder(root:Node):Unit = {
    var stack:List[Node] = Nil
    var curr = root
    var flg = true

    while(flg) {
      while(curr != null) {
        stack = curr::stack
        curr = curr.left
      }
      if(curr == null && stack != Nil) {
        val item = stack.head
        stack = stack.tail
        out.write(" ")
        out.write(item.key.toString)
        if(count<100) count += 1
        else {
          out.flush
          count = 0
        }
        curr = item.right
      } else {
        flg = false
      }
    }
  }

  def scan(list:List[Node]):Unit = {
    list match {
      case Nil => ()
      case hd::tl => {
        out.write(" ")
        out.write(hd.key.toString)
        if(count<100) count += 1
        else {
          out.flush
          count = 0
        }
        val hd2 = if(hd.right!=null) hd.right::tl else tl
        val hd3 =if(hd.left!=null) hd.left::hd2 else hd2
        scan(hd3)
      }
    }
  }

  def preOrder(tree:Node):Unit =
    if(tree == null) return
    else  scan(tree::Nil)

  def main(args:Array[String]) = {
    val n = readInt
    val tree = new Node(-1)

    for(i<-0 until n) {
      val s = readLine.split(" ")
      s(0) match {
        case "insert" =>
          if(tree.key == -1) tree.key = s(1).toInt
          else insert(tree, new Node(s(1).toInt))
        case _ => {
          inOrder(tree)
          out.write("\n")
          out.flush()
          preOrder(tree)
          out.write("\n")
          out.flush()
        }
      }
    }
  }
}

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

int A;
int a[6];

bool dp[6+1][100001];

int main() {
    cin >> A;
    a[0] = 100;
    a[1] = 101;
    a[2] = 102;
    a[3] = 103;
    a[4] = 104;
    a[5] = 105;
    
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;
    
    for (int i = 0; i < 6; ++i) {
        for (int j = 0; j <= A; ++j) {
            dp[i+1][j] |= dp[i][j];
            if (j >= a[i]){
                dp[i+1][j] |= dp[i][j-a[i]];
                dp[i+1][j] |= dp[i+1][j-a[i]];
            }
        }
    }
    dp[6][0] = false;
    if (dp[6][A]) cout << 1 << endl;
    else cout << 0 << endl;
}


Measured memory_bytes: 1528
/*Author: Gautam*/
 
 
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
#define MOD 1000000007
#define ull unsigned long long int
#define newline cout<<endl
 
 
/* TYPE DEFINITIONS */
typedef     long long int        ll;
typedef     vector<ll>     vi;
typedef     pair<int,int>   pi;
 
 
 
/* MATH */
bool isPrime(ull n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ull i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
 
ll pow(ll a,ll b)
{
    ll res=1;
    while(b>0)
    {
        if(b&1)res=(res*a);
        a=(a*a);
        b>>=1;
    }
    return res;
}

  
//
/* MACROS */
 
#define  all(A)         (A).begin() , (A).end()
#define  arrall(A,n)    (A),((A)+(n))
#define  rall(A)        (A).rbegin() , (A).rend()
#define  sz(A)          (int)(A).size()
#define  pb             push_back
#define  ppb            pop_back
#define  mp             make_pair
#define  ln(X)          (int)(X).length()
#define  square(X)      ((X)*(X))
#define  cube(X)        ((X)*(X)*(X))
#define  forn(i, n)  for (int i = 0; i < int(n); i++)
#define  forr(i, n)  for (int i = int(n - 1); i >= 0; i--)
#define  fora(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define  forb(i, a, b)  for (int i = int(a); i >= int(b); i--)
#define  fore(it, a)    for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) 
void solve()
{
    int a,b;
    cin>>a>>b;
    if(a<=9&&b<=9)cout<<a*b;
    else cout<<-1;

}  
int main()
{
 
    FastIO;
    ll t=1;
   // cin>>t;
    while(t--)
    {
        solve();
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)

int main() {
	string s; cin >> s;
	ll a = s.find('A');
	ll b = s.rfind('Z');
	cout << b - a + 1 << endl;

	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#define NUM 200000

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/***
* pivotを決め、
* 全データをpivotを境目に振り分け、
* pivotの添え字を返す
***/
int partition (int array[], int left, int right) {
  int i, j, pivot;
  i = left;
  j = right + 1;
  pivot = left;   // 先頭要素をpivotとする

  do {
    do { i++; } while (array[i] < array[pivot]);
    do { j--; } while (array[pivot] < array[j]);
    // pivotより小さいものを左へ、大きいものを右へ
    if (i < j) { swap(&array[i], &array[j]); }
  } while (i < j);

  swap(&array[pivot], &array[j]);   //pivotを更新

  return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
  int pivot;

  if (left < right) {
    pivot = partition(array, left, right);
    quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
    quick_sort(array, pivot+1, right);
  }
}

int main (void) {
  int a[NUM];
  int n,count = 0;

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

  quick_sort(a,0,n - 1);


  for(int i = 0;i < n - 1;i++){
    if(a[i] == a[i + 1]){
      printf("NO\n");
      count++;
      break;
    }
  }

  if(count == 0){
    printf("YES\n");
  }
  

  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
vector<vector<int>> grid(6, vector<int>(6, 0));

int main(){
    int h, w, k; cin >> h >> w >> k;
    for (int i=0; i!=h; i++){
        string s; cin >> s;
        for (int j = 0; j!=w; j++){
            if (s[j] == '#') grid[i][j] = 1;
        }
    }

    int sum=0;
    for (int i=0; i!=(int)pow(2, h+w); i++){
        int num = 0;
        for (int r=0; r!=h; r++){
            for (int c=0; c!=w; c++){
                if (!((i>>r)&1) && !((i>>(h+c))&1) && grid[r][c]){
                    num++;
                }
            }
        }
        if (num==k) sum++;
    }
    cout << sum << endl;
    return 0;
}

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

int x[90010], y[90010], sum[90010];
int main() {
  int H, W, D;
  cin >> H >> W >> D;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      int a;
      cin >> a;
      a--;
      x[a] = i;
      y[a] = j;
    }
  }
  for (int i = 0; i < H * W; i++) {
    if (i >= D) sum[i] = sum[i - D] + abs(x[i] - x[i - D]) + abs(y[i] - y[i - D]);
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    cout << sum[r] - sum[l] << endl;
  }
  return 0;
}


Measured memory_bytes: 4648
// おせんべい
/*
  横10行以下なので、すべての裏返し方を全列挙。
  それぞれの場合に、出荷できるせんべいが最大になる縦の裏返し方を考える。
*/
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAX_R = 10;
const int MAX_C = 10000;
bool senbei[MAX_R][MAX_C];



int main() {
  while (true) {
    // 入力
    int r, c;
    cin >> r >> c;
    if (!(r | c))
      return 0;
    int buf;
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
        cin >> buf;
        if (buf) {
          senbei[i][j] = true;
        } else {
          senbei[i][j] = false;
        }
      }
    }

    // 計算
    // bitDPみたいに、2進法の数iと横r行のひっくり返し方を対応させる
    int cnt, cnt_r;
    int cnt_max = 0;
    int last = 1 << r;
    bool tate[MAX_R];
    for (int i = 0; i < last; i++) {
      cnt = 0;
      int k = i;
      for (int j = 0; j < r; j++) {
        // tate[j] = 1ならj行目をひっくり返す。0ならひっくり返さない。
        tate[j] = (k % 2 == 1) ? true: false;
        k /= 2;
      }
      for (int j = 0; j < c; j++) {
        cnt_r = 0;
        for (int l = 0; l < r; l++) {
          if (senbei[l][j] ^ tate[l])
            cnt_r++;
        }
        cnt += max(cnt_r, r - cnt_r);
      }
      cnt_max = max(cnt_max, cnt);
    }
    // 出力
    cout << cnt_max << endl;
  }
}

Measured memory_bytes: 1256
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define MAXN 1000005
#define INF 1000000000
#define MOD 1000003
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> P;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef __gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> pq;
int q,x[MAXN],d[MAXN],n[MAXN];
int fact[MAXN],invf[MAXN];
int pow_mod(int a,int i)
{
    int s=1;
    while(i)
    {
        if(i&1) s=1LL*s*a%MOD;
        a=1LL*a*a%MOD;
        i>>=1;
    }
    return s;
}
int get_ans(int l,int r)
{
    if(l==0) return fact[r];
    return 1LL*fact[r]*invf[l-1]%MOD;
}
int main()
{
    fact[0]=invf[0]=1;
    for(int i=1;i<MOD;i++) fact[i]=1LL*fact[i-1]*i%MOD;
    invf[MOD-1]=pow_mod(fact[MOD-1],MOD-2);
    for(int i=MOD-2;i>=1;i--) invf[i]=1LL*invf[i+1]*(i+1)%MOD;
    scanf("%d",&q);
    for(int i=1;i<=q;i++) scanf("%d%d%d",&x[i],&d[i],&n[i]);
    for(int i=1;i<=q;i++)
    {
        if(d[i]==0) printf("%d\n",pow_mod(x[i],n[i]));
        else if(x[i]==0) puts("0");
        else
        {
            int mult=1LL*x[i]*pow_mod(d[i],MOD-2)%MOD;
            int ans=pow_mod(d[i],n[i]);
            if(n[i]>=MOD) puts("0");
            else
            {
                int l=mult,r=(mult+n[i]-1)%MOD;
                int res;
                if(l<=r) res=get_ans(l,r);
                else res=0;
                ans=1LL*res*ans%MOD;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}



Measured memory_bytes: 15232
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
const ll mod=1e9+7;
vector<int> nei[maxn];
ll num[5][maxn];
void dfs(int root,int fa)
{
	num[0][root]=num[1][root]=1;
	for(int i=0;i<(int)nei[root].size();i++)
	{
		int next=nei[root][i];
		if(next==fa) continue;
		dfs(next,root);
		(num[0][root]*=(num[0][next]+num[1][next]))%=mod;
		(num[1][root]*=num[0][next])%=mod;
	}
	return;
}
void fl()
{
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
int main()
{
//    fl();
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		nei[u].push_back(v);
		nei[v].push_back(u);
	}
	dfs(1,0);
	ll ans=(num[0][1]+num[1][1])%mod;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 17544
n, m, l = map(int, input().split())
a = [[0 for i in range(m)] for j in range(n)]
b = [[0 for i in range(l)] for j in range(m)]
c = [[0 for i in range(l)] for j in range(n)]

for i in range(n):
    s = list(map(int, input().split()))
    for j in range(m): a[i][j] = s[j]
for i in range(m):
    s = list(map(int, input().split()))
    for j in range(l): b[i][j] = s[j]
for i in range(n):
    for j in range(l):
        s = 0
        for x in range(m):
            s += a[i][x] * b[x][j]
        c[i][j] = s
for i in range(n):
    for j in range(l):
        if j == (l - 1):
            print(c[i][j])
        else:
            print(c[i][j], "", end = "")


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

int main(){
  int n,k,x,y;
  cin >> n >> k >> x >> y;
  ull ans=0;
  for(int i=1;i<=n;i++){
    if( i <= k ){
      ans += x;
    }else{
      ans += y;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
N = int(input())
A = {}
B = []
for n in range(N):
    a = input()
    B.append(a)
    A[a] = 0
for n in range(N):
    A[B[n]] += 1
res = 0
C = []
for key, value in A.items():
    if res < value:
        res = value
for key, value, in A.items():
    if res <= value:
        C.append(key)
C.sort()
for c in C:
    print(c)

Measured memory_bytes: 33416
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		ArrayList<String> list = new ArrayList<>();

		while(true){

			StringBuilder str = new StringBuilder(in.next());

			if(str.substring(0).equals("-")){

				break;

			}else{

			int shuffle_num = in.nextInt();

				for(int i = 0; i < shuffle_num; i++){

					int card_num = in.nextInt();

					String shuffle_word = str.substring(0, card_num);

					str.delete(0, card_num);

					str.append(shuffle_word);

				}
			}

			list.add(str.toString());

		}

		for(String result: list){

			System.out.println(result);

		}
	}
}

Measured memory_bytes: 26296
#include <iostream>
#include <vector>
using namespace std;
int main(){
  string t;
  cin >> t;
  int len = t.size();
  if (len == 1) {
    t = "D";
  } else {
    for (int i = 0 ; i < len - 1 ; i ++) {
    char prev = t.at(i) , next = t.at(i + 1);
    if (prev == 'P'){
      if (next == '?'){
        t.at(i + 1) = 'D';
      }
    } else if (prev == 'D'){
      if (next == '?') {
        t.at(i + 1) = 'D';
      }
    } else {
      t.at(i) = 'D';
      if (next == '?') {
        t.at(i + 1) = 'D';
      }
    }
  }
  }
  cout << t << endl;
}

Measured memory_bytes: 3760