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

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define fWrite          freopen ("out.txt","w",stdout);
#define TC              int t;cin >> t;FOR(tc,1,t)
#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

#define Make(x,p)       (x  (1<<p))
#define DeMake(x,p)     (x & ~(1<<p))
#define Check(x,p)      (x & (1<<p))
#define popcount(x)     __builtin_popcount(x)

const int MOD=1e9+7;
int n,m;
char grid[1005][1005];
LL dp[1005][1005];

LL call(int i,int j){
    if(i==n and j==m) return 1;
    if(dp[i][j]!=-1) return dp[i][j];
    LL a=0,b=0;
    if(i+1<=n and grid[i+1][j]!='#') a=call(i+1,j);
    if(j+1<=m and grid[i][j+1]!='#') b=call(i,j+1);
    return dp[i][j]=(a+b)%MOD;
}

int main()
{
    cin >> n >> m;
    FOR(i,1,n) FOR(j,1,m) cin >> grid[i][j];
    MEM(dp,-1);
    cout << call(1,1)%MOD;
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
#include <boost/algorithm/searching/knuth_morris_pratt.hpp>

int main() {
    using namespace std;
    using namespace boost::algorithm;
    string s, t;
    cin >> s >> t;
    unsigned long loop{1}, M{t.size()};
    {
        auto tt = t + t;
        auto it = knuth_morris_pratt_search(tt.begin() + 1, tt.end() - 1, t.begin(), t.end());
        if(it != tt.end() - 1){
            auto l = it - tt.begin();
            t = string(tt.begin(), it);
            loop = M / l;
            M = l;
        }
    }
    {
        auto ss = s + s;
        auto it = knuth_morris_pratt_search(ss.begin() + 1, ss.end() - 1, s.begin(), s.end());
        if(it != ss.end() - 1)s = string(ss.begin(), it);
    }
    unsigned long N{s.size()};
    {
        unsigned long n{(N + M - 1) / N};
        string ss(s.begin(), s.end());
        while(n){
            if(n & 1)s += ss;
            ss += ss;
            n >>= 1;
        }
    }

    vector<unsigned long> morris_pratt_search_result;
    auto morris_pratt_search_all = [&morris_pratt_search_result](auto s, auto t){
        string Q(t + "_" + s);
        unsigned long N{s.size()}, M{t.size()}, L{Q.size()};
        vector<unsigned long> MP(L + 1);
        for(unsigned long i = 1, j = 0; i <= L; MP[i++] = j){
            while(j > 0 && Q[i - 1] != Q[j - 1])j = MP[j - 1];
            if(++j > M && i >= j + M && i < j + N + M)morris_pratt_search_result.push_back(i - j - M);
        }
    };

    morris_pratt_search_all(s, t);
    vector<unsigned long> idx(N);
    for(const auto& i : morris_pratt_search_result)if(i < N)idx[i] = ~0UL;

    auto f = [rec = [&idx, &M, &N](auto f, unsigned long i, unsigned long t, unsigned long k) -> unsigned long{
        if(!idx[i])return 0;
        if(i == t && k)idx[i] = 2 * N;
        else if(!~idx[i])idx[i] = f(f, (i + M) % N, t, 1) + 1;
        return idx[i];
    }](unsigned long n){rec(rec, n, n, 0);};
    for(unsigned long i = 0; i < N; ++i)f(i);

    unsigned long ans{*max_element(idx.begin(), idx.end())};
    if(ans > N)puts("-1");
    else cout << ans / loop << endl;
    return 0;
}

Measured memory_bytes: 44916
N, M = [int(_) for _ in input().split()]
PS = [input().split() for _ in range(M)]
count = [0] * (N + 1)
isac = [0] * (N + 1)
for p, s in PS:
    p = int(p)
    if isac[p] == 1:
        continue
    if s == 'AC':
        isac[p] = 1
    else:
        count[p] += 1
wa = 0
ac = 0
for i in range(N + 1):
    if isac[i] == 1:
        ac += 1
        wa += count[i]
print(ac, wa)


Measured memory_bytes: 68568
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 100000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}

void Integer_factorization(ll factor[],ll n){
    ll a = 2;
    bool flag = false;
    for(int p = 2;p*p <= n;p++){
        while(n%p == 0){
            n/=p;
            factor[p]++;
        }
    }
    if(n!=1)  factor[n]++; //prime num
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}

void solve(void){
    int c[3][3];
    int p[3] = {0,1,2};
    rep(i,0,3) rep(j,0,3) cin >> c[i][j];
    int ans = 0;
       rep(i,0,3){
           rep(j,0,3){
               ans += c[i][j];
           }
       }
    if(ans == (c[0][0]+c[1][1]+c[2][2])*3)ys();
    else ns();
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

void Main() {
  Cin(int, n);
  vector<string> vs(n);
  for (auto& e : vs) cin >> e;

  set<string> ss;

  bool ok = true;
  for (int i = 0; i < n - 1; ++i) {
    if (vs[i].back() != vs[i + 1].front()) ok = false;
  }
  for (auto e : vs) {
    if (ss.count(e)) ok = false;
    ss.insert(e);
  }
  puts(ok ? "Yes" : "No");
  return;
}

int main() {
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n;
int val[3][N],p[N],inv[N],cir[2];
void fail(){puts("No");exit(0);}
int main(){
    scanf("%d",&n);
    for(int t=0;t<3;t++)
        for(int i=1;i<=n;i++)
            scanf("%d",&val[t][i]);
    for(int i=1;i<=n;i++){
        p[i]=(val[1][i]+1)/3;
        int temp[3]={val[0][i],val[1][i],val[2][i]};
        sort(temp,temp+3);
        for(int j=0;j<3;j++) if(temp[j]!=p[i]*3+j-2) fail();
        if(val[1][i]%3!=2) fail();
        inv[i]=val[0][i]>val[1][i] ? 1:0;
    }
    for(int i=1;i<=n;i++) if((p[i]-i)%2!=0) fail();
    for(int i=2;i<=n;i++) inv[i%2]+=inv[i];
    for(int i=1;i<=n;i++)
        if(p[i]!=0){
            cir[i%2]++;
            for(int j=i,last;j!=0;last=j,j=p[j],p[last]=0);
        }
    for(int i=0;i<=1;i++) if(((n/2+(n&i))-cir[i])%2!=inv[i^1]%2) fail();
    return puts("Yes"),0;
}

Measured memory_bytes: 2176
import java.util.*;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int Y = sc.nextInt();
 
    int cou = 0;
    for(int i=0; i<=X; i++){
    if(i*2+(X-i)*4==Y){
        cou++;
}
}
    if(cou>0){
   	System.out.println("Yes");
    }else{
	System.out.println("No");
      }
}
}


Measured memory_bytes: 35552
#include<stdio.h>
#include<math.h>
int main(void){
long n,ans,min=1000000000000;
  scanf("%ld",&n);
  for(long i=1;i<=sqrt(n);i++){
if(n%i==0){ans=i+n/i-2;
           //printf("%ld\n",ans);
           if(min>ans)min=ans;
          }
  }
  printf("%ld",min);
  return 0;
}

Measured memory_bytes: 128
import numpy as np
X,N = map(int,input().split())

if N ==0:
    print(X)

else:
    p = list(map(int,input().split()))

    length =np.zeros(102)
    length =list(length)

    for i in range(len(length)):
        length[i]= abs(X-i)

    for i in range(N):
        length[p[i]]=1000

    ans = length.index(min(length))
    print(ans)


Measured memory_bytes: 27060
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
    int a,b;
    bool operator<(const node&o)const
    {
        return b>o.b;
    }
}p[100005];
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        q.push(x);
    }
    for(int i=1;i<=m;i++)
        scanf("%d%d",&p[i].a,&p[i].b);
    sort(p+1,p+1+m);
    for(int i=1;i<=m;i++)
    {
        if(p[i].b<q.top()) break;
        for(int j=1;j<=p[i].a;j++)
        {
            if(p[i].b>q.top())
                q.pop(),q.push(p[i].b);
            else break;
        }
    }
    long long ans=0;
    while(!q.empty())
    {
        ans+=q.top();
        q.pop();
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 1528
using System;

namespace ABC045Ax
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c, s;

            a = int.Parse(Console.ReadLine());
            b = int.Parse(Console.ReadLine());
            c = int.Parse(Console.ReadLine());

            s = (a + b) * c / 2;

            Console.WriteLine(s);
            Console.ReadKey();


        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,x;cin>>n>>m>>x;
  vector<int>p(n);
  vector<vector<int>>a(n,vector<int>(m));
  for(int i=0;i<n;i++){
    cin>>p[i];
    for(int j=0;j<m;j++)cin>>a[i][j];
  }
  int wwwww=100000000;
  for(int b;b<(1<<n);b++){
    vector<int>c(m);int s=0;
    for(int i=0;i<n;i++){
      if(b>>i&1){
        s+=p[i];
        for(int j=0;j<m;j++)c[j]+=a[i][j];
      }
    }
    bool t=true;
    for(int j=0;j<m;j++){if(c[j]<x)t=false;}
    if(t)wwwww=min(wwwww,s);
  }
  if(wwwww!=100000000)cout<<wwwww<<endl;
  else cout<<-1<<endl;
}




Measured memory_bytes: 3548
import java.util.Scanner;

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

		int total = 0;
		for(int i = 1; i <=N; i++){
			int temp = Calculation(i);
			if(temp >= A && temp <= B){
				total += i;
			}
		}
		System.out.println(total);
	}

	public static int Calculation(int num){
		int ret = 0;
		while(num > 0){
			int mod = num % 10;
			ret += mod;
			num = num / 10;
		}
		return ret;
	}
}

Measured memory_bytes: 21716
// g++ macro.cpp -std=c++14
#include <bits/stdc++.h> //STL include
typedef long long ll;// long long int
const ll INF = 10000000000;//INFinity
using namespace std;//namespace

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}//transform
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//#define int long long // yabai

#define dump(x)  cout << #x << " = " << (x) << endl;// debug cout

#define FOR(i,a,b) for(int i=(a);i<(b);++i)// for macro
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define ALL(obj) (obj).begin(),(obj).end()// iterator

#define pb(a) push_back(a)//push_back
#define mp make_pair// make_pair


int main(){

    int m;
    cin>>m;
    cout<<24+(24-m)<<endl;

    return 0;
}


Measured memory_bytes: 764
#include <stdio.h>

int Liner_Search(int a[], int n, int key) {
    int i = 0;
    a[n] = key;
    while (a[i] != key) i++;
    if (i == n) return 0;
    return 1;
}

int main() {
    int i, n, a[10000+1], q, key, sum = 0;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    
    scanf("%d", &q);
    
    for (i = 0; i < q; ++i) {
        scanf("%d", &key);
        if(Liner_Search(a, n, key)) sum++;
    }
    
    printf("%d\n", sum);
    
    return 0;
}

Measured memory_bytes: 1776
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll dp[1001][1001];

int main(){
  ll n,k;
  cin>>n>>k;

  dp[0][0]=1;
  
  for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
      dp[i][j]+=dp[i-1][j-1]*(k-j+1);
      dp[i][j]+=dp[i-1][j]*j;
      dp[i][j]%=mod;
    }
  }
  cout<<dp[n][k]<<endl;
  return 0;
}


Measured memory_bytes: 9988
n, y = gets.split.map(&:to_i)

can = false
i1 = 0
j = 0
k = 0
# 1000円札の枚数を固定して鶴亀算
0.upto(n) do |i|
  i1 = i
  nn = n - i
  yy = y - i * 1000
  break if yy < 0

  next unless yy % 5000 == 0

  # 手元で連立方程式解く
  # j+k= nn
  # 5000j+10000k=yy
  j = 2 * nn - yy / 5000
  next if j < 0 #TODO この場合ある？

  k = yy / 5000 - nn
  next if k < 0

  # 念の為チェック
  if i1+j+k==n && i*1000+j*5000+k*10000==y
    can = true
    break
  end
end

puts can ? [k,j,i1].join(' ') : '-1 -1 -1'

Measured memory_bytes: 1788
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto n = readln.chomp.to!int;
  auto a = readln.chomp.split.to!(real[]);
  
  real sum = 0.0;
  foreach (e; a) {
    sum += 1 / e;
  }
  writefln("%.12f",1/sum);
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
	int a,b,c;
	int m=0;
	int cnt=0;
	cin >> a >> b >> c;
	
	while(a%2==0&&b%2==0&&c%2==0){
		if(a==b&&b==c){
		cout << -1 << endl;
	 return 0;
	}
		int d,e,f;
		d  = a/2+b/2;
		e = a/2+c/2;
		f = b/2+c/2;
		a = d;b=e;c=f;
		cnt++;

	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
x = list(input())

x12 = int(''.join(x[:2]))
x34 = int(''.join(x[2:]))

is_12YYMM = True
is_34YYMM = None
is_12MMYY = None
is_34MMYY = True

if (x12 > 12) or (x12 < 1):
  is_12MMYY = False
else:
  is_12MMYY = True

if (x34 > 12) or (x34 < 1):
  is_34YYMM = False
else:
  is_34YYMM = True

if (is_12YYMM and is_34YYMM) and (is_12MMYY and is_34MMYY):
  print('AMBIGUOUS')
elif (is_12YYMM and is_34YYMM):
  print('YYMM')
elif (is_12MMYY and is_34MMYY):
  print('MMYY')
else:
  print('NA')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000000000
#define MAXN        100000
#define mod         998244353  
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,sum=0,sum1=0,j,diff;
    cin>>n;
    string s;
    cin>>s;
    ll a[n+1][3];
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++){
        if(s[i]=='R'){
            a[i+1][0]=1;
        }
        if(s[i]=='G'){
            a[i+1][1]=1;
        }
        if(s[i]=='B'){
            a[i+1][2]=1;
        }
        a[i+1][0]+=a[i][0];
        a[i+1][1]+=a[i][1];
        a[i+1][2]+=a[i][2];
    }
    // cout<<s<<endl;
    // for(i=0;i<=n;i++){
    //     cout<<a[i][0]<<" ";
    // }
    // cout<<endl;
    // for(i=0;i<=n;i++){
    //     cout<<a[i][1]<<" ";
    // }
    // cout<<endl;
    // for(i=0;i<=n;i++){
    //     cout<<a[i][2]<<" ";
    // }
    // cout<<endl;
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            sum1=0;
            diff=0;
            if(s[i]=='R' && s[j]=='G'){
                diff=j-i;
                sum1+=(a[n][2]-a[j+1][2]);
                if((j+diff)<n){
                    if(s[j+diff]=='B'){
                        sum1--;
                    }
                }
            }
            if(s[i]=='R' && s[j]=='B'){
                diff=j-i;
                sum1+=(a[n][1]-a[j+1][1]);
                if((j+diff)<n){
                    if(s[j+diff]=='G'){
                        sum1--;
                    }
                }
            }
            if(s[i]=='G' && s[j]=='B'){
                diff=j-i;
                sum1+=(a[n][0]-a[j+1][0]);
                if((j+diff)<n){
                    if(s[j+diff]=='R'){
                        sum1--;
                    }
                }
            }
            if(s[i]=='G' && s[j]=='R'){
                diff=j-i;
                sum1+=(a[n][2]-a[j+1][2]);
                if((j+diff)<n){
                    if(s[j+diff]=='B'){
                        sum1--;
                    }
                }
            }
            if(s[i]=='B' && s[j]=='G'){
                diff=j-i;
                sum1+=(a[n][0]-a[j+1][0]);
                if((j+diff)<n){
                    if(s[j+diff]=='R'){
                        sum1--;
                    }
                }
            }
            if(s[i]=='B' && s[j]=='R'){
                diff=j-i;
                sum1+=(a[n][1]-a[j+1][1]);
                if((j+diff)<n){
                    if(s[j+diff]=='G'){
                        sum1--;
                    }
                }
            }
            // cout<<i<<" "<<j<<" "<<diff<<" ";
            // cout<<sum1<<endl;
            sum+=sum1;
        }
    }
    cout<<sum;
}

Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define MAX 100010
using namespace std;

pair<int, int> arr[MAX];
priority_queue<int> pq;

int main(void)
{
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> arr[i].first >> arr[i].second;
	sort(arr, arr + N);
	int idx = 0;
	long long ans = 0;
	for (int i = 0; i <= M; i++)
	{
		while (idx < N && arr[idx].first == i) pq.push(arr[idx++].second);
		if (!pq.empty())
		{
			ans += pq.top();
			pq.pop();
		}
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

bool check(int a,int b,int c,int d){
    if(a==0 and b==1 and c==2)return true;
    if(b==0 and c==1 and d==2)return true;
    if(a==0 and c==1 and d==2)return true;
    if(b==0 and c==2 and d==1)return true;
    if(b==1 and c==0 and d==2)return true;
    if(a==0 and b==1 and d==2)return true;
    return false;
}

int dp[102][5][5][5];
int main(){
    //AGC,ACG,GACをふくまない
    int mod=1000000007;
    int n;
    cin>>n;
    dp[0][4][4][4]=1;
    rep(i,n){
        rep(a,5){
            rep(b,5){
                rep(c,5){
                    rep(d,4){
                        if(check(a,b,c,d)){
                            continue;
                        }
                        dp[i+1][b][c][d]+=dp[i][a][b][c];
                        dp[i+1][b][c][d]%=mod;
                    }
                }
            }
        }
    }
    int ans=0;
    rep(a,4){
        rep(b,4){
            rep(c,4){
                ans+=dp[n][a][b][c];
                ans%=mod;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
  int N,i,p,L,R,sum =0 ,min =100000000;
  int *x;

  scanf("%d",&N);

  x= calloc(N, sizeof(int));

  for(i=0;i<N;i++)
    scanf("%d",&x[i]);

  L = x[0];
  R = x[0];
  for (i=0; i<N; i++)
    {
      if(L > x[i]) L = x[i];
      else if(R < x[i]) R = x[i];
    }

  for(p=L; p <= R; p++)
    {
      for(i=0; i<N; i++){
        sum += ((x[i]-p)*(x[i]-p)) ;
      }
      if( sum < min ){min = sum;}
    sum = 0;
    }
  printf("%d", min);

  free(x);
  return 0;
}


Measured memory_bytes: 1720
#include<bits/stdc++.h>
#define ll long long 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define sl(a) a.size()
#define mod 1000000007 
#define lcm(a,b) (a*b)/__gcd(a,b)
#define MAX 10000003
using namespace std;
ll count(ll arr[], ll n, ll i)
{
    if(i>=n-1) return 0;
    if(i<n-2) 
    {
        ll x=abs(arr[i+1]-arr[i]),y=abs(arr[i+2]-arr[i]);
        return min(x+count(arr,n,i+1),y+count(arr,n,i+2));
    }
    return abs(arr[i+1]-arr[i]);
}
void solve()
{
    ll n;  cin>>n;
    ll arr[n],dp[n]={0};
    rep(i,0,n) cin>>arr[i];
    dp[0]=0, dp[1]=abs(arr[1]-arr[0]);
    rep(i,2,n)
    {
        dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
    }cout<<dp[n-1];
}
int main()
{
    BOOST
    int T=1;  //cin>>T;
    while(T--) solve();
    return 0;
}

Measured memory_bytes: 5136
// abc147_e
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int H, W;
    cin >> H >> W;

    vector<vector<int>> A(H, vector<int>(W, 0));
    vector<vector<int>> B(H, vector<int>(W, 0));

    REP(i, H) REP(j, W) cin >> A[i][j];
    REP(i, H) REP(j, W) cin >> B[i][j];

    vector<vector<int>> X(H, vector<int>(W, 0));
    REP(i, H) REP(j, W){
        X[i][j] = abs(A[i][j] - B[i][j]);
    }

    int mx_n = 12801;
    vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(mx_n)));
    dp[0][0][mx_n/2] = true;
    REP(i, H) REP(j, W) {

        int x = X[i][j];

        if (i < H-1){
            REPN(k, x, mx_n-x){
                dp[i+1][j][k + x] = dp[i+1][j][k + x] | dp[i][j][k];
                dp[i+1][j][k - x] = dp[i+1][j][k - x] | dp[i][j][k];
            }
        }

        if (j < W-1){
            REPN(k, x, mx_n-x){
                dp[i][j+1][k + x] = dp[i][j+1][k + x] | dp[i][j][k];
                dp[i][j+1][k - x] = dp[i][j+1][k - x] | dp[i][j][k];
            }
        }
    }

    int x = X[H-1][W-1];
    auto tmp = dp[H-1][W-1];
    REPN(k, x, mx_n - x){
        dp[H-1][W-1][k+x] = tmp[k];
        dp[H-1][W-1][k-x] = tmp[k];
    }

//    vector<int> asdf(20);
//    iota(ALL(asdf), 0);
//    print(0, 0, asdf);
//
//    REP(i, H){
//        print(i, "-----");
//        REP(j, W){
//            print(i, j, dp[i][j]);
//        }
//    }
//    print(0, 0, tmp);


    int ans = INF;
    REPN(k, mx_n/2, mx_n){
        if (dp[H-1][W-1][k]) {
            ans = min(ans, k-mx_n/2);
        }
    }

    REPN_REV(k, 0, mx_n/2){
        if (dp[H-1][W-1][k]) {
            ans = min(ans, mx_n/2-k);
        }
    }

    print(ans);


    return 0;
}


Measured memory_bytes: 12800
color = str(input())

ans1 = 0
ans2 = 0

for i in range(len(color)):
    if (i%2==0 and color[i:i+1]=='0') or (i%2==1 and color[i:i+1]=='1'):
        ans1+=1
    else:
        ans2+=1

print(min(ans1,ans2))
        


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

int main(){
  string s;
  cin>>s;
  string t;
  
  for(int i=0;i<s.size();i++){
    switch(s.at(i)){
      case '0':
        t=t+'0';
        break;
      case '1':
        t=t+'1';
        break;
      case 'B':
        if(!t.empty()){
          t.pop_back();
        }
    }
  }
  
  cout<<t<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<set>
#include<algorithm>
#define int long long
using namespace std;
struct man
{
	int a,b,c;
	bool operator<(const man &x)const{return a-b<x.a-x.b;}
}x[200000];
int f[200000],g[200000];
signed main()
{
	int a,b,c,ans=0;
	scanf("%lld%lld%lld",&a,&b,&c);
	for(int i=1;i<=a+b+c;i++)
	{
		scanf("%lld%lld%lld",&x[i].a,&x[i].b,&x[i].c);
		x[i].a-=x[i].c;
		x[i].b-=x[i].c;
		ans+=x[i].c;
	}
	sort(x+1,x+a+b+c+1);
	multiset<int> s;
	int tot1=0,tot2=0;
	for(int i=1;i<=a+b+c;i++)
	{
		s.insert(x[i].b);
		tot1+=x[i].b;
		if(s.size()>b)
		{
			tot1-=*s.begin();
			s.erase(s.begin());
		}
		f[i]=tot1;
	}
	s.clear();
	for(int i=a+b+c;i>0;i--)
	{
		s.insert(x[i].a);
		tot2+=x[i].a;
		if(s.size()>a)
		{
			tot2-=*s.begin();
			s.erase(s.begin());
		}
		g[i]=tot2;
	}
	int mx=-(1ll<<62);
	for(int i=b;i<=b+c;i++)mx=max(mx,f[i]+g[i+1]);
	printf("%lld\n",ans+mx);
	return 0;
}


Measured memory_bytes: 11520
import copy

N,M = map(int,input().split())
H = list(map(int,input().split()))

towers = copy.copy(H)

for i in range(M):
    a,b = map(int,input().split())
    if H[a-1] < H[b-1]:
        towers[a-1] = 0
    elif H[a-1] > H[b-1]:
        towers[b-1] = 0
    elif H[a-1] == H[b-1]:
        towers[a-1] = 0
        towers[b-1] = 0

ans = 0

for i in towers:
    if i != 0:
        ans += 1

print(ans)

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

A = [input().strip() for _ in range(N)]
B = [input().strip() for _ in range(M)]
temp = "".join(B)


ans = False

for j in range(N-M+1):
    for i in range(N-M+1):
        tmp = ""
        for y in range(M):
            tmp += A[j+y][i: i + M]
        if tmp == temp:
            ans = True

if ans:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
const ll mod = 1e9 + 7;

int main() {
  int n, m, ac = 0, wa = 0;
  cin >> n >> m;
  vector<int> a(n, 0);
  vector<int> w(n, 0);
  rep(i, m) {
    int p;
    string s;
    cin >> p >> s;
    p--;
    if (s.compare("WA") == 0) {
      if (a[p] == 0) w[p]++;
    } else {
      if (a[p] == 0) {
        ac++;
        a[p]++;
      }
    }
  }
  rep(i, n) {
    if (a[i] != 0) wa += w[i];
  }
  cout << ac << " " << wa << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  int x,y,z,K; cin>>x>>y>>z>>K;
  vector<ll> a(x), b(y), c(z);
  rep(i, x) cin >> a[i];
  rep(i, y) cin >> b[i];
  rep(i, z) cin >> c[i];

  sort(all(a), greater<ll>());
  sort(all(b), greater<ll>());
  sort(all(c), greater<ll>());

  vector<ll> ans;
  rep(i, x) rep(j, y){
    if((i+1)*(j+1) > K) break;
    rep(k, z){
      if((i+1)*(j+1)*(k+1) > K) break;
      ans.pb(a[i]+b[j]+c[k]);
    }
  }

  sort(all(ans), greater<ll>());

  rep(i, K) std::cout << ans[i] << '\n';
}


Measured memory_bytes: 1404
N, K = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]

max_score = max(C[1:])
for init in range(1, N + 1):   # 初めの場所をinitとする
    score = [0]  # k回移動後のスコア
    i = init
    for k in range(1, K + 1):
        i = P[i]  # k回移動後に着くところ
        score.append(score[-1] + C[i])
        max_score = max(max_score, score[k])
        if i == init:  # ループ検出
            loop_score = score[-1]
            loop_len = k
            if loop_score < 0:
                max_score = max(max_score, max(score[1:]))
            else:
                max_score = max(max_score, max(score[j] + loop_score * ((K - j) // loop_len) for j in range(1, loop_len + 1)))
            break

print(max_score)

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

using namespace std;

int main()
{
	int top, bot, r, l, f, b, n, t;
	string str;
	
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		top = 1;
		bot = 6;
		r = 4;
		b = 5;
		f = 2;
		l = 3;
		while(n--){
			cin >> str;
			
			if(str == "north"){
				t = top;
				top = b;
				b = bot;
				bot = f;
				f = t;
			} else if(str == "east"){
				t = top;
				top = l;
				l = bot;
				bot = r;
				r = t;
			} else if(str == "south"){
				t = top;
				top = f;
				f = bot;
				bot = b;
				b = t;
			} else if(str == "west"){
				t = top;
				top = r;
				r = bot;
				bot = l;
				l = t;
			}
		}
		
		cout << top << endl;
	}
	
	return 0;
}

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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    string s;
    cin >> s;
    ll n = s.size();
    ll ans = 0;
    ll con = 0;
    REP(i, n) {
        if(s[i] != 'A' and s[i] != 'C' and s[i] != 'G' and s[i] != 'T')
            con = 0;
        else
            con++;
        chmax(ans, con);
    }
    cout << ans << en;
}

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

    solve();

    /*
    ll t;
    cin >> t;
    REP(i, t) { solve();}
    */

    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int arr[3][3],flag[100]={0},i,j,n,x,x1,x2,x3,x4,x5,x6,x7,x8,x9;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
			cin >> arr[i][j];
	}
	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> x;
		flag[x]=1;
	}
	x1 = flag[arr[0][0]];
	x2 = flag[arr[0][1]];
	x3 = flag[arr[0][2]];
	x4 = flag[arr[1][0]];
	x5 = flag[arr[1][1]];
	x6 = flag[arr[1][2]];
	x7 = flag[arr[2][0]];
	x8 = flag[arr[2][1]];
	x9 = flag[arr[2][2]];

	if(x1*x2*x3 | x4*x5*x6 | x7*x8*x9 | x1*x4*x7 | x2*x5*x8 | x3*x6*x9 | x1*x5*x9 | x3*x5*x7)
		cout <<"Yes\n";
	else
		cout << "No\n";
	return 0;
}


Measured memory_bytes: 256
a = [[[0 for z in range(10)] for y in range(3)] for x in range(4)]
n = int(input())
for i in range(n):
    b, f, r, v = [int(x) for x in input().split()]
    a[b - 1][f - 1][r - 1] += v

for i in range(4):
    for j in range(3):
        print('', *a[i][j])
    if i != 3:
        print('#' * 20)

Measured memory_bytes: 7740
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a) ? 1 : -1)
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    cout << fixed << setprecision(10);
    string s;
    cin>>s;
    REP(i,s.size()){
        cout<<"x";
    }
    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 < (int)N; i++)

struct primeFactor {
  int p, r;
};

vector<primeFactor> primeFactors(int n) {
  vector<primeFactor> res;
  int m = n;
  for(int i = 2; i*i <= m; i++) {
    if(m % i) continue;
    primeFactor f = primeFactor{i,0};
    while(m % i == 0) {
      m /= i;
      f.r++;
    }
    res.push_back(f);
  }
  if(m != 1) {
    res.push_back(primeFactor{m,1});
  }
  return res;
}

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

  int ans = 0;
  for(int i = 1; i <= N; i += 2) {
    int n = 1;
    for(auto pf: primeFactors(i)) n *= (pf.r+1);
    if(n == 8) ans++;
  }

  cout << ans << endl;

  return 0;
}


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


int main(){
  ll D, G;
  cin >> D >> G;
  vector<ll> p(D+1), c(D+1);
  for(int i=1; i<=D; i++) cin >> p.at(i) >> c.at(i);

  int ans = 1001001;
  //コンプリートする問題をbit全探索する
  //vector<ll> comp_solve(D+1);//これをコメントアウトするとテストケースa04がWAになる??
  //for(int i=1; i<=D; i++) comp_solve[i] = 100*i*p[i] + c[i];
  
  for(int i=0; i<(1<<D);i++){//2^D回(最大1024回)ループ
    vector<bool> is_solve(D+1,false);
    int score = 0;
    int num_solve = 0;
    bool is_ok = false;//目標点を越えたらtrue
    for(int j=1; j<=D ; j++){//j*100点問題を解くか解かないのか?のD回ループ     
      if(i & (1<<(j-1))){//j*100点の問題を解くなら...
        score += 100*j*p[j] + c[j];
        num_solve += p[j];
        is_solve[j] = true;
        //cout << " i: "<<i<<" j: "<<j <<" score: "<<score<<" num_solve: "<<num_solve<< endl;
        if(score >= G){
          is_ok = true;
          ans = min(ans, num_solve);
          //cout << "yah1" <<endl;
          break;//jループを抜ける
        }
      }
    }
    if(is_ok) continue;//iループを次へすすめる
    /*for(int j=D; j>=1; j--){
      cout << "is_solve["<<j<<"]: " << is_solve[j] << " ";
    } cout << endl;*/
    for(int j=D; j>=1; j--){//コンプリートしてない問題で一番得点の高い問題を数問解く(全完しない)
      if(is_solve[j]==true) continue;
      int left_score = G - score;
      int num = ceil( (double)left_score / (100*j));//切り上げ!!int同士の計算だと切り下げになるからdoubleにキャスト
      if(num <= p[j]){
        num_solve += num;
        score += num_solve* 100*j;
      }
      //cout << " left_score: " << left_score<<" num: " <<num<<" num_solve: "<<num_solve<<" p["<<j<<"]: "<<p[j]<<endl;
      if(score >= G) ans = min(ans, num_solve);
      break;//コンプリートしない問題は１種類だけなのでjループを抜ける
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		if (A.length()>B.length()) {
			System.out.println("GREATER");
		} else if(A.length()==B.length()){
			for (int i = 0; i < A.length(); i++) {
				char a = A.charAt(i);
				char b = B.charAt(i);
				if (a > b) {
					System.out.println("GREATER");
					break;
				}else if(a < b) {
					System.out.println("LESS");
					break;
				}
				if (i== A.length()-1) {
					System.out.println("EQUAL");
				}
			}

		}else if(A.length()<B.length()){
			System.out.println("LESS");
		}




	}


}



Measured memory_bytes: 35696
t0=[]; t2=[]; n=gets.to_i
t0=gets.chomp.split(" ").map(&:to_i); m=gets.to_i
sum=t0.inject(:+)
m.times do|i|
  p0,t1=gets.chomp.split(" ").map(&:to_i)
  t2[i]=sum-t0[p0-1]+t1
end
puts t2


Measured memory_bytes: 1788
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, M, X = get_ints_minus_one
A = get_ints_minus_one

left = 0
index = 0
loop do
  if A[index] >= X
    break
  end
  left += 1
  index += 1
end

right = 0
while index <= M
  right += 1
  index += 1
end

puts [left, right].min


Measured memory_bytes: 14404
#include <iostream>
#include <cmath>
#define eps 1e-9
using namespace std;
typedef struct
{
    double x;
    double y;
}Point;
double area(Point a,Point b,Point c)
{
    return a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
    Point a,b,c,tar;
    while(cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>tar.x>>tar.y)
    {
        double sum=abs(area(a,b,c));
        double cmp=abs(area(a,b,tar))+abs(area(a,c,tar))+abs(area(b,c,tar));
        if(fabs(sum-cmp)<eps)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

/**
 * Segment Tree. This data structure is useful for fast folding on intervals of an array
 * whose elements are elements of monoid M. Note that constructing this tree requires the identity
 * element of M and the operation of M.
 * Header requirement: vector, algorithm
 * Verified by AtCoder ABC017-D (http://abc017.contest.atcoder.jp/submissions/660402)
 */
template<class I, class BiOp = I (*) (I, I)>
class SegTree {
  int n;
  std::vector<I> dat;
  BiOp op;
  I e;
public:
  SegTree(int n_, BiOp op, I e) : op(op), e(e) {
    n = 1;
    while (n < n_) { n *= 2; } // n is a power of 2
    dat.resize(2 * n);
    for (int i = 0; i < 2 * n - 1; i++) {
      dat[i] = e;
    }
  }
  /* ary[k] <- v */
  void update(int k, I v) {
    k += n - 1;
    dat[k] = v;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  void update_array(int k, int len, const I *vals) {
    for (int i = 0; i < len; ++i) {
      update(k + i, vals[i]);
    }
  }
  /*
    Updates all elements. O(n)
   */
  void update_all(const I *vals, int len) {
    for (int k = 0; k < std::min(n, len); ++k) {
      dat[k + n - 1] = vals[k];
    }
    for (int k = std::min(n, len); k < n; ++k) {
      dat[k + n - 1] = e;
    }
    for (int b = n / 2; b >= 1; b /= 2) {
      for (int k = 0; k < b; ++k) {
	dat[k + b - 1] = op(dat[k * 2 + b * 2 - 1], dat[k * 2 + b * 2]);
      }
    }
  }
  /* l,r are for simplicity */
  I querySub(int a, int b, int k, int l, int r) const {
    // [a,b) and  [l,r) intersects?
    if (r <= a || b <= l) return e;
    if (a <= l && r <= b) return dat[k];
    I vl = querySub(a, b, 2 * k + 1, l, (l + r) / 2);
    I vr = querySub(a, b, 2 * k + 2, (l + r) / 2, r);
    return op(vl, vr);
  }
  /* [a, b] (note: inclusive) */
  I query(int a, int b) const {
    return querySub(a, b + 1, 0, 0, n);
  }
};


int main(void){
  int n;
  cin >> n;
  VL a(n), b(n);
  REP(i, 0, n) {
    cin >> a[i] >> b[i];
  }
  SegTree<ll, plus<ll> > st(n, plus<ll>(), 0);
  REP(i, 0, n) {
    st.update(i, a[i] - (i >= 1 ? a[i - 1] : 0));
  }
  ll cnt = 0;
  for (int i = n - 1; i >= 0; --i) {
    ll cur = st.query(0, i);
    ll aug = (b[i] - cur % b[i]) % b[i];
    st.update(0, st.query(0, 0) + aug);
    cnt += aug;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3840
# -*- coding: utf-8 -*-
import heapq

a,b,c = map(int, input().split())
l = [a,b,c]
l2 = heapq.nsmallest(3, l)
if (l2[0] + l2[1]) == max(l):
  print('Yes')
else:
  print('No')


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for (int i = a; i < (int)b; ++i)
#define rrep(i, n) for (int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	int l, r, d;
	cin >> l >> r >> d;
	cout << r / d - (l - 1) / d << endl;
    
    return 0;
}



Measured memory_bytes: 3436
# coding: utf-8
# Here your code !
N=int(input())
b=input()
c=b.split(" ")
d=map(int,c)
a=list(d)
X=sum(a)
ans=[]
Y=0
for i in range(N-1):
#    A=abs(X-2*sum(a[0:i]))
    Y=Y+a[i]
    B=abs(X-2*Y)
    ans.append(B)
ans1=min(ans)
print(ans1)

Measured memory_bytes: 33880
import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int l = sc.nextInt();

        long[][] a = new long[n][m];
        long[][] b = new long[m][l];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < l; j++) {
                b[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
                long c = 0;
                for (int k = 0; k < m; k++) {
                    c += a[i][k] * b[k][j];
                }
                System.out.print(c);
                if (j == l - 1) {
                    System.out.println("");
                } else {
                    System.out.print(" ");
                }
            }
        }

    }

}


Measured memory_bytes: 54356
fn pop_count(mut n: usize) -> usize {
    let mut res = 0;
    while n > 0 {
        res += 1 & n;
        n >>= 1;
    }
    res
}

fn solve() {
    let (n, w): (usize, usize) = (read::<usize>(), read::<usize>());
    let mut vw = vec![];
    for i in 0..n {
        let (v, w): (usize, usize) = (read::<usize>(), read::<usize>());
        vw.push((v, w));
    }
    let mut dp = vec![vec![0; n + 1]; w + 1];
    for i in 1..n + 1 {
        for w in 0..w + 1 {
            if let Some(beforew) = w.checked_sub(vw[i - 1].1) {
                dp[w][i] = max(dp[beforew][i - 1] + vw[i - 1].0, dp[w][i - 1]);
            } else {
                dp[w][i] = dp[w][i - 1];
            }
        }
    }
    let mut res = 0;
    for k in 0..w + 1 {
        res = max(res, dp[k][n]);
    }
    println!("{}", res);
}

fn main() {
    let stack_size = 104_857_600;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min, Ord, Ordering, PartialOrd};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;
const INF: usize = 100_000_000_000;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========



Measured memory_bytes: 17220
#include<iostream>
#include<math.h>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main(){
	int n,m;
	while(cin>>n>>m){
		if(n==0 && m==0)break;
		int ta[110]={},ha[110]={},t=0,h=0,s,f=0;
		for(int i=0;i<n;i++){
			cin>>ta[i];
			t+=ta[i];
		}
		for(int i=0;i<m;i++){
			cin>>ha[i];
			h+=ha[i];
		}
		sort(ta,ta+(n-1));
		sort(ha,ha+(m-1));
		s=max(t,h)-min(t,h);
		if(s%2!=0){
			cout<<-1<<endl;
		}
		else{
			s=s/2;
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++){
					if((t>=h && ta[i]-ha[j]==s) || (t<=h && ha[j]-ta[i]==s)){
						cout<<ta[i]<<" "<<ha[j]<<endl;
						f=1;
						j=m+1;
						i=n+1;
					}
				}
			}
			if(f==0){
				cout<<-1<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1180
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

// 

public class ABC144_A // ←Class名変更！！    Program
{
    public static void Main()
    {
        var n = Ria();

        var b = true;
        b = b && n[0] <= 9;
        b = b && 1<=n[0];
        b = b && n[1] <= 9;
        b = b && 1 <= n[1];


        var result = -1;
        if (b)
        {
            result = n[0] * n[1];
        }

        WriteLine($"{result}");
        return;

    } // Main

    public static string Rs() { return ReadLine(); }
    public static char Rc() { var c = ReadLine(); return c[0]; }    //最初の1文字だけ返す
    public static int Ri() { return int.Parse(ReadLine()); }
    public static long Rl() { return long.Parse(ReadLine()); }
    public static char[] Rca() { return ReadLine().ToCharArray(); }
    public static int[] Ria() { return Array.ConvertAll(ReadLine().Split(' '), int.Parse); }
    public static long[] Rla() { return Array.ConvertAll(ReadLine().Split(' '), long.Parse); }
} // Class


Measured memory_bytes: 13140
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
a,b ,c = rrm()
k = rri()
def solve(a, b,c, k):
    while k:
        if a<b<c:
            return True
        if b<=a:
            b*=2
            k-=1
        elif c<=b:
            c*=2
            k-=1
    return a<b<c
ans = solve(a, b,c ,k)
if ans:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 64984
from fractions import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)

n=int(input())
a=list(map(int,input().split()))
t=0
for i,aa in enumerate(a):
    if i==0:
        t=a[0]
        continue
    t=lcm(t,aa)

mod=t-1
ans=0
for aa in a:
    ans+=mod%aa
print(ans)



Measured memory_bytes: 5348
import sys

k = 0

while k == 0:
    r = raw_input()
    H, W = r.split()
    H = int(H)
    W = int(W)
    
    if H == 0 and W == 0:
        k = 1
    else:
        for j in range(H):
            for i in range(W):
                if i == 0 or i == W-1 or j == 0 or j == H-1:
                    sys.stdout.write("#")
                else:
                    sys.stdout.write(".")
            print("")
        print("")

Measured memory_bytes: 6384
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  ll x = 4LL*a*b;
  ll y = c-(a+b);
  if(y < 0){
    cout << "No" << endl;
    return 0;
  }
  y *= y;
  if(x < y){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256