akhauriyash/Code-Regression huggingface dataset:
from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == -1:
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Measured memory_bytes: 87260
//In the name of Allah
#include <bits/stdc++.h>
using namespace std;
#define MAX 100011
#define ll long long
#define endl '\n'
int a[MAX],dp[MAX];

int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,k;
	
	cin>>n>>k;
	for(int i = 0 ; i < n ; i++)cin>>a[i];
	
	memset(dp,127,sizeof dp);	
	dp[0] = 0;
	for(int i = 1;  i < n ; i++){
		for(int j = 1; j <= k ; j++){
			if(i - j >= 0)dp[i] = min(dp[i],dp[i-j] + abs(a[i] - a[i-j]));
		}
	}	
	cout<<dp[n-1];
	return 0; 
} 

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
long long int v[200005];
int asc(const void* a, const void* b)
{
	if (v[*(int*)a] > v[*(int*)b])return 1;
	if (v[*(int*)a] < v[*(int*)b])return -1;
	if (*(int*)a > * (int*)b)return 1;
	if (*(int*)a < *(int*)b)return -1;
	return 0;
}
int main()
{
	long long int n, k;
	scanf("%lld %lld", &n, &k);
	long long int i;
	long long int a[200005];
	for (i = 0; i < n; i++)
		scanf("%lld", &a[i]);
	long long int sum[200005];
	sum[0] = 0;
	for (i = 0; i < n; i++)
		sum[i + 1] = sum[i] + a[i];
	for (i = 0; i <= n; i++)
		v[i] = (sum[i] - i + n * k) % k;
	int c[200005];
	for (i = 0; i <= n; i++)
		c[i] = i;
	qsort(c, n + 1, sizeof(int), asc);
	long long int ans = 0;
	long long int min, mid, max;
	for (i = 0; i < n; i++)
	{
		min = i;
		max = n + 1;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (v[c[i]] != v[c[mid]])max = mid;
			else if (c[mid] - c[i] >= k)max = mid;
			else min = mid;
		}
		ans += min - i;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 6396
# 想定解法1

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)

AB.sort(reverse=True)
AB = AB[:K]

ABC = []
for ab in AB:
  for c in C:
    ABC.append(ab+c)

ABC.sort(reverse=True)
ABC = ABC[:K]

for ans in ABC:
  print(ans)


Measured memory_bytes: 148204
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int ans = 0;
    REP(i,n){
        int t;
        scanf("%d", &t);
        if (t < a || t >= b)
            ans++;
    }
    cout << ans << endl;
    return 0;
}


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



int main()
{
    int n;
    cin>>n;
    string h;
    cin>>h;
    int i=0;
    int j=h.length()-1;
    while(h[i]=='R')
    {
        i++;
    }
    while(h[j]=='W')
    {
        j--;
    }
    int c=0;
    while(i<j)
    {
        c++;
        i++;
        j--;
        while(h[i]=='R')
        {
            i++;
        }
        while(h[j]=='W')
        {
            j--;
        }
    }
    cout<<c<<endl;

}




















Measured memory_bytes: 3720
n = int(input())
table = [0]*(10**5)
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            table[x**2+y**2+z**2+x*y+y*z+z*x] += 1

for i in range(1, n+1):
    print(table[i])

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

#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>

using namespace std;


//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*int power(int a,int n)
{
    if(n == 1)return a%mod;
    if(n == 0)return 1;
    if(n&1)return ((a%mod)*(power((a*a)%mod,n>>1))%mod)%mod;
    return power((a*a)%mod,n>>1)%mod;
}
*/
const int md = 998244353;
int dp[100005][105],w[105],v[105];


signed main()
{
    showoff;
    int n,W;
    cin >> n >> W;
    FOR(i,1,n+1)
    cin >> w[i] >> v[i];
    FOR(i,1,100001){
        FOR(j,1,n+1){
        if(w[j] <= i){
        dp[i][j] = max(dp[i][j-1],v[j]+dp[i-w[j]][j-1]);
        }
        else dp[i][j] = dp[i][j-1];
      }
    }
    cout << dp[W][n] << "\n";
    return 0;
}


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

dp = [float("inf")] * (2 ** N)

dp[0] = 0

for i in range(M):

    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    key = 0

    for j in c:
        key += 2 ** (j-1)

    for j in range(2**N):
        if dp[j | key] > dp[j] + a:
            dp[j | key] = dp[j] + a

if dp[2 ** N - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** N - 1])

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

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

