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

using namespace std;

int a[1234567];

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  int g = 0;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    g = __gcd(g, a[i]);
    mx = max(mx, a[i]);
  }
  if (k <= mx && k % g == 0) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
typedef struct{
        char name[11];
        int time;
}process;
typedef struct node{
        process data;
        struct node *next;
        struct node *prev;
}queue;
queue *head = NULL;
queue *last = NULL;
void Push_back(process);
process Pop_front(void);
main()
{
        int n, q, count = 0;
        process pro;
        scanf("%d %d%*c", &n, &q);
                while(n--){
                        scanf("%s %d%*c", pro.name, &pro.time);
                        Push_back(pro);
                }
                while(last != NULL){
                        pro = Pop_front();
                        if(pro.time > q){
                                pro.time -= q;
                                Push_back(pro);
                                count += q;
                        }else{
                                count += pro.time;
                                printf("%s %d\n", pro.name, count);
                        }
                }
}
void Push_back(process data)
{
        queue *p;
        if((p = (queue*)malloc(sizeof(queue))) == NULL){
                fprintf(stderr, "Memory cannot allocate\n");
                exit(0);
        }
        p -> data = data;
        p -> next = NULL;
        p -> prev = last;
        last = p;
        if(head == NULL){
                head = p;
        }else{
                        p -> prev -> next = p;
                }
}
process Pop_front(void)
{
        process pop_data;
        queue *p = head;
        if(last == NULL){
                        exit(1);
        }
        pop_data = head -> data;
        if(head -> next== NULL){
                last = NULL;
        }else{
                head -> next -> prev = NULL;
        }
        p = head;
                head = head -> next;
        //free(p);
        return pop_data;
}

Measured memory_bytes: 10560
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define ld long double
#define pb push_back
#define pf push_front
#define dll deque<ll>
#define vll vector<ll>
#define pll pair<ll,ll>
#define mapll map<ll,ll>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define deb(x) cout<<x
using namespace std;
void swap(auto*,auto*);
ld dist(ll x1,ll y1,ll x2,ll y2)
{
	return (ld)sqrt((ll)pow(x1-x2,2)+(ll)pow(y1-y2,2));
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n; cin>>n; ll d; cin>>d; ll c=0;
    for(ll i=0;i<n;i++)
    {
    	ll x,y; cin>>x>>y; if(dist(x,y,0,0)<=d) c++;
    }
    cout<<c<<endl;
}
void swap(auto &a,auto &b)
{
    auto temp=a; a=b; b=temp;
}

Measured memory_bytes: 3696
n = int(input())
#a, b = map(int,input().split())
l = list(map(int,input().split()))
#l = [list(map(int,input().split())) for i in range(n)]

import itertools
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a,b,c=l[i],l[j],l[k]
            if len(set([a,b,c]))==3:
                if a+b>c and b+c>a and a+c > b:
                    ans+=1
print(ans)



Measured memory_bytes: 9192
#include<bits/stdc++.h>
using namespace std;
 
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " " << a.second; }
template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; }
template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; }
 
#define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)
#define ALL(v) (v).begin(), (v).end()
#define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());}
#define fr first
#define sc second
 
typedef pair< int , int > Pi;
typedef pair< int , Pi > Pii;

typedef long long int64;
const int INF = 1 << 30;

int main(){
  int C, D, W, X;
  vector< vector< int > > E, F;
  vector< vector< vector< int > > > dp;

  while(cin >> C >> D >> W >> X, C){
    E  = vector< vector< int > >( C, vector< int >(D));
    F  = vector< vector< int > >( C, vector< int >(D));
    dp = vector< vector< vector< int > > >
      ( D + 1, vector< vector< int > >(W + 1, vector< int >( X + 1, 0)));

    cin >> E;
    cin >> F;


    for(int i = 0; i < D; i++) {
      for(int j = 0; j <= X; j++) {
        for(int k = 0; k < C; k++) {
          if(E[k][i] == 0) continue;
          for(int l = W; l >= F[k][i]; l--) {
            // 複数回ライブをやる
            if(j > 0) {
              int value = 0, futan = 0;
              for(int m = k; m >= 0; m--) {
                if(E[m][i] == 0) break;
                value += E[m][i]; futan += F[m][i];
                if(l - futan < 0) break;
                dp[i + 1][l - futan][j - 1] = max( dp[i + 1][l - futan][j - 1], dp[i][l][j] + value);
              }
            }
            // 一回だけ
            dp[i + 1][l - F[k][i]][j] = max( dp[i + 1][l - F[k][i]][j], dp[i][l][j] + E[k][i]);
          }
        }
      }
      for(int j = 0; j <= W; j++) {
        for(int k = 0; k <= X; k++){
          dp[i + 1][j][k] = max( dp[i + 1][j][k], dp[i][j][k]);
        }
      }
    }

    int ret = 0;
    for(int j = 0; j <= W; j++){
      for(int k = 0; k <= X; k++){
        ret = max( ret, dp[D][j][k]);
      }
    }
    cout << ret << endl;
  }
}