int ans;
map<int,VI> edge;
void dfs(int current, vector<bool>& used){
  if(used[current]) return;
  //cout << current << endl;
  used[current] = true;
  if(edge.find(current) != edge.end()){
    //cout << "hi" << endl;
    for(int to :edge[current]){
      dfs(to,used);
    }
  }else{
    ans++;
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  while(true){
    cin >>  n;
    if(n == 0) break;
    map<string,int> mp;

    int cnt = 0;
    edge.clear();
    rep(i,n){
      string s;
      cin >> s;
      int j = 0;

      // find key
      int x = 0;
      for(j = 0; j < s.size(); j++){
        if(s[j] == ':'){
          string key = s.substr(0,j);
          //cout << key << endl;
          if(mp.find(key) == mp.end()){
            mp[key] = cnt;
            x = cnt;
            cnt++;
          }else{
            x = mp[key];
          }
          break;
        }
      }

      int prev = j;
      for(;j < s.size(); j++){
        if(s[j] == ',' || s[j] == '.'){
          string tmp = s.substr(prev+1,j-prev-1);
          prev = j;
          if(mp.find(tmp) == mp.end()){
            //cout << "yi" << endl;
            mp[tmp] = cnt;
            edge[x].push_back(cnt);
            //cout << cnt << endl;
            cnt++;
          }else{
            edge[x].push_back(mp[tmp]);
          }

        }
      }


    }
    vector<bool> used(cnt+1,false);
    ans = 0;
    // for(auto z: edge){
    //   cout << z.first << ": ";
    //   for(int y: z.second) cout << y << " ";
    //   cout << endl;
    // }
    dfs(0,used);
    //cout << "ans" << endl;
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3300
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000+7;

//マクロ
//型エイリアス
using ll = long long;
using P=pair<long long,long long>;
using vl=vector<long long>;
//ショートカット
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,k,n) for(int i=k;i<n;i++)
#define all(v) v.begin(), v.end()
#define pb push_back
//入力
#define vin(v,N) for(int i=0;i<N;i++) cin>>v.at(i)
#define lin(n) long long n;cin>>n
#define vlin(v,N) vector<long long>v(N);for(long long i=0;i<N;i++)cin>>v.at(i)

//関数
//最大公約数
long long gcd(long long m,long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m,long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x,long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  lin(N);lin(M);
  vl box(N,1);
  vector<bool>p(N,false);
  p[0]=true;
  
  rep(i,M){
    lin(x);lin(y);
    box[x-1]--;box[y-1]++;
    if(p[x-1])
      p[y-1]=true;
    if(box[x-1]==0)
      p[x-1]=false;
  }
  
  ll res=0;
  
  rep(i,N){
    if(box[i]>0&&p[i])
      res++;
    //cout<<box[i]<<" "<<p[i]<<endl;
  }
  
  cout<<res;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>

int main() {
  int n;
  std::cin >> n;
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    int d1, d2;
    std::cin >> d1 >> d2;
    if (d1 == d2)
      cnt++;
    else
      cnt = 0;
    if (cnt == 3) {
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
}


Measured memory_bytes: 3104
#include <stdio.h>

int main(){
	int a[11],b,c,d,i,j;
	for(i=0;i<10;i++){
		scanf("%d",&a[i]);
	}
	a[10]=10001;
	for(j=0;j<100;j++){
	for(i=0;i<10;i++){
		if(a[i]>=a[i+1]){
			b=a[i];
			a[i]=a[i+1];
			a[i+1]=b;
		}
	}
	}
	printf("%d\n%d\n%d\n",a[9],a[8],a[7]);
	return 0;
}

Measured memory_bytes: 600
P = 998244353


nn = 200200

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P


def comb(a, b):
    return fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0


N, M, K = map(int, input().split())

if M == 1:
    if N - K == 1:
        print(1)
    else:
        print(0)
    exit(0)


t = pow(M-1, N-1, P)
m = pow(M-1, P-2, P)
ans = 0
for k in range(K+1):
    ans = (ans + t * comb(N-1, k)) % P
    t = t * m % P
print(ans * M % P)


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

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

	bitset<1100000000> bs;
	int	n;
	cin >> n;
	rep(i, n)
	{
		int	x;
		cin >> x;
		if (bs.test(x))
		{
			cout << "NO" << endl;
			return (0);
		}
		else
			bs.set(x);
	}
	cout << "YES" << endl;
}


Measured memory_bytes: 134528
#include<stdio.h>
 
 
int main()
{
    int i,j,a[3];
    for(i=0;i < 3;i++) scanf("%d",&a[i]);
 
    for (i = 0; i < 2; i++) {
        for (j = 2; j > i; j--) {
            if (a[j - 1] > a[j]) {
                int change = a[j];
                a[j] = a[j - 1];
                a[j-1] = change;
            }
        }
    }
    printf("%d %d %d\n",a[0],a[1],a[2]);
    return 0;
}

Measured memory_bytes: 1848
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

int main()
{
	double h = 0.1e5;
	int x, y;
	int num1 = 0, num2 = 0;
	scanf("%d %d", &x, &y);
	int a[3], b[3];
	for(int i = 0; ; i++) {
		a[i] = x % 10;
		x = x / 10;
		num1++;
		if(x == 0) break;
	}
	for(int i = 0; ; i++) {
		b[i] = y % 10;
		y = y / 10;
		num2++;
		if(y == 0) break;
	}
	int k1 = 0, k2 = 0;
	int m = 1;
	for(int i = 0; i < num1 + num2 - 1; i++) m = m*10;
	int z = m;
	for(int i = num1 - 1; i >= 0; i--) {
		k1 = k1 + a[i]*m;
		m = m / 10;
	}
	for(int i = num2-1; i >= 0; i--) {
		k1 = k1 + b[i]*m;
		m = m / 10;
	}
	for(int i = num2 - 1; i >= 0 ; i--) {
		k2 = k2 + b[i]*z;
		z = z / 10;
	}
	for(int i = num1 - 1; i >= 0; i--) {
		k2 = k2 + a[i]*z;
		z = z / 10;
	}
	if((int)sqrt(k1) == sqrt(k1) || (int)sqrt(k2) == k2) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 128
d,g=map(int,input().split())
g//=100
l=[]
ans=1000
for i in range(1,d+1):
  p,c=map(int,input().split())
  c//=100
  l+=[[p,c,i*p,i*p+c]]
for i in range(2**d):
  score=0
  a=0
  b=1
  c=0
  if not i:
    b=d
  while i:
    if i%2>0:
      score+=l[a][3]
      c+=l[a][0]
    else:
      b=a+1
    a+=1
    i//=2
  if score>=g:
    ans=min(ans,c)
  elif score+l[b-1][2]>=g:
    ans=min(ans,c+(g-score)//b+((g-score)%b>0))
print(ans)
      


Measured memory_bytes: 3064
//17
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

struct IS{
  int i,s;
  bool operator<(IS a)const{
    if(s!=a.s){
      return s>a.s;
    }else{
      return i<a.i;
    }
  }
};

int main(){
  for(int m;cin>>m,m;){
    IS sc[40];
    cin.ignore();
    for(int i=0;i<m;i++){
      string s;
      getline(cin,s);
      stringstream ss(s);
      int id;
      ss>>id;
      int a[21]={};
      for(int j=0;ss>>a[j];j++);
      int scr=0;
      int x=0;
      for(int f=1;;f++){
	if(f!=10){
	  if(a[x]==10){
	    scr+=10+a[x+1]+a[x+2];
	    x++;
	  }else if(a[x]+a[x+1]==10){
	    scr+=10+a[x+2];
	    x+=2;
	  }else{
	    scr+=a[x]+a[x+1];
	    x+=2;
	  }
	}else{
	  scr+=a[x]+a[x+1]+a[x+2];
	  break;
	}
      }
      IS cs={id,scr};
      sc[i]=cs;
    }
    sort(sc,sc+m);
    for(int i=0;i<m;i++){
      cout<<sc[i].i<<' '<<sc[i].s<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

const long double pi = acos(-1.0);

int32_t main(){
	int b, h, v;
	cin >> b >> h >> v;
	long double maxi = b*b*h;
	
	if(v > maxi/2){
		long double h_ = 2.0*(1.0*h*b*b-v)/(b*b);
		long double angle = atan(h_/b);
		cout << fixed << setprecision(10) << angle*180/pi << endl;
	}
	else{
		long double l = 0, r = b;
		long double ans;
		int iter = 0;
		while(l <= r){
			long double mid = (l+r)/2.0;
			long double vol = 0.5*h*b*mid;
			if(vol <= v){
				ans = mid;
				l = mid;
			}
			else
				r = mid;
			iter++;
			if(iter == 500)
				break;
		}
		long double angle = atan(1.0*h/ans);
		cout << fixed << setprecision(10) << angle*180/pi << endl;
	}
	
	
	

	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(){
int N,Y,SEN,GOSEN,MAN,BOOL=0,i,j,k;
  scanf("%d %d",&N,&Y);
  for(i=0;i<=N;i++)
  {
    for(j=0;j<=N;j++)
    {
      k=N-(i+j);
      if(k>=0&&i+j+k==N&&10000*k+5000*j+1000*i==Y)
      {
	   MAN=k;
	   GOSEN=j;
        SEN=i;
        BOOL=1;
     	break;
      }
    }    
   }
  
  if(BOOL==1){printf("%d %d %d",MAN,GOSEN,SEN);}
  else printf("-1 -1 -1");
return 0;
}

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

int main()
{
    //freopen("test.inp","r",stdin);
    long long n, a, b, res = 1e18, tmp = 1e18;
    cin >> n >> a >> b;
    if ((b-a)%2 == 0)

    {
        res = (b-a)/2;
        cout << res;
        return 0;
    }
    if (a-1 > n-b)
    {
        cout << n-b+1+(b-a)/2;
        return 0;
    }
    else
        cout << a+(b-a)/2;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,sum[N];
bool vis[N];
int main()
{
    scanf("%d%d",&n,&m);
    int ans=0,res=0;
    while(m--)
    {
        int x;char s[10];
        scanf("%d%s",&x,s);
        if(s[0]=='W')
        {
            if(!vis[x]) sum[x]++;
        }
        else
        {
            if(!vis[x]) ans++,res+=sum[x];
            vis[x]=true;
        }
    }
    printf("%d %d\n",ans,res);
}


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

int top, S[1000];

void push(int x) {
    S[++top] = x;
}

int pop() {
    top--;
    return S[top + 1];
}

int main() {
    int a, b;
    top = 0;
    char s[100];

    while (scanf("%s", s) != EOF) {
        if (s[0] == '+') {
            a = pop();
            b = pop();
            push(a + b);
        } else if (s[0] == '-') {
            b = pop();
            a = pop();
            push(a - b);
        } else if (s[0] == '*') {
            a = pop();
            b = pop();
            push(a * b);
        } else {
            push(atoi(s));
        }
    }

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

    return 0;
}



Measured memory_bytes: 2100
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var S = Console.ReadLine().ToCharArray();
        var ans = new int[S.Length];
        for (int i = 0; i < S.Length; ++i) ans[i] = 0;
        var start = 0;
        var currentR = 0;
        for (int i=0;i<S.Length;++i)
        {
            if (S[i] == 'L')
            {
                for (int j=start;j<=i;j++)
                {
                    if (S[j] == 'R')
                    {
                        var sa = (i - j) - 1;
                        if (sa % 2 != 1)
                        {
                            ans[i - 1]++;
                        }
                        else
                        {
                            ans[i]++;
                        }
                    }
                    else
                    {
                        var sa= (j - currentR) - 1;
                        if (sa % 2 == 1)
                        {
                            ans[currentR]++;
                        }
                        else
                        {
                            ans[currentR+1]++;
                        }
                    }
                }
                start = i+1;
            }
            else
            {
                currentR = i;
            }
        }
        for (int i=0;i<S.Length;++i)
        {
            Console.Write(ans[i]);
            if(i!=S.Length-1)Console.Write(' ');
        }
        Console.WriteLine();
    }

}


Measured memory_bytes: 13296
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,bin[200100],res,tot=1;
map<pair<int,int>,int>mpA,mpB;
signed main(){
	scanf("%lld",&n),bin[0]=1;
	for(int i=1,x,y;i<=n;i++){
		bin[i]=(bin[i-1]<<1)%mod,scanf("%lld%lld",&x,&y);
		if(!x&&!y){res++;continue;}
		if(!x){mpA[make_pair(0,1)]++;continue;}
		if(!y){mpB[make_pair(1,0)]++;continue;}
		int pm=1;
		if(x<=0)x=-x,y=-y;
		if(y<=0)pm=-1,y=-y;
		int tmp=__gcd(x,y);
		x/=tmp,y/=tmp;
		if(pm==1)mpA[make_pair(x,y)]++;
		else mpB[make_pair(x,y)]++;
	}
//	for(auto x:mpA)printf("(%lld,%lld):%lld\n",x.first.first,x.first.second,x.second);puts("");
//	for(auto x:mpB)printf("(%lld,%lld):%lld\n",x.first.first,x.first.second,x.second);puts("");
	for(auto x:mpA){
		int u=bin[x.second],v=0;
		pair<int,int>p=x.first;
		swap(p.first,p.second);
		if(mpB.find(p)!=mpB.end())v=bin[mpB[p]]-1,mpB.erase(mpB.find(p));
		(tot*=u+v)%=mod;
	}
	for(auto x:mpB)(tot*=bin[x.second])%=mod;
	printf("%lld\n",(tot+res-1+mod)%mod);
	return 0;
}

Measured memory_bytes: 17776
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> v(5);
    vector<int> d(5);
    int skip = 0;
    int maxi = 0;
    for(int i = 0; i < 5; i++)
    {
        cin >> v[i];
        d[i] = (v[i] % 10 != 0) * (10 - (v[i] % 10));
        if(d[i] > maxi)
        {
            maxi = d[i];
            skip = i;
        }
    }
    for(int i = 0; i < 5; i++) if(i != skip) v[i] += d[i];
    cout << accumulate(v.begin(), v.end(), 0);

    return 0;
}


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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define vvi             vector<vi>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define mod             1000000007
#define inf             1e18
#define deb(x)          cout << #x << "=" << x << '\n';
#define ps(x,y)         fixed<<setprecision(y)<<x
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

void solve() {

    int n, k, _min=inf;
    cin >> n >> k;
    vi h(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
    }

    vi dp(n+1);

    dp[n] = 0;

    for(int i = n-1; i>=1; i--) {
        _min=inf;
        for (int j = 1; j <= k&&i+j<=n; ++j) {
            _min=min(_min, dp[i+j]+abs(h[i]-h[i+j]));
        }
        
        dp[i] = _min;
    }

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

int32_t main() {
    FIO;
    int t = 1;
//    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 1792
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Console;
using static System.Math;
class Z { static void Main() => new K(); }
class K
{
	int F => int.Parse(Str);
	int[] G => Strs.Select(int.Parse).ToArray();
	string Str => ReadLine();
	string[] Strs => Str.Split();
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	long MaxSum(List<long> a) => a.Where(i => i >= 0).Sum();
	bool Good(List<long> a) => a.Any(i => i >= 0);
	void Solve()
	{
		var N = F;
		var a = G;
		var ev = new List<long>(N / 2);
		var od = new List<long>(N / 2);
		for (var i = 0; i < N; i++) if (i % 2 == 0) ev.Add(a[i]); else od.Add(a[i]);
		bool gev = Good(ev), god = Good(od);
		if (!gev&&!god)
		{
			var m = a.Max();
			int i = 0, j = N;
			while (a[i] != m) i++;
			WriteLine(a[i]);
			WriteLine(N - 1);
			for (var k = 0; k < i; k++) { WriteLine(1); j--; }
			while (j > 1) WriteLine(j--);
			return;
		}
		long mev = MaxSum(ev), mod = MaxSum(od);
		WriteLine(Max(mev, mod));
		var del = new List<int>();
		/*var st = new List<bool>();
		if (mev >= mod && gev) for (var i = 0; i < N; i++) st.Add(i % 2 == 0 && ev[i / 2] >= 0);
		else for (var i = 0; i < N; i++) st.Add(i % 2 == 1 && od[i / 2] >= 0);*/
		var l = new LinkedList<bool>();
		if (mev >= mod && gev) for (var i = 0; i < N; i++) l.AddLast(i % 2 == 0 && ev[i / 2] >= 0);
		else for (var i = 0; i < N; i++) l.AddLast(i % 2 == 1 && od[i / 2] >= 0);
		while (l.Count > 2)
		{
			var i = l.Count - 1;
			var n = l.Last;
			var pn = n.Previous.Previous;
			if (!n.Value) { del.Add(i); l.RemoveLast(); }
			else if (pn.Value)
			{
				del.Add(i - 1);
				l.RemoveLast();
				l.RemoveLast();
			}
			else
			{
				del.Add(i - 2);
				if (l.Count == 3) l.RemoveFirst();
				else
				{
					l.RemoveLast();
					l.RemoveLast();
					l.Last.Value = true;
				}
			}
		}
		//if (l.First.Value == l.Last.Value) throw new IOException();
		if (l.Count > 1) del.Add(l.First.Value ? 1 : 0);
		WriteLine(del.Count);
		foreach (var i in del) WriteLine(i + 1);
	}
}


Measured memory_bytes: 13660
/**
  *  Worg
  */
#include <cstdio>
#include <algorithm>

//FILE *fin = freopen("main.in", "r", stdin); FILE *fout = freopen("main.out", "w", stdout);

const int kMaxN = 1e5 + 5;

long long dp[kMaxN][2];
int left[kMaxN][2], cost[kMaxN][2], right[kMaxN][2];

int Bits(int x) {
    int answer = 0;

    while(x > 0) {
        answer ++; x >>= 1;
    }

    return answer;
}

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

    for(int i = 1; i <= N; i++) {
        int x; scanf("%d", &x);

        if((x & (x - 1)) == 0) {
            left[i][0] = left[i][1] = cost[i][0] = cost[i][1] = right[i][0] = right[i][1] = Bits(x) - 1;
        } else {
            int k = Bits(x) - 1;

            left[i][0] = k; cost[i][0] = k + 1; right[i][0] = k + 1;

            left[i][1] = k + 1; cost[i][1] = k + 1; right[i][1] = k;
        }

        for(int j = 0; j < 2; j++) {
            dp[i][j] = cost[i][j] + std::min(dp[i - 1][0] - std::min(right[i - 1][0], left[i][j]),
                                             dp[i - 1][1] - std::min(right[i - 1][1], left[i][j]));
        }
    }

    printf("%lld\n", std::min(dp[N][0], dp[N][1]));
	return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
#define INF 1000000000
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repX(i, n ,x) for (int i = x; i < (int)(n); i++)
#define repM(i, n) for (int i = n; i > 0; i--)

int main() {
    int A,B;
    cin >> A >> B;
    if(A<1||A>9){
        cout << "-1" << endl;
        return 0;
    }
    if (B < 1 || B >9)
    {
        cout << "-1" << endl;
        return 0;
    }
    cout << A*B << endl;

    return 0;
}

Measured memory_bytes: 256
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    println(join(split(readline(),',')," "))
end
main()

Measured memory_bytes: 163220
n,m=map(int,input().split())
l=list(map(int,input().split()))
d={}

c=0
for i in l:
  if i in d:
    d[i]+=1
  else:
    d[i]=1
l1=d.values()
if m>=len(l1):
  print(0)
else:
  l1=sorted(l1)
  for i in range(len(l1)-m):
    c+=l1[i]
  print(c)
  

Measured memory_bytes: 34172
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
S = int(input())

b = S % (10**9)
x2 = (10**9 - b)%(10**9)
y2 = (S+x2)/(10**9)

print("0 0 1000000000 1",x2,int(y2))


Measured memory_bytes: 4592
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;cin>>s;
  int K;cin>>K;
  int N=s.length();
  vector<string> substrings;
  for(int i=1;i<K+1;i++){
    for(int j=0;j<N-i+1;j++){
      substrings.push_back(s.substr(j,i));
    }
  }
  sort(substrings.begin(),substrings.end());
  int tmp=0;
  int i=0;
  string last="";
  int count=1;
  while(1){
    if(last!=substrings[i]){
      if(count==K){cout<<substrings[i];return 0;}count++;
    }
    last=substrings[i];
    i++;
  }
}

Measured memory_bytes: 1660
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
    string[] input = Console.ReadLine().Split(' ');
    long n = long.Parse(input[0]);
    long k = long.Parse(input[1]);
    long p = 1000000007;

    if(n-k < 0) Console.WriteLine(0);
    else Console.WriteLine(SplitNumber(n-k,k,p));
	}

  static long SplitNumber(long n, long k, long mod)
  {//区別しないn個の玉を区別しないk個の箱に分ける方法の個数(mod)をO(nk)で返す。
  //数え方は、dp[n,k]は、0個の箱を含む時+dp[n,k-1]、含まない時+dp[n-k,k]とする。
    long[,] dp = new long[n+1,k+1];
    
    for(int i = 0; i <= k; i++)
    {
      dp[0,i] = 1;
      for(int j = 1; j <= n; j++)
      {
        if(j-i >= 0) dp[j,i] += dp[j-i,i];
        if(i-1 >= 0) dp[j,i] += dp[j,i-1];
     
        dp[j,i] %= mod;
      }
    }

    return dp[n,k];
  }
  
}



Measured memory_bytes: 20052
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;


public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		int[] A = new int[N];
		int count = 0;
		int[] B = new int[N];
		for(int i=0;i<N;i++){
			A[i] = Integer.parseInt(sc.next());
			if(A[i]<0)count++;
			B[i] = Math.abs(A[i]);
		}
		
		Arrays.sort(B);
		long ans = 0;
		if(count%2 == 0){
			for(int i=0; i<N; i++)
				ans += (long)B[i];
		}else{
			ans -= B[0];
			for(int i=1; i<N; i++)
				ans += (long)B[i];
		}
		
		
		



		System.out.println(ans);
		
		
		sc.close();
	}
	
}


Measured memory_bytes: 47968
def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()


Measured memory_bytes: 51080
#include<stdio.h>

int main(void){

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

    for(i = 0;i < N;i++){
        if(A[i] % 2 != 0){
            continue;
        }else{
            if((A[i] % 3 != 0) && (A[i] % 5 != 0)){
                printf("DENIED\n");
                return 0;
            }
        }
    }

    printf("APPROVED\n");
    return 0;
}

Measured memory_bytes: 128
import itertools
n = list(range(1, int(input())+1))
p, q = input(), input()
a = [str(x) for x in n]
new_list = []
for x in itertools.permutations(a):
    new_list.append(" ".join(x))
print(abs(new_list.index(p) - new_list.index(q)))

Measured memory_bytes: 6040
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc009.contest.atcoder.jp/tasks/agc009_a>
問題文============================================================
 N 項からなる数列 A1,…,AN があり、N 個のボタンがあります。
 i(1≦i≦N) 個目のボタンを押すと、数列 A の 1 項目から i 項目までの値が 1 ずつ増加します。
 
 数列 B1,…,BN が与えられます。高橋君は、これらのボタンを何回か押して、
 すべての i に対し、Ai が Bi の倍数になるようにします。
 
 高橋君がボタンを押す回数の最小値を求めてください。
=================================================================

解説=============================================================
================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<ll> A(N),B(N);
    for(int i = 0; i < N;i++) cin >> A[i] >> B[i];
    ll cnt = 0;
    for(int i = N - 1; i >= 0; i--){
        A[i] += cnt;
        cnt += (A[i] + B[i] - 1)/B[i]*B[i] - (A[i]);
    }
    cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 1792
N = int(input())
p = [list(map(int, input().split())) for _ in range(N)]
def find(H):
    for cx in range(101):
        for cy in range(101):
            for x, y, h in p:
                if h > max(H - abs(x - cx) - abs(y - cy), 0):
                    break
            else:
                return True
    return False

lo = 0
hi = 10 ** 10
while hi - lo > 1:
    mid = (hi + lo) // 2
    if find(mid):
        hi = mid
    else:
        lo = mid

for cx in range(101):
    for cy in range(101):
        for x, y, h in p:
            if h != max(hi - abs(x - cx) - abs(y - cy), 0):
                break
        else:
            print(cx, cy, hi)
            exit()

Measured memory_bytes: 51568
S['= r'],m[4]['= r'],z,d[4]={0,-2},k,i;f(i){m[k][i]=S[i]+47?0:m[k][i]?:1+f(d[k]-~i);}main(t){for(scanf("%*d%d",d);S[++i-~*d]=~getchar();d[2]=-*d-2);for(;--i;z=fmax(z,1-t))for(t=k=4;k--;)t-=f(i-~*d);printf("%d",z);}

Measured memory_bytes: 78464
#include <stdio.h>

int main(void)
{
	int a,b,c;
	scanf("%d %d %d", &a,&b,&c);
	
	if((a==b && b==c) || (a!=b && b!=c && a!=c)) printf("No\n");
	else{
	printf("Yes\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl


signed main(void){
    int N;
    string S,T;
    cin >> N;
    cin >> S >> T;
    REP(i,S.size()){
        cout << S[i] << T[i];
    }cout << endl;
    return 0;
}



Measured memory_bytes: 256
import itertools

inf = 10 ** 12

n, m, r = map(int, input().split())
n += 1
rl = [int(i) for i in input().split()]
d = [[inf for _ in[0]*n] for _ in[0]*n]

for _ in[0]*m:
    f, t, c = map(int, input().split())
    d[f][t] = c
    d[t][f] = c

for i in range(n):
    for j in range(n):
        for k in range(n):
            d[j][k] = min(d[j][k], d[j][i] + d[i][k])

ans = inf
for arr in itertools.permutations(rl):
    t = 0
    for i in range(0, r-1):
        t += d[arr[i]][arr[i+1]]
    ans = min(ans, t)
print(ans)

Measured memory_bytes: 47064
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
using ll = long long;
int main()
{
    int x;
    cin >> x;
    int ans = 0;
    ans += x / 500 * 1000;
    x %= 500;
    ans += x / 5 * 5;
    cout << ans << "\n";
    
    return 0;
}

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

int32_t main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
////////////////////////////////

    int n;
    cin >> n;

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

    int ans= 0;

    for (int i=1;i<n;i++){

    	if (arr[i] <  arr[i-1]){
    		ans+= arr[i-1]-arr[i];
    		arr[i] = arr[i-1];
    	}

    }

    cout<<ans<<'\n';

}


Measured memory_bytes: 5212
#include<iostream>
#include<array>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a, b;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back(x);
        b.push_back(y);
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    if (n % 2 != 0) {
        cout << (b.at(n / 2) - a.at(n / 2) + 1) << endl;
    } else {
        int meda = a.at(n / 2) + a.at((n / 2) - 1);
        int medb = b.at(n / 2) + b.at((n / 2) - 1);
        cout << medb - meda + 1 << endl;
    }

}

Measured memory_bytes: 5032
#include <stdio.h>
#include <string.h>
#include <vector>


int main(void){
    char s[101];
    long k;
    int count=0, i, n;
    std::vector<int> nums; //{}
        
    scanf("%s", s);
    scanf("%ld", &k);
    n = strlen(s);
    
    for(int i=0; i<n; i++){
        if(s[i]==s[i+1]){
            count++;
        }else{
            nums.push_back(count+1);
            count=0;
        }
    }
   /*for(i=0; i<nums.size(); i++){
        printf("%d,", nums[i]);
    }
*/
    if(nums.size()==1){
        printf("%ld", k*nums[0]/2);
        return 0;
    }
    if(s[0]!=s[n-1]){
        long sum=0;
        for(i=0; i<nums.size();i++){
            sum = sum + nums[i]/2*k;
        }
        printf("%ld", sum);
        return 0;
    }
        long sum=0;
        for(i=1; i<nums.size()-1;i++){
            sum = sum + nums[i]/2*k;
        }
        sum += nums[0]/2 + nums[nums.size()-1]/2;
        sum += (nums[0]+nums[nums.size()-1])/2*(k-1); 
        printf("%ld", sum);
        return 0;
}

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

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

	long long extra0=0, extra2k=0;

	for(int i=1;i<=n;i++) {
		if(i%k==0) extra0++;
	}

	if(k%2==0) {
		extra2k=0;
		for(int i=1;i<=n;i++) {
			if(i%k==k/2) extra2k++;
		}
	}

	cout << extra0*extra0*extra0 + extra2k*extra2k*extra2k << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func main() {

	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	in := sc.Text()
	val := strings.Split(in, " ")

	a, _ := strconv.ParseFloat(val[0], 6)

	f := float64(a) * float64(a) * math.Pi
	r := float64(a) * float64(2) * math.Pi

	fmt.Printf("%.6f %.6f", f, r)
	fmt.Println()

}



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

int main() 
{
int k,n;
cin>> k;
string s;cin>>s;
n=s.length();
//cout<<n<<" "<<k<<"\n";
if(n<=k)
{cout<<s;}
else if(n>k)
{for(int i=0; i<k; i++)
{
    cout<<s[i];
}
cout<<"...";}
    return 0;
}

Measured memory_bytes: 3580
#include<iostream>
#include<map>
#include<list>
#include<queue>
#include<cstring>
using namespace std;
int dp[1000000];

class graph {
	map<int,list<int>> l;
	int v;
	

	public:
		graph(int n)
		{
			v=n;
		}
	void addedge(int a,int b)
	 { l[a].push_back(b);
	 }
	 int  dfshelper(int src)
	 { //cout<<src<<" ";
	  //vis[src]=1;
	   if(dp[src]!=-1)
	    return dp[src];
	     int ans=0;
	     for(auto p:l[src])
	      {  
             ans=max(ans,1+dfshelper(p));
			 	      	
		  }
	 	  return dp[src]=ans;
	 	
	 }
	 void dfs()
	 { //map<int,bool> vis;
	   int cnt[v+1]={0};
	   int ans=0;
	   for(int i=1;i<=v;i++)
	   {  
	     ans= max(ans,dfshelper(i));
	 	
	   }
	   cout<<ans;
}
};
int main()
{memset(dp,-1,sizeof(dp));
	int n,m;
	cin>>n;
	graph g(n);
	cin>>m;
	for(int i=0;i<m;i++)
	{int a,b;
	  cin>>a>>b;
	  g.addedge(a,b);
	}
	g.dfs();
}

Measured memory_bytes: 15232
use proconio::{fastout, input};

fn main() {
    input!(n: usize, a: [usize; n], q: usize, b_c: [(usize, usize); q]);
    let mut sum: usize = a.iter().sum();
    let v: &mut [usize; 10 * 10 * 10 * 10 * 10] = &mut [0; 10 * 10 * 10 * 10 * 10];
    for i in a {
        v[i - 1] += 1
    }
    for (b, c) in b_c {
        let count = v[b - 1];
        v[c - 1] += count;
        sum = sum.wrapping_add((c.wrapping_sub(b)).wrapping_mul(count));
        v[b - 1] = 0;
        println!("{}", sum);
    }
}


Measured memory_bytes: 6824
a =int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
ls = []
ls.append(abs(a-b))
ls.append(abs(a-c))
ls.append(abs(a-d))
ls.append(abs(a-e))
ls.append(abs(b-c))
ls.append(abs(b-e))
ls.append(abs(b-d))
ls.append(abs(c-d))
ls.append(abs(c-e))
ls.append(abs(d-e))

if max(ls) <= k:
    print("Yay!")
else:
    print(":(")

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>

int main()
{
long long int n;
long long int count = 0;
std::vector<long long int> a;
std::vector<long long int> b;
std::cin >> n;
for(long long int i = 0; i < n; i++){
    long long int aa,bb;
    std::cin >> aa >> bb;
    a.push_back(aa);
    b.push_back(bb);
}
for(long long int i = n - 1; i >= 0; i--){
    if((count + a[i]) % b[i] == 0){
        continue;
    }
    count += b[i] - (count + a[i]) % b[i];
}
std::cout << count << std::endl;
return 0;
}

Measured memory_bytes: 2036
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		prob(System.in, System.out);
	}

	public static void prob(InputStream in, PrintStream out) {
		Scanner sc = new Scanner(in);
		int k = Integer.valueOf(sc.nextLine());
		String s = sc.nextLine();
		
		if (s.length() <= k) {
			out.println(s);
		} else {
			out.println(s.substring(0, k) + "...");
		}
	}
}

Measured memory_bytes: 38648
"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

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

memo = sorted(tuple(map(int,input().split())) for _ in range(M))

seg = SegmentTree.all_identity(min, None, float('inf'), N)

seg[0] = 0

for l,r,c in memo:
    seg[r-1] = min(seg[r-1], seg[l-1:r] + c)

res = seg[N-1]
print(res if res != float('inf') else -1)

Measured memory_bytes: 128756
n = int(input())

s = []
for i in range(n):
  s.append(input())
  
no = False

s_1 = s[1::]

for i, c in enumerate(s):
  if s.count(c) > 1:
    no = True
    
  if i < len(s)-1:
    c_1 = s_1[i]
    if c[-1] != c_1[0]:
      no = True
      
if no == True:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 9144
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f(LL n,LL b){
  LL ans=0;
  while (n){
    ans+=n%b;
    n/=b;
  }
  return ans;
}
int main(){
  LL n,s;
  scanf("%lld%lld",&n,&s);
  if (n<s){
    printf("-1\n");
    return 0;
  }
  if (s==n) {
    printf("%lld\n",n+1);
    return 0;
  }
  for (LL b=2; b*b<=n; ++b){
    if (f(n,b)==s){
      printf("%lld\n",b);
      return 0;
    }
  }
  for (LL p=(LL)sqrt(n); p>=1; --p){
    LL b=(n-s)/p+1;
    if (b==1)continue;
    if (f(n,b)==s){
      printf("%lld\n",b);
      return 0;
    }
  }
  printf("-1\n");
}

Measured memory_bytes: 256
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
answer_line = []
for i in range(x):
    answer_line.append(p[i])
for i in range(y):
    answer_line.append(q[i])
for i in r:
    answer_line.append(i)
answer_line.sort(reverse=True)
ans = 0
for i in range(x+y):
    ans += answer_line[i]
print(ans)

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

int main(){
    //入力
    string S;
    cin >> S;

    //出力
    string ans;
    for(int i=0;i<(S.size()+1)/2;i++){
        ans+=S.at(2*i);
    }
    cout << ans << endl;
    return 0;

}

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

using namespace std;

typedef long long ll;

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

	string s, t;
	cin >> s >> t;

	ll n = (ll) s.size();
	ll m = (ll) t.size();

	vector<int> alp(26, 0);
	rep(i, n) alp[s[i] - 'a']++;

	rep(i, m){
		if(alp[t[i] - 'a'] == 0){
			cout << -1 << endl;
			return 0;
		}
	}

	map<int, vector<ll>> mp;
	rep(i, n){
		mp[s[i] - 'a'].push_back((ll) i);
	}

	for(auto itr = mp.begin(); itr != mp.end(); itr++){
		sort((itr->second).begin(), (itr->second).end());
	}
	//
	// map<int, int> mp2;
	// for(auto itr = mp.begin(); itr != mp.end(); itr++){
	// 	mp2[itr->first] = 0;
	// }

	ll ans = 1LL;
	ll pos = -1;
	for(int i = 0; i < m; i++){
		int c = t[i] - 'a';

		auto itr2 = upper_bound(mp[c].begin(), mp[c].end(), pos);
		if(itr2 == mp[c].end()){
			ans += (n - pos - 1);
			ans += *mp[c].begin() + 1;

			// cout << (n - pos - 1) + *mp[c].begin() + 1 << endl;
			pos = *mp[c].begin();
		}else{
			ans += (*itr2 - pos);
			// cout << (*itr2 - pos) << endl;
			pos = *itr2;
		}

	}

	cout << ans - 1 << endl;
}


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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int cnt[100002];
bitset<100002> reach, total;

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; ++i)
        cnt[i] = 1;

    reach[0] = total[0] = 1;

    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        --a; --b;
        if(cnt[a] > 0){
            cnt[a]--;
            cnt[b]++;
            if(reach[a]){
                total[b] = 1;
                reach[b] = reach[b] | reach[a];
            }
            if(cnt[a] == 0){
                total[a] = reach[a] = 0;
            }
        } else {
            total[a] = 0;
        }
    }

    cout << total.count();

    return 0;
}


Measured memory_bytes: 640
# coding: utf-8

N = int(input())
A = []
for _ in range(2):
    A.append(list(map(int, input().split(" "))))


def oritara(A, orirutoko):
    tmp = sum(A[0][:orirutoko+1])
    tmp += sum(A[1][orirutoko:])
    return tmp

ame = 0
for i in range(N):
    ame = max(oritara(A, i), ame)

print(ame)


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

int main() {
    int K;
    string S;
    cin>> K >> S;

    if(S.size() <= K){
        cout << S << endl;
    }

    else {
        for(int i =0;i<K;i++){
            cout << S.at(i);
        }
        cout << "..." << endl;
    }
}


Measured memory_bytes: 3632
ans = []

while True:
    n, x = map(int, input().split())
    count = 0

    if n == x == 0:
        break
    for i in range(1, n-1):
        for j in range(i+1, n):
            k = x - i - j
            if j < k <= n:
                count += 1
    ans.append(count)

print(*ans, sep='\n')



Measured memory_bytes: 5600
N = int(input())
reslist = [0,0,0,0]
alist = ['AC','WA', 'TLE','RE']
for i in range(N):
    temp = input()
    if temp == alist[0]:
        reslist[0] += 1
    elif temp == alist[1]:
        reslist[1] += 1
    elif temp == alist[2]:
        reslist[2] += 1
    else:
        reslist[3] += 1
for i in range(4):
    print(alist[i], 'x', reslist[i])

Measured memory_bytes: 9236