Measured memory_bytes: 1420
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

using namespace std;
using P = pair<int, int>;

long long MOD = 1000000007;
long long dp[100005][4];

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

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

	vector<P>ab(M);
	for (int i = 0; i < M;++i) {
		cin >> ab[i].first >> ab[i].second;
	}
	sort(ab.begin(),ab.end(),compare_by_b);

	vector<int>place;
	for (int i = 0; i < M;++i) {
		if (place.empty() || !(ab[i].first <= place.back() && place.back() < ab[i].second)) {
			place.push_back(ab[i].second - 1);
		}
	}

	cout << place.size() << endl;
}


Measured memory_bytes: 1024
r, c = map(int, input().split())

total = 0
c_sum = [0 for i in range(c)]
for i in range(r):
    e = list(map(int, input().split()))
    total += sum(e)
    r_sum = 0
    for j in range(c):
        print(e[j], end=' ')
        r_sum += e[j]
        c_sum[j] += e[j]
    print(r_sum)
for i in range(c):
    print(c_sum[i], end=' ')
print(total)



Measured memory_bytes: 5632
a, b = map(int, input().split())
s = input()

x = s[:a].isdecimal()
if s[a] == "-":
  y = True
else:
  y = False
z = s[a+1:].isdecimal()

if x and y and z == True:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9208
/*ex5_3
  kt125 */

#include<stdio.h>
#define SIZE 100

int main(void){
    int height, width, //縦、横
        count, //'.'をカウントする変数
        i=0, j=0, k=0, //カウンタ変数
        row_del_num, //消去する行の数
        col_del_num, //消去する列の数
        height_ans, //答えとなる配列の縦の長さ
        width_ans, //答えをなる配列の横の長さ
    	col_del[SIZE], //消去する列の番号を記憶する配列
        row_del[SIZE];  //消去する行の番号を記憶する配列
  
    char board[SIZE][SIZE], //与えられたマス目の配列
         ans_row[SIZE * SIZE], //答えとなるマス目の文字を一列に並べた配列
    	 ans[SIZE][SIZE];  //答えとなる配列
  
    scanf("%d %d", &height, &width);

    for(i=0; i < height;i++){
        for (j=0; j < width; j++){
            scanf(" %c", &board[i][j]);
        }  
    }

    for(i=0; i < height; i++){
        for(j=0; j < width; j++){
            if(board[i][j]== '.'){
                count++;
            }
        }
        if (count == width){ //i行が全て'.'だった場合
            row_del[k] = i; //配列の最初から順に用いるためにkを使う
            k++;
        }
        count = 0; //各行ごとにリセット
    }  
    row_del_num = k; //消去する行の数

    k = 0; //リセット

    for(i=0; i < width; i++){
        for(j=0; j < height; j++){
            if(board[j][i]== '.'){
                count++;
            }
        }
        if (count == height){ //i列が全て'.'だった場合
            col_del[k] = i;
            k++;
        }
      	count = 0; //各列ごとにリセット
    } 

  	col_del_num = k; //消去する列の数
    
    for(i=0; i < row_del_num; i++){
        for (j=0; j < width; j++){
            board[row_del[i]][j] = 'o'; //消去する行の文字を'o'に置き換える
        }
    }
    for(i=0; i < col_del_num; i++){
        for (j=0; j < height; j++){
            board[j][col_del[i]] = 'o'; //消去する列の文字を'o'に置き換える
        }
    }
  	k = 0; // リセット
  	
    for(i=0; i < height; i++){
        for(j=0; j < width; j++){
            if (board[i][j] != 'o'){ //'o'を飛ばす
                ans_row[k] = board[i][j];
              	k++;
            }
        }
    }

  	height_ans = height - row_del_num; //答えとなる配列の縦の長さ
  	width_ans = width - col_del_num; //答えとなる配列の横の長さ

    for(i=0; i < height_ans; i++){
        for(j=0; j < width_ans;j++){
            ans[i][j] = ans_row[j + i * (width_ans)]; //一次元の配列をマス目に合うように二次元に直す
        }
    }
  
	for(i=0; i < height_ans;i++){
        for (j=0; j < width_ans; j++){
            printf("%c", ans[i][j]); //マス目をprint
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 256
#解説解答
S = input()
T = input()
ls = len(S)
lt = len(T)
s1 = [[] for _ in range(26)]
s2 = [[] for _ in range(26)]
for i in range(ls):
  s1[ord(S[i])-97].append(i)
  s2[ord(S[i])-97].append(i+ls)
s = [[] for _ in range(26)]
for k in range(26):
  s[k] = s1[k] + s2[k]
#print(s)
ans = 0
mans = 0
import bisect
for j in range(lt):
  now = ord(T[j])-97
  if s[now] == []:
    print(-1)
    break
  here = bisect.bisect_left(s[now],mans)
  ans = ans - mans + s[now][here] + 1
  mans = (s[now][here] + 1) % ls
  #print(now,here,s[now],s[now][here],ans,mans)
else:
  print(ans)

Measured memory_bytes: 13300
import numpy as np

H, W = map(int, input().split())
masu = [input() for i in range(H)]
#temp = [list(input().replace("#","0").replace(".","1")) for i in range(H)]
#masu = [[int(temp[i][j]) for j in range(W)] for i in range(H)]

dp = np.zeros((H, W))
if masu[0][0] == "#":
    dp[0][0] = 1

for i in range(0,H):
    for j in range(0,W):
        if i == 0:
            a = 100000
        else:
            if masu[i][j] == "#" and masu[i-1][j] == ".":
                a = dp[i-1][j] + 1
            else:
                a = dp[i-1][j]
        if j == 0:
            b = 100000
        else:
            if masu[i][j] == "#" and masu[i][j-1] == ".":
                b = dp[i][j-1] + 1
            else:
                b = dp[i][j-1]
        if a != 100000 or b != 100000:
            dp[i][j] = min([a, b])
print(int(dp[H-1][W-1]))


Measured memory_bytes: 12512
#include <stdio.h>

int main() {
  int N;
  scanf("%d", &N);

  int* A = new int[N];
  for(int i=0;i<N;i++) {
    scanf("%d", &A[i]);
  }

  int max = 0;
  for(int i=0;i<N-1;i++) {
    for(int t=i+1;t<N;t++) {
      int tmp = A[i] - A[t];
      tmp = tmp >= 0 ? tmp : -tmp;
      if(tmp > max) max = tmp;
    }
  }

  printf("%d\n", max);


  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] s){
  	Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    
    if(a*b%2==1)
      System.out.println("Odd");
    else
      System.out.println("Even");
  }
}


Measured memory_bytes: 21588
# coding: utf-8

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

output = 0
for i in range(N):
    output += B[A[i]-1]
    if i > 0 and A[i] == A[i-1]+1:
        output += C[A[i-1]-1]

print(output)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,m,a,c,b,minn,pos;
    long long int arr[50][2],a1[50][2];
    scanf("%lld" ,&n);
    scanf("%lld",&m);
    for(a=0;a<n;a++)
    {
        scanf("%lld",&arr[a][0]);
        scanf("%lld",&arr[a][1]);
    }
    for(a=0;a<m;a++)
    {
        scanf("%lld",&a1[a][0]);
        scanf("%lld",&a1[a][1]);
    }
    for(a=0;a<n;a++)
    {
        for(b=0;b<m;b++)
        {
            long long x,z;
            if(arr[a][0]>=a1[b][0])
                x=arr[a][0]-a1[b][0];
            else
                x=a1[b][0]-arr[a][0];

            if(arr[a][1]>=a1[b][1])
                z=arr[a][1]-a1[b][1];
            else
                z=a1[b][1]-arr[a][1];
            if(b==0)
            {
                minn=x+z;
                pos=b;
            }
            else
            {
                if(x+z<minn)
                {
                    minn=x+z;
                    pos=b;
                }
                else if(x+z==minn)
                {
                    long long int i,j;
                    if(a1[pos][0]<=a1[b][0])
                        i=pos;
                    else
                        i=b;
                    if(a1[pos][1]<=a1[b][1])
                        j=pos;
                    else
                        j=b;
                    if(a1[i][0]<=a1[j][1])
                        pos=i;
                    else
                        pos=j;
                }
            }

        }
        printf("%lld\n",pos+1);
    }

}

Measured memory_bytes: 256
/**
 * Title: D - Rain Flows into Dams
 * Url: https://atcoder.jp/contests/abc133/tasks/abc133_d
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

    int n; cin >> n;
    vector<ll> a(n), m(n);
    for(int i=0; i<n; i++) cin >> a[i];
    m[0] = a[0];
    for(int i=1; i<n; i++) {
        if(i%2==1) {
            m[0] -=a[i];
        } else {
            m[0] += a[i];
        }
    }
    
    for(int i=1; i<n; i++) {
        m[i] = 2*(a[i-1] - m[i-1]/2);
    }

    for(int i=0; i<n; i++) {
        if(i==n-1) {
            cout << m[i] << endl;
        } else {
            cout << m[i] << " ";
        }
    }

    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
#include <bitset>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

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

int main(){
    cin>>N;
    vector<string> s(N);
    vec t(N);
    rep(i,N)cin>>s[i]>>t[i];
    cin>>S;
    ll ans = 0;
    bool plus = false;
    rep(i,N){
        if(plus) ans += t[i];
        if(S == s[i]) plus = true;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
fn main() {
    let (n, a, b) = read_tuple::<usize>();

    let mut count = n / (a + b) * a;
    let rem = n % (a + b);

    if rem <= a {
        count += rem;
    } else {
        count += a;
    }
    println!("{:?}", count);
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}
fn read_tuple<T: std::str::FromStr + Copy>() -> (T, T, T) {
    let temp = read_vec();
    (temp[0], temp[1], temp[2])
}



Measured memory_bytes: 4352
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>

namespace adaptor = boost::adaptors;
using index_t = std::size_t;

void Main()
{
	int N;
	std::string str;
	std::cin >> N;
	std::cin >> str;
	int count = 0;
	for (auto x : boost::irange(0, 1000))
	{
		int index = 0;
		char pass[3];
		pass[0] = '0' + ((x / 100) % 10);
		pass[1] = '0' + ((x / 10) % 10);
		pass[2] = '0' + (x % 10);
		for (auto i : boost::irange(0, N))
		{
			if (pass[index] == str[i])
			{
				++index;
				if (index == 3)
				{
					++count;
					break;
				}
			}
		}
	}
	std::cout << count << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 384
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
#define debug cout<<"debug"<<endl;
using namespace std;
const int maxn=2e5+50;
char s[maxn];
int c[maxn],cnt[maxn],ok,n;
bool vis[maxn];
vector<int> loc[30];

int lowbit(int x){
	return x&(-x);
}

void add(int x,int d){
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i]+=d;
	}
}

int sum(int x){
	int ret=0;
	for(int i=x;i>0;i-=lowbit(i)){
		ret+=c[i];
	}
	return ret;
}

int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
		memset(c,0,sizeof(c));
		memset(cnt,0,sizeof(cnt));
		memset(vis,0,sizeof(vis));
		ok=0; 

		for(int i=1;i<=n;i++){
			cnt[s[i]-'a']++;
			loc[s[i]-'a'].push_back(i);
		}
		for(int i=0;i<26;i++){
			if(cnt[i]%2) ok++;
		}
		if(ok>1){
			printf("-1\n");
			return 0;
		}
		for(int i=1;i<=n+1;i++){
			add(i,1);
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			int c=s[i]-'a';
			int loc_right=loc[c].back();
			if(loc_right==i){
				ans+=(sum(n)-sum(loc_right))>>1;///当遍历到只有一个字母的时候 根据对称性得 
			}
			else{
				ans+=sum(n)-sum(loc_right);
			}
			loc[c].pop_back();
			add(i,-1); 
			add(loc_right,-1);
			vis[i]=vis[loc_right]=true;
		}
		printf("%lld\n",ans);
		//memset(s,0,sizeof(s));
	return 0;
}


Measured memory_bytes: 3576
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

W, H, N = inm()


def solve():
    xl = 0
    xr = W
    yb = 0
    yt = H
    for _ in range(N):
        x, y, a = inm()
        if a == 1:
            xl = min(max(xl, x), xr)
        elif a == 2:
            xr = max(min(xr, x), xl)
        elif a == 3:
            yb = min(max(yb, y), yt)
        else:
            assert a == 4
            yt = max(min(yt, y), yb)
    return (yt - yb) * (xr - xl)


print(solve())


Measured memory_bytes: 9152
# include <iostream>
# include <cstdio>
# include <algorithm>
# include <queue>
# include <vector>
# include <cstring>

using namespace std;

long long a[400000];
long long num[100];
long long ans = 0;
const long long mod = 1e9+7;
int main(void){
    // freopen("aaa.in","r",stdin);
    long long N;
    scanf("%lld",&N);
    for (int i=1;i<=N;i++){
        scanf("%lld",&a[i]);
        for (long long j=0;j<=60;j++)
        if (((long long)1<<j)&a[i]) num[j]++;
    }
    // cout<<num[50]<<endl;
    long long temp = 1;
    for (int i=0;i<=60;i++)
    {
        ans+=(num[i]*(N-num[i]))%mod*temp;
        // cout<<num[i]<<" "<<i<<endl;
        ans%=mod;
        temp<<=1;
        temp%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}



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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int d, t, s;
  cin >> d >> t >> s;
  
  if (t * s >= d) cout << "Yes\n";
  else cout << "No\n";
}

Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {

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

		StringBuffer line = new StringBuffer(sc.nextLine());
		for (int i = 0; i < line.length(); i++) {
			char ch = line.charAt(i);
			if (ch >= 'a' && ch <= 'z') {
				ch += 'A' - 'a';
				line.setCharAt(i, ch);
			} else if (ch >= 'A' && ch <= 'Z') {
				ch -= 'A' - 'a';
				line.setCharAt(i, ch);
			}
		}
		
		System.out.println(line);
		
		sc.close();
	}
}

Measured memory_bytes: 17144
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	
	int csum = 0, ans = 0;
	int N, P;
	string S;
	vector<int> con;
	
	cin>>N>>P;
	cin>>S;

	if(10%P){
		con.resize(P);
	
		con[0] = 1;
	
		for(int i = S.size()-1, ten = 1 % P; i >= 0; i--){
			csum = csum + ten * (S[i] - '0') % P;
			csum %= P;
			
			ans += con[csum];
			
			con[csum]++;
			ten *= 10;
			ten %= P;
		}
	} else{
		for(int i = 0; i < S.size(); i++){
			if((S[i] - '0') % P == 0) {
				ans += i + 1;
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int INF = 0x3f3f3f3f;
const int N = 100000 + 5;
bool is_palindrome(string str) {
    int length = str.length();
    for (int i = 0; i < length / 2; ++i)
        if (str[i] != str[length - i - 1])
            return false;
    return true;
};
int main()
{
	string s;
	cin >> s;
	int len = s.length();
	string s1 = s.substr(0,len/2);
	string s2 = s.substr(len/2+1,len/2);
	if(s1 != s2){
		cout << "No" << endl;
	}
	else{
		if(is_palindrome(s1)){
			cout << "Yes" << endl;
		}
		else
			cout << "No" << endl;
	}
    return 0;
}

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

int n, pos;
vector<int> pre, in, post;

void rec(int left, int right) {
  if ( left >= right ) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(left, m);
  rec(m + 1, right);
  post.push_back(root);
}

void solve() {
  pos = 0;
  rec(0, pre.size());
  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << post[i];
  }
  cout << endl;
}

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

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    pre.push_back(k);
  }

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    in.push_back(k);
  }

  solve();

  return 0;
}

Measured memory_bytes: 3112
//y=Axの行列Aを最適化するプログラム1
#include <iostream>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <sstream>
#include <vector>
#include <map>
#include <fstream>
using namespace std;


int main()
{
	int a, b, c;

	cin >> a >> b >> c;

	int sum1 = 0, sum2 = 0;

	if ((a + b) == c) {
		cout << "Yes" << endl;
	}
	else if(a == (b + c)){
		cout << "Yes" << endl;
	}
	else if (b == (a + c)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  vector<int> v(n),s(n+1);
  s[0]=0;
  for(int i=0;i<n;i++){
    cin >> v[i];
    s[i+1]=s[i]+v[i];
  }
  int m=min(n,k);
  int ans=0;
  for(int i=0;i<=m;i++){
    for(int j=0;j<=m-i;j++){
      int sum=s[i]+s[n]-s[n-j];
      vector<int> a;
      for(int u=0;u<i;u++){
        if(v[u]<0){
          a.push_back(v[u]);
        }
      }
      for(int u=n-1;u>n-1-j;u--){
        if(v[u]<0){
          a.push_back(v[u]);
        }
      }
      sort(a.begin(),a.end());
      int x=a.size();
      for(int u=0;u<min(x,k-i-j);u++){
        sum-=a[u];
      }
      ans=max(ans,sum);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[100005];int n;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d",&a[i].first,&a[i].second);
		a[i].first+=a[i].second;
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	long long ans=0;
	for (int i=1;i<=n;i++)
		if (i&1) ans+=a[i].first-a[i].second;else ans-=a[i].second;
	printf("%lld\n",ans);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vdouble = vector<double>;
using vstr = vector<string>;
typedef pair<int,int> P;
int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
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; }
const ll INF = 1LL << 60;
const ll mod = 1000000007;

string s,t;

ll dp[3100][3100]={0};//dp[i+1][j+1]:=sのi文字目までとtのj文字目まででのLCSの長さ

int main(){
	//乱数srand((unsigned)time(NULL));
	//入力
	cin>>s>>t;
	
	//dpテーブル埋め
	for(int i=0; i<s.size(); i++){
		for(int j=0; j<t.size(); j++){
			if(s[i]==t[j]) chmax(dp[i+1][j+1],dp[i][j]+1);
			chmax(dp[i+1][j+1],dp[i+1][j]);
			chmax(dp[i+1][j+1],dp[i][j+1]);
		}
	}
	
	//復元
	string res="";
	int i = (int)s.size(), j= (int)t.size();
	while(i>0&&j>0)
	{
		if(dp[i][j]==dp[i-1][j]){
			i--;
		}
		else if(dp[i][j]==dp[i][j-1]){
			j--;
		}
		else{
			res=s[i-1]+res;
			i--;j--;
		}
	}
	cout<<res<<endl;
}   

Measured memory_bytes: 73984
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e6+3)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
vector<int>topo;
vector<bool>vis(100005,0);
void dfs(int v,vii &adj)
{
	vis[v] = 1;
	for(int x:adj[v]){
		if(!vis[x])dfs(x,adj);
	}
	topo.pb(v);
}
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	vii in(n),out(n);
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u;
		v--;u--;
		in[v].pb(u);
		out[u].pb(v);
	}
	for(int i=0;i<n;i++)if(!vis[i])dfs(i,in);
	reverse(all(topo));
	vector<ll>dp(n,0);
	for(int i=0;i<n;i++)
	{
		for(int x:out[topo[i]]){
			dp[topo[i]] = max(dp[topo[i]],dp[x]+1);
		}
	}
	ll ans = 0;
	for(int i=0;i<n;i++)ans = max(ans,dp[i]);
	cout<<ans;
}

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

int main(){
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(i <  b && j <  a) cout << 0;
            if(i <  b && j >= a) cout << 1;
            if(i >= b && j <  a) cout << 1;
            if(i >= b && j >= a) cout << 0;
        }
        cout << endl;
    }
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  
  int a = n % 10;
  n = n / 10;
  int b = n % 10;
  n = n / 10;
  int c = n % 10;
  
  int ans = a + b + c;
  cout << ans;
}


Measured memory_bytes: 3620
<?php

fscanf(STDIN, "%d%d%d%d", $a,$b,$c,$d);
// $nums = explode(' ', trim(fgets(STDIN)));

$max = -10**18;

if ($max < $a * $c){
    $max = $a * $c;
}

if ($max < $a * $d){
    $max = $a * $d;
}

if ($max < $b * $c){
    $max = $b * $c;
}

if ($max < $b * $d){
    $max = $b * $d;
}

echo $max;


Measured memory_bytes: 16196
import GHC.Integer.GMP.Internals;main=interact$show.f.map read.words;f[x,y]|(s,0)<-divMod(2*y-x)3,(t,0)<-divMod(2*x-y)3,s>=0,t>=0=g(s+t)%recipModInteger(g s%g t)m|0<1=0;g x=foldl(%)1[1..x];x%y=rem(x*y)m;m=10^9+7

Measured memory_bytes: 81532
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramC
    {
        static void Main()
        {
            long l = NextLong, r = NextLong;

            if (r - l >= 2018)
            {
                System.Console.WriteLine(0);
                return;
            }

            long min = int.MaxValue;

            for (long i = l; i < r; i++)
            {
                for (long j = i + 1; j <= r; j++)
                {
                    min = Math.Min(min, i * j % 2019);
                }
            }

            System.Console.WriteLine(min);
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


Measured memory_bytes: 13268
n = int(input())
x_str = input().split()
xs = [int(c) for c in x_str]

xs_len = len(xs)
center = (xs_len - 1)//2

c_xs = xs[:]
c_xs.sort()

[print(c_xs[center+1] if x <= c_xs[center] else c_xs[center]) for x in xs]


Measured memory_bytes: 31136
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define quickIO()	{cin.tie(0);	cout.sync_with_stdio(false);}
#define reach(i,a)	for(auto i:a)
#define rep(i,n)	for(int i=0;i<(int)n;i++)
#define REP(i,n)	for(int i=0;i<=(int)n;i++)
#define srep(i,a,n)	for(int i=a;i<(int)n;i++)
#define SREP(i,a,n)	for(int i=a;i<=(int)n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
int bitcnt(ll x) {
	x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);
	x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);
	x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);
	x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);
	x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);
	x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);
	return x;
}
int bitcnt(int x) {
	x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
	x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
	x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
	x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
	x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
	return x;
}
ll sqrt(ll x) {
	ll left = 0, right = x;
	rep(i, 100) {
		ll mid = (left + right) >> 1;
		if (mid*mid <= x)	left = mid;
		else	right = mid;
	}
	return left;
}
ll gcd(ll a, ll b) {
	return a%b == 0 ? b : gcd(b, a%b);
}
#define debug(x)	printf("Case #%d: ", x)
#define DEBUG 0
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 1e-15;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };

// 解説した通りの再帰関数解法。
// 実装し直して気付きましたが、1文字目の手前にも+を入れるか判定をしています。
// しかし、これで結果は変わらないので、最後に÷2している感じです。

string s;

ll solve(ll decided, ll left, int idx) {
	if (idx == s.size()) {
		return decided + left;
	}
	// 手前に+を差し込んだ時
	ll ret1 = solve(decided + left, s[idx] - '0', idx + 1);
	// 差し込まない時
	ll ret2 = solve(decided, left * 10 + s[idx] - '0', idx + 1);

	return ret1 + ret2;
}

int main() {
	cin >> s;
	cout << solve(0, 0, 0) / 2 << endl;
	return 0;
}

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

ll dp[110][110];

int main(int argc, char **argv)
{
	ll v, e; cin >> v >> e;

	for (ll i = 0; i < v; ++i) for (ll j = 0; j < v; ++j) dp[i][j] = (i!=j)*INF;

	for (ll i = 0; i < e; ++i)
	{
		ll s, t, d; cin >> s >> t >> d;
		dp[s][t] = d;
	}

	for (ll via = 0; via < v; ++via)
		for (ll s = 0; s < v; ++s)
			for (ll g = 0; g < v; ++g)
				dp[s][g] = min(dp[s][via] + dp[via][g], dp[s][g]);

	for (ll i = 0; i < v; ++i)
	{
		if (dp[i][i] < 0)
		{
			std::cout << "NEGATIVE CYCLE" << std::endl;
			return 0;
		}
	}

	for (ll i = 0; i < v; ++i)
	{
		for (ll j = 0; j < v; ++j)
		{
			if (j) std::cout << " ";
			if (dp[i][j]*2 > INF)
				std::cout << "INF";
			else
				std::cout << dp[i][j];
		}
		std::cout << std::endl;
	}
	
}



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

int main(){
  string S,T;
  cin >> S >> T;
  T=T.substr(0,T.size()-1);
  if(S==T){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3632
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
int a[100001];
int main()
{
	priority_queue<int,vector<int>,greater<int> > q;
	int n,x; 
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		q.push(x);
	}
	while(q.size()>1)
	{
		int ans=0;
		int z=q.top();
		q.pop(); 
		while(!q.empty())
		{
			int k=q.top();
			q.pop();
			if(k%z!=0) a[ans++]=k%z;
		}
		q.push(z);
		for(int i=0;i<ans;i++)
			q.push(a[i]);
	} 
	printf("%d",q.top()); 
}


Measured memory_bytes: 1144
#include<bits//stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
typedef long double ld;
ll n, m, x = 0, y,z,w,h, sum= 0, ans = 0;ld s = 0;
int main() {
	cin >> n; vector<pair<int,int>> a(n);vector<int> b(n);
	rep(i, n) {cin >> x >> y;a[i] = { x,y };b[i] = i;}
	do {
		rep(i, n - 1) {
			s += sqrt(pow(a[b[i]].first - a[b[i + 1]].first, 2) + pow(a[b[i]].second - a[b[i + 1]].second, 2));
		}sum++;
	} while (next_permutation(ALL(b)));
	cout << fixed << setprecision(10) << (ld)s / sum << endl;
}

Measured memory_bytes: 3852
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const string MINUSINF = "-";

void chmax(string &a, string b) {
  if (a == MINUSINF) { a = b; }
  else if (a.size() < b.size()) { a = b; }
  else if (a.size() == b.size()) {
    if (a < b) { a = b; }
  }
}

long long match[10] = {2,5,5,4,5,6,3,7,6};
// dp[i] := マッチ棒をちょうどi本使って作れる数値の最大値
// dp[i+match[a]] = max(dp[i+match[a], dp[i]*10 + a) と遷移
string dp[10100];

int main() {
  int n, m;
  cin >> n >> m;

  vector<int> a(m);

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

  for (int i = 0; i < 10100; i++) { dp[i] = MINUSINF; }

  dp[0] = "";
  for (int i = 0; i <= n; i++) {
    if (dp[i] == MINUSINF) { continue; }
    for (auto aa : a) {
      chmax(dp[i+match[aa-1]], dp[i] + (char)('0' + aa));
    }
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 43776
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
ll n,x;
ll a[2222];
ll b[2222];
int main(void){
  cin >> n >> x;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    b[i] = a[i];
  }
  
  ll ans = 1LL<<60;
  for(int j = 0; j < n; j++){
    ll tmp = x*j;
    for(int i = 0; i < n; i++){
      b[i] = min(b[i],a[(i-j+n)%n]);
      tmp += b[i];
    }
    ans = min(ans,tmp);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#[test]
fn test_solve() {
    assert_eq!(solve("2 3 1\n1 1\n1 2\n2 2\n1 2\n"), "3\n");
    assert_eq!(solve("10 3 2\n1 5\n2 8\n7 10\n1 7\n3 10\n"), "1\n1\n");
    assert_eq!(solve("10 10 10\n1 6\n2 9\n4 5\n4 7\n4 7\n5 8\n6 6\n6 7\n7 9\n10 10\n1 8\n1 9\n1 10\n2 8\n2 9\n2 10\n3 8\n3 9\n3 10\n1 10\n"), "7\n9\n10\n6\n8\n9\n6\n7\n8\n10\n");
}

fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let n: usize = sc.read();
    let m: usize = sc.read();
    let q: usize = sc.read();
    let lr: Vec<(usize, usize)> = (0..m).map(|_| (sc.read(), sc.read())).collect();
    let ab: Vec<(usize, usize)> = (0..q).map(|_| (sc.read(), sc.read())).collect();
    
    let mut cnt = vec![vec![0; n]; n];
    for &(l, r) in &lr {
        cnt[l-1][r-1] += 1;
    }
    let mut sum = vec![vec![0; n+1]; n+1];
    for l in 0..n {
        for r in 0..n {
            sum[l+1][r+1] = cnt[l][r] + sum[l+1][r] + sum[l][r+1] - sum[l][r];
        }
    }

    let mut ret = String::new();
    use std::fmt::Write;

    for &(a, b) in &ab {
        let num = sum[b][b] + sum[a-1][a-1] - sum[a-1][b] - sum[b][a-1];
        writeln!(&mut ret, "{}", num).unwrap();
    }

    ret
}
fn main() {
    let mut buf = String::new();
    use std::io::{Read, Write};
    std::io::stdin().read_to_string(&mut buf).unwrap();
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };




void solve() {
    int N; cin >> N;
    vector<ll> a(N), b(N), c(N);
    rep(i, N) cin >> a[i] >> b[i];
    bool f = true;
    rep(i, N) if(a[i]%b[i]) f=false;
    if(f){
        cout << 0 << endl;
        return;
    }
    reverse(all(a)); reverse(all(b));
    rep(i, N) c[i] = b[i]-a[i]%b[i];
    rep(i, N-1){
        if(c[i] > c[i+1]){
            c[i+1] += ((c[i]-c[i+1]+b[i+1]-1)/b[i+1])*b[i+1];
        }
    }
    cout << c[N-1] << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 6656
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;


#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)
ll dp[200001];
ll seg[800005];
ll mod = 998244353;
ll merge(ll a, ll b) {
	return max(a, b);
}
void build(ll pos, ll l, ll r) {
	if(l > r) {
		return;
	}
	if(l == r) {
		seg[pos] = l;
		return;
	}
	ll mid = (l + r) / 2;
	build(2*pos + 1, l, mid);
	build(2*pos + 2, mid + 1, r);
	seg[pos] = merge(seg[2*pos + 1], seg[2*pos + 2]);
	return;
}
ll query(ll pos, ll l, ll r, ll l1, ll r1) {
	if(l > r || r1 < l || l1 > r) {
		return -1;
	}
	if(l1 <= l && r <= r1) {
		return seg[pos];
	}
	ll mid = (l + r) / 2;
	return(merge(query(2*pos + 1, l, mid, l1, r1), query(2*pos + 2, mid + 1, r, l1, r1)));
}
void update(ll pos, ll l, ll r, ll x, ll val) {
	if(l > r || x < l || x > r) {
		return;
	}
	if(l == r) {
		seg[pos] = val;
		return;
	}
	ll mid = (l + r) / 2;
	update(2*pos + 1, l, mid, x, val);
	update(2*pos + 2, mid + 1, r, x, val);
	seg[pos] = merge(seg[2*pos + 1], seg[2*pos + 2]);
	return;
}
int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, i;
    cin>>n;
    dp[n] = 1;
    vector<pair<ll, ll>> v(n);
    vector<ll> temp(n);
    build(0, 0, n);
    for(i = 0; i < n; i++) {
    	cin>>v[i].ff>>v[i].ss;
    	temp[i] = v[i].ff;
    }
    sort(all(v));
    sort(all(temp));
    for(i = n - 1; i >= 0; i--) {
    	ll ind = lower_bound(all(temp), v[i].ff + v[i].ss) - temp.begin();
    	// cout<<ind - 1<<"\n";
    	ll req = query(0, 0, n, i, ind - 1);
    	update(0, 0, n, i, req);
    	// cout<<req<<"\n";
    	if(req == i) {
    		dp[i] = (2 * dp[i + 1]) % mod;
    	} else {
    		dp[i] = (dp[i + 1] + dp[req + 1]) % mod;
    	}	
    	// cout<<
    }
    cout<<dp[0]<<"\n";
}

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

template<typename T> void drop(const T &x){cout<<x<<'\n';exit(0);}

void solve() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> x(n, vector<int>(d));
  for(int i=0; i<n; ++i) {
    for(int j=0; j<d; ++j) {
      cin >> x[i][j];
    }
  }

  int ans = 0;
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      int a = 0, b = 0;
      for(int k=0; k<d; ++k) {
        a += pow(x[i][k]-x[j][k], 2);
        b += pow(x[i][k]-x[j][k], 2);
      }
      if((int)sqrt(a) == sqrt(b)) ans++;
    }
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T=1;
  //cin >> T;
  while(T--) solve();

  return 0;
}


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

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

typedef long long ll;

using namespace std;

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

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

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

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

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

long long int n=1,cnt=0,ans=0,a[150][150],b,c,cmp,cmpp,data,m,h,w,x,y,xcmp=0,ycmp=0,sum=0;

string s;

vector<int> z;

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

       cin >> n;
       rep(i,2){
           rep(j,n){
               cin >> a[i][j];
           }
       }
        rep(i,n){
            cmp+=a[0][i];
            rrep(j,i,n){
                cmpp+=a[1][j];
            }
            ans=max(ans,cmp+cmpp);
            cmpp=0;
        }
        Cout(ans);
return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main()
{
    int n, i, p = 0;
    int x[101], y[101];
    double D[4] = {0};
     
    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d", &x[i]);
    for(i=0; i<n; i++) scanf("%d", &y[i]);
     
    do{
         
        if(p == 0){
            for(i=0; i<n; i++) D[0] = fmax(D[0], abs(x[i]-y[i]));
        }else{
            for(i=0; i<n; i++) D[p] += pow(abs(x[i]-y[i]), p);
            D[p] = pow(D[p], (1.0/(double)p));
            printf("%f\n", D[p]);
        }
         
        p++;
         
    }while(p<4);
     
     
    printf("%f\n", D[0]);
     
    return 0;
}
 

Measured memory_bytes: 700
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<math.h>
#include<vector> 
using namespace std;
int main()
{int a,b,x;
 cin>>a>>b>>x;
 if(a<=x && a+b>x)
 cout<<"YES"<<endl;
 else
 cout<<"NO"<<endl; 
 system("pause");
 return 0;
}

Measured memory_bytes: 504
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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 dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    ll ans=0;
    vector<ll> A(3*N);
    REP(i,3*N) cin>>A[i];
    VRSORT(A);
    for(int i=1;i<2*N;i+=2) ans+=A[i];
    cout<<ans<<endl;
}

Measured memory_bytes: 2560