akhauriyash/Code-Regression huggingface dataset:
// @prefix atcoder
// @description atcoder template

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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'

int modpow(int a, int n, int mod) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

string s;

signed main()
{
	cin >> s;

	int res = 0;
	int now = 0;
	map<int, int> mp;
	mp[0] = 1;

	REP(i, s.size()){
		now += modpow(10, i, 2019) * (s[s.size()-1-i] - '0');
		now %= 2019;
		mp[now]++;
	}

	for (auto m : mp){
		res += (m.second) * (m.second - 1) / 2;
		DEBUGP(m);
    }
	cout << res << endl;


	return 0;
}


Measured memory_bytes: 3756
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int main(){
  int k;
  string s;
  cin >> k >> s;
  if(s.size() <= k)cout << s << endl;
  else{
  	string sub = s.substr(0, k);
  	sub += "...";
  	cout << sub << endl;
  }
  return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>

int main()
{
  int N,M;
  int i=0;
  int j;
  int t=1;
  scanf("%d",&N);
  M=N;
  while(1){
    if(M/2!=0){
      M/=2;
      i++;
    }else if(M/2==0) break;
  }
  for(j=0;j<i;j++) t*=2;
  printf("%d",t);
  return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

#define N_LIM 200000
bool edge[N_LIM][2];
bool visited[N_LIM];

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n, m;
  cin >> n >> m;

  REP(i, n){
    REP(j, 2)
      edge[i][j] = false;
  }

  vector<ll> a(m), b(m);
  REP(i, m){
    cin >> a[i] >> b[i];
    if(a[i] == 1){
      b[i]--;
      edge[b[i]][0] = true;
    }
    else if(b[i] == n){
      a[i]--;
      edge[a[i]][1] = true;
    }
  }

  bool ansflag = false;
  REP(i, n){
    if(edge[i][0] && edge[i][1])
      ansflag = true;
  }

  if(ansflag)
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 3840
import java.util.Scanner;
public class Main
{
	public static void main(String[] args)
    {
     	 Scanner sc = new Scanner(System.in);
      	
     	String[] sep = sc.nextLine().split(" ");
      	System.out.println(sep[2] + " " + sep[0] + " " + sep[1]);
    }
}

Measured memory_bytes: 21460
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String S = sc.next();

		int result = 0;

		if ("+".equals(String.valueOf(S.charAt(0)))) {
			result++;
		} else {
			result--;
		}
		if ("+".equals(String.valueOf(S.charAt(1)))) {
			result++;
		} else {
			result--;
		}
		if ("+".equals(String.valueOf(S.charAt(2)))) {
			result++;
		} else {
			result--;
		}
		if ("+".equals(String.valueOf(S.charAt(3)))) {
			result++;
		} else {
			result--;
		}
		System.out.println(result);
	}

}


Measured memory_bytes: 21716
#include<stdio.h>
int main(){
    int A,B,C,D,L,R;
    scanf("%d %d %d %d",&A,&B,&C,&D);
    L=A+B;
    R=C+D;
    if(L==R){
        printf("Balanced\n");
    }
    else if(L>R){
        printf("Left\n");
    }
    else if(R>L){
        printf("Right\n");
    }
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	bool ans = false;
	int a1 = n % 10;
	int a2 = (n/10) % 10;
	int a3 = (n/100) % 10;
	ans = a1==7 || a2==7 || a3==7;
	if (ans) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 3596
n = int(input())
f = True
w = []
w.append(input())
last = w[0][-1]

for i in range(1,n):
    w.append(input())
    
    if w[i][0] == last and not(w[i] in w[:i]):
        last = w[i][-1]
    else:
        f = False

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



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
  double X;
  int64_t Y = 100;
  cin >> X;
  int year = 0;
  while(Y < X){
    Y *= 1.01;
    year++;
  }
  cout << year;
}

Measured memory_bytes: 3704
#include <iostream>
#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

#define repeat(n) for(int _ = 1; _ <= n; _++)

struct Node {
	int x1;
	int x2;
};

bool operator < (Node a, Node b)
{ return a.x1 + a.x2 < b.x1 + b.x2; }

int main()
{
	ios::sync_with_stdio(false);
#ifdef CAI_WEI_HAN
	freopen("test.in", "r", stdin);
#endif
	
	int n;
	cin >> n;
	
	static Node a[100005];
	for(int i = 1; i <= n; i++)
		cin >> a[i].x1 >> a[i].x2;
	sort(&a[1], &a[n]+1);
	
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		if((n-i) % 2 == 0)
			ans += a[i].x1;
		else
			ans -= a[i].x2;
	}
	
	cout << ans;
}


Measured memory_bytes: 1024
import java.util.Scanner;

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

  int n = fuck.nextInt();

  int b = 0;

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

        int a = n - i;

        b = a + b;
    }

  System.out.println(b + n);

  }

}



Measured memory_bytes: 9428
mod=10**9+7
MAX=10**5+1000

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

n=int(input())
a=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k,mod)-cmb(n+1-c,k-1,mod)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k,mod)
    print(ans)

Measured memory_bytes: 21840
import java.io.*;
import java.util.*;


public class Main {
    public static void main (String[]args)throws IOException {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        int minDistance=k-(a[n-1]-a[0]);
        for (int i = 1; i < n; i++)
            minDistance = Math.max(minDistance, a[i] - a[i-1]);
        System.out.println(k-minDistance);
    }
}


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

int main(){
  int A,B,count = 0;

  cin >> A >> B;

  for(int i = A; i < B + 1; i++){
    int first = i / 10000;
    int fifth = i % 10;
    if(first == fifth){
      int second = (i % 10000) / 1000;
      int forth = (i % 100) / 10;
      if(second == forth){
        count++;
        // cout << i << endl;
      }else{
        continue;
      }
    }else{
      continue;
    }
  }

  cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;
ll power(ll n, ll k){
  ll res = 1;
	while(k > 0){
		if (k & 1) 
      res = res * n % MOD;
		n = n * n % MOD;
		k >>= 1;
	}
	return res;
}
ll fact(ll n){

  ll res = 1;
  while (n > 0){
    res = (res * n) % MOD;
    n--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}

ll hoge(ll r, ll c){
  ll res = 1;
  for (int i = 0; i < c; i++){
    res = res * (r - i) % MOD;
  }

  return res;
}

ll ncr(ll r, ll c){
  if (c == 0)
    return 1;
  if (r == 0)
    return 1;

  return ((hoge(r + c, c) % MOD) * inv(fact(c))) % MOD;
}



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


  ll sum = 1;
  ll l = 1;
  ll ncl = 1;

  if (k < n){
    while (l <= k){
      ncl = (((ncl * (inv(l) % MOD)% MOD) * (inv(l) % MOD) % MOD) * (n - l) % MOD) * (n - l + 1) % MOD;
      sum = (sum + ncl) % MOD;
      l++;
    }
 
    /*
    while (l <= k){
      sum = (sum + ncr(n - l, l) * ncr(n - l - 1, l)) % MOD;
      l++;
    }
    */
  }
//  else if (k == n){
//    while (l < k - 1){
//      ncl = (((ncl * (inv(l) % MOD)% MOD) * (inv(l) % MOD) % MOD) * (n - l) % MOD) * (n - l + 1) % MOD;
//      sum = (sum + ncl) % MOD;
//      l++;
//    }
// 
//    /*
//    while (l < k - 1){
//      sum = (sum + ncr(n - l, l) * ncr(n - l - 1, l)) % MOD;
//      l++;
//    }
//    */
//  }
  else {
    while (l < n){
      ncl = (((ncl * (inv(l) % MOD)% MOD) * (inv(l) % MOD) % MOD) * (n - l) % MOD) * (n - l + 1) % MOD;
      sum = (sum + ncl) % MOD;
      l++;
    }
  }
  
  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#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() {
    int n;
    cin >> n;
    int h[n+2];
    rep(i,n) cin >> h[i+2];
    h[0] = h[2], h[1] = h[2];
    int dp[n+2] = {};
    rep(i,n) {
        dp[i+2] = min(dp[i+1] + abs(h[i+2] - h[i+1]), dp[i] + abs(h[i+2] - h[i]));
    }
    int ans = dp[n+1];
    cout << ans << endl;
}


Measured memory_bytes: 1024
def f(x)
    a = x.split("")
    return 'NA' if a.uniq.size == 1
    return 0 if x == "6174"
    sorted = a.sort
    l = sorted.reverse.join.to_i
    s = sorted.join.to_i
    return 1 + f(sprintf("%04d", (l - s)))
end

while gets
    break if $_ =~ /^0000$/
    puts f($_.chomp)
end

Measured memory_bytes: 9524
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

vector< vector< pair<ll, ll> > > e;
vector<ll> ans;

void make_tree(ll v, ll p) {
    for (auto i = e.at(v).begin(); i != e.at(v).end();) {
        if ((*i).first == p) e.at(v).erase(i);
        else make_tree((*i).first, v), ++i;
    }
}

void solve(ll v, ll d) {
    ans.at(v) = d;
    for (auto i = e.at(v).begin(); i != e.at(v).end(); ++i) solve((*i).first, d + (*i).second);
}

int main() {
    ll n, u, v, w;
    scanf("%lld", &n);
    e.resize(n + 1);
    ans.resize(n + 1);
    for (ll i = 1; i < n; ++i) {
        scanf("%lld%lld%lld", &u, &v, &w);
        e.at(u).push_back({v, w});
        e.at(v).push_back({u, w});
    }
    make_tree(1, 0);
    solve(1, 0);
    for (ll i = 1; i <= n; ++i) printf("%lld\n", ans.at(i) % 2);
    return 0;
}


Measured memory_bytes: 9984
#include <algorithm>
#include <cstdlib>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
string a,b;



int main(int argc, char const *argv[])
{
    cin>>a>>b;
    string ab=a+b;
    int integer_of_ab = atoi(ab.c_str());
    for(int i=0;i<integer_of_ab;i++){
        if(pow(i,2)==integer_of_ab){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=100;
int a[MAXN+5];
int n,ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			ans+=a[i]*a[j];
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.io.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int a = Integer.parseInt(sc.next()); //Aの値段
		int b = Integer.parseInt(sc.next()); //Bの値段
		int c = Integer.parseInt(sc.next()); //ABの値段
		int d = Integer.parseInt(sc.next()); //Aの枚数
		int e = Integer.parseInt(sc.next()); //Bの枚数
		int ap =0;							//A買う枚数
		int bp =0;							//B買う枚数
		int cp = 0;							//C買う枚数
		if(2*c <= a && 2*c <= b){
			if(d<=e)cp =2*e;
			if(e<d)cp =2*d;
		}else if(2*c <= a){						//A一枚がAB二枚よりも高い場合
			cp =d*2;
			if(d<e)bp =e-d;
		}else if(2*c <= b){					//B一枚がAB二枚よりも高い場合
			cp =e*2;
			if(e<d)ap =d-e;
		}else if(a+b>2*c) {					//A+BがAB二枚よりも高い場合
			if(d>=e) {
				cp=2*e;
				ap=d-e;
			}else if(d<e){
				cp=2*d;
				bp=e-d;
			}
		}else{
			ap=d;
			bp=e;
		}
		System.out.println(ap*a+bp*b+cp*c); 
	}
}


Measured memory_bytes: 22612
#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;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multi_set;

#define mod         1000000007
#define pi          3.1415926535898
#define eps         1e-9


#define fast       ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define vt vector
#define ar array
#define fs          first
#define sc          second
#define pb         push_back
#define sp          printf(" ")
#define nl          '\n'
#define all(a) a.begin(),a.end()
#define unique(c) (c).resize(unique(all(c)) - (c).begin())
#define sz(x) (int)(x).size()
#define revsort(x) sort(all(x));reverse(all(x))

#define set0(a)     memset(a,0,sizeof(a))
#define setneg(a)   memset(a,-1,sizeof(a))
#define setinf(a)   memset(a,126,sizeof(a))

#define REP(i,start,end) for (int i = start; i <=end; i++)
#define RREP(i,end,start) for (int i=end; i>=start ;i--)
#define EACH(x, a) for (auto& x: a)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<LL> vll;
typedef vector<double> vd;
typedef vector<vector<LL> > matrix;
typedef vector<vector<int> > graph;


 
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
    cin >> x;
}
void read(double& d) {
    string t;
    read(t);
    d=stod(t);
}
void read(long double& d) {
    string t;
    read(t);
    d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class A> void read(vt<A>& x) {
    EACH(a, x)
        read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
    EACH(a, x)
        read(a);
}

LL powm(LL x, LL y,LL m) {
    if (y==0) return 1;
    if (y==1) return x%m;
    if (y&1) return (x*(powm((x*x)%m,y/2,m)))%m;
    return powm((x*x)%m,y/2,m)%m;
}

LL inv(LL x, LL m) {
    return powm(x,m-2,m);
}

int add(int var1, int var2) {
    return (((((LL)(var1)) % mod + (LL)(var2)) % mod) + mod) % mod;
}


int mul(int var1, int var2) {
    return (((LL)(var1)) % mod * (LL)(var2)) % mod;
}

LL INF=1e16;

LL x,k,d;

bool func(LL a1, LL a2) {
    if (a2 > abs(INF/d) ) return 0;
    return ((x-a1*d > 0 and x-a2*d > 0) or (x-a1*d < 0 and x-a2*d < 0));
}

void solve() {
    read(x, k, d);
    if (x<0) d = -d;

    LL ans = 0;
    LL jump = k;
    while (jump) {
        while (ans+jump <= k and func(ans, ans+jump))
            ans += jump;
        jump /= 2;
    }
    x -= ans*d;
    k -= ans;
    k &= 1;
    if (k) {
        x = min(abs(x+d), abs(x-d));
    }
    x = abs(x);
    cout << x << nl;
}

int main() {
    fast;
    solve();
}


Measured memory_bytes: 3608
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;

#define y1 y11
#define less less228
#define left left228
#define right right228
#define list list228
#define all(v) v.begin(), v.end()
#define tm tm228
 
 
 
template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int INF = 1e18 + 228;

struct man
{
    int h, p;
    man() {}
    man(int _h, int _p) {h = _h, p = _p;}
};
bool operator<(man a, man b) {
    return a.h + a.p < b.h + b.p;
}

const int N = 5005;

man a[N];
int dp[N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].h >> a[i].p;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i - 1; j + 1; --j) {
            if (dp[j] <= a[i].h) {
                uin(dp[j + 1], a[i].p + dp[j]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (dp[i] != INF) uax(ans,i);
    }
    
    cout << ans << '\n';
    return 0;
}
// RU_023
 
/*
6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
-----
1
 
 
 
8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4
 
 
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
 
 
8 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1
3
1
1
3
2
3
2
 
 
 
 
 
*/

Measured memory_bytes: 384
import java.util.Scanner;
import java.lang.Integer;
import java.lang.StringBuilder;
import java.lang.Math;

public class Main {
  private static int N;
  private static int[] a;

  private static void print() {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < N; i++) {
      result.append(a[i]);
      result.append(" ");
    }
    System.out.println(result.toString().trim());
  }

  private static void sort() {
    if (a.length == 1) {
      print();
      return;
    }
    int min = 0;

    for (int i = 1; i < N; i++) {
      print();
      int v = a[i];
      int j = i - 1;
      while (j >= 0 && v < a[j]) {
        // right shift
        a[j + 1] = a[j];
        j--;
      }
      a[j + 1] = v;
    }
    print();
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = in.nextInt();
    }

    // sort a.
    sort();
    // a is now sorted.


  }
}

Measured memory_bytes: 28712
import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int N = sc.nextInt();
        int[] a = new int[N];

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

        int maxGap = 0;
        for (int i = N; i > 0;i--) {
            if (i > 1) {
                maxGap = Math.max(maxGap ,(a[i-1] - a[i-2])) ;
            }

            else {
                maxGap = Math.max(maxGap, (K - a[N-1] + a[0]));
            }
        }

        System.out.println(K-maxGap);
    }
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  int x=0;
  
  for(int i=0;i<N;i++){
      cin>>vec.at(i);
    x+=vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
  
  if(x%10!=0){
    cout<<x<<endl;
  }
  else{
  
  for(int i=0;i<N;i++){
    if(vec.at(i)%10!=0){
      x-=vec.at(i);
      cout<<x<<endl;
      return 0;
    }
  }
  
    cout<<"0"<<endl;
  }
}


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    ll ans = 0;

    char in[3];

    ll out = 0;
    int dig = 0;
    int Q = 0;

    bool allnine = 1;

    while(true){
        int fl = 1;
        int fr = 10;
        if( dig > 0 ) fl--;
        // [l,r)
        while( fr - fl > 1 ){
            int fc = (fl+fr)/2;
            // printf ("[%d,%d) %d\n", fl, fr, fc );

            out = ans*10+fc;
            Rep(donkeykong,17-dig) out *= 10;
            out--;

            Q++;
            printf ("? %lld\n", out );
            fflush( stdout );

            Scs(in);

            if( in[0] == 'Y' ) fr = fc;
            else fl = fc;

        }
        if( fl == 0 ){
            Q++;
            printf ("? %lld\n", ans+1 );
            fflush( stdout );

            Scs(in);

            if( ( in[0] == 'Y' ) xor allnine ) break;
        }
        if( fl != 9 ) allnine = 0;
        ans = ans*10+fl;
        dig++;
        // printf ("# %lld\n", ans );
    }

    printf ("! %lld\n", ans );
    fflush( stdout );
    // printf ("Q=%d\n", Q);


    return 0;
}





Measured memory_bytes: 596
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class Program
	{
		static long mod = 1000000007;

		static int N;
		static int K;
		static int[] a;

		static long[,] dp;

		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			N = vs[0];
			K = vs[1];
			a = Console.ReadLine().Split().Select(int.Parse).ToArray();

			dp = new long[N, K + 1];
			for (int j = 0; j <= a[0]; j++) {
				dp[0, j] = 1;
			}

			for (int i = 1; i < N; i++) {
				long sum = 0;
				for (int j = 0; j <= K; j++) {
					sum += dp[i - 1, j];
					if (j - a[i] - 1 >= 0) {
						sum -= dp[i - 1, j - a[i] - 1];
					}
					dp[i, j] = sum % mod;
				}
			}
			Console.WriteLine(dp[N - 1, K]);
		}
	}
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    int answer = 1;
    for (int i = 0; i < n; i++)
    {
        answer = min(answer * 2, answer + k);
    }
    cout << answer << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 50

struct NODE { int parent, left, right; };

struct NODE Tree[MAX];
int N;
int pre[MAX];
int ino[MAX];

int cnt = 0;

int Top(int sp, int ep) {
	int ans;
	for (int i = 0; i < 50; i++) {
		for (int j = sp; j < ep; j++) {
			if (pre[i] == ino[j]) {
				ans = j;
				return ans;
			}
		}
	}
}

void Hierarchy(int sp, int top, int ep) {
	int lTop, rTop;
	if (ep - sp != 1) {
		if (sp != top) {
			lTop = Top(sp, top);
			Tree[ino[top]].left = ino[lTop];
			Tree[ino[lTop]].parent = ino[top];
			Hierarchy(sp, lTop, top);
		}
		if (top + 1 != ep) {
			rTop = Top(top + 1, ep);
			Tree[ino[top]].right = ino[rTop];
			Tree[ino[rTop]].parent = ino[top];
			Hierarchy(top + 1, rTop, ep);
		}
	}

}

void Postorder(int id) {
	if (id == -1)return;
	Postorder(Tree[id].left);
	Postorder(Tree[id].right);
	printf("%d", id);
	cnt++;
	if (cnt != N)printf(" ");
}

int main() {
	int root;
	for (int i = 0; i < 50; i++) {
		Tree[i].parent = -1; Tree[i].left = -1; Tree[i].right = -1;
		pre[i] = -1; ino[i] = -1;
	}
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &pre[i]);
	}
	for (int i = 0; i < N; i++) {
		scanf("%d", &ino[i]);
	}
	root = ino[Top(0, N)];
	Hierarchy(0, Top(0, N), N);

	Postorder(root); printf("\n");

	return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;

int N;

int main() {
    cin >> N;

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += i;
    }

    cout << ans << endl;
}

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

using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;

int main() {
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == t[i])ans++;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
N=int(input())
d=dict()
for tt in range(N):
    s=input()
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
for st in ["AC","WA","TLE","RE"]:
    if st not in d:
        print(st," x ",0)
    else:
        print(st," x ",d[st])

Measured memory_bytes: 9196
#!/usr/bin/env python3

n, k = list(map(int, input().split()))

ans = 0
for i in range(k+1, n+1):
    num = n//i
    ans_tmp = num * (i-k)
    ans_tmp += max(0, n % i - k + 1)
    if k == 0:
        ans_tmp -= 1
    ans += ans_tmp
    # print(num * (i-k))
    # print(max(0, n % i - k + 1))
    # print()
print(ans)


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

using namespace std;
#define ll long long
int main()
{  ll n;cin>>n;
  string s;
  while(n>0){
      n--;
      s+=('a'+n%26);
      n=n/26;
  }
 reverse(s.begin(),s.end());
 cout<<s<<endl;
   
   return 0;
}

Measured memory_bytes: 3596
#include <vector>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <climits>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int n,m,z=0,c=0;
    cin>>n>>m;
    vector<vector<int>>a;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        a.push_back(vector<int>(k));
        for(int j=0;j<k;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<n;j++){
            z+=count(a[j].begin(),a[j].end(),i);
        }
        if(z==n){
            c++;
        }
        z=0;
    }
    cout<<c;
}

Measured memory_bytes: 256
import collections
N = int(input())
array = []
for i in range(N):
    s = input()
    dict = {}
    for j in range(len(s)):
        if s[j] not in dict:
            dict[s[j]] = 1
        else:
            dict[s[j]] += 1
    dict = sorted(dict.items())

    array.append(str(dict))
sum = 0
c = collections.Counter(array)
for v in c.values():
    sum += int(v*(v-1)/2)
print(sum)

Measured memory_bytes: 28272
n = int(input())
a = list(map(int,input().split()))
c = 1
x = 0
for i in range(n-1):
    y = a[i+1]-a[i]
    if x*y<0:
        if i<n-2:x = a[i+2]-a[i+1]
        c+=1
    elif y!=0:x=y
print(c)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
using namespace std;


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

ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}


int main() {
    //vector<int> ans;
    ll a,b ,c,d,n,m;
    cin>>a>>b>>c>>d;
    
    n = ((a-1)/c) + ((a-1)/d) -((a-1)/lcm(c, d));
    m = (b/c) + (b/d) -(b/lcm(c, d));
    
    ll k = a - 1 - n;
    ll l = b - m;
        
    cout<<l-k<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>
#define NIL -1
#define MAX 26
using namespace std;

struct Node
{
    int parent, left, right;
};
Node T[MAX];

void travelPreorder(int root) {
    if(root == NIL) return;
    cout << " " << root;
    travelPreorder(T[root].left);
    travelPreorder(T[root].right);
}

void travelInorder(int root) {
    if (root == NIL)
        return;
    travelInorder(T[root].left);
    cout << " " << root;
    travelInorder(T[root].right);
}

void travelPostorder(int root)
{
    if (root == NIL)
        return;
    travelPostorder(T[root].left);
    travelPostorder(T[root].right);
    cout << " " << root;
}

int main()
{
    int n, root;
    cin >> n;
    for(int i=0; i<n; i++) {
        T[i].parent = T[i].left = T[i].right = NIL;
    }
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        cin >> T[t].left >> T[t].right;
        if (T[t].left != NIL)
        {
            T[T[t].left].parent = t;
        }
        if (T[t].right != NIL)
        {
            T[T[t].right].parent = t;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (T[i].parent == NIL)
            root = i;
    }
    cout << "Preorder" << endl;
    travelPreorder(root);
    cout << "\n";
    cout << "Inorder" << endl;
    travelInorder(root);
    cout << "\n";
    cout << "Postorder" << endl;
    travelPostorder(root);
    cout << "\n";
}



Measured memory_bytes: 3108
#include <iostream>

using namespace std;

int roots[10000];

int root(int x) {
  if (x == roots[x]) {
    return x;
  } else {
    //roots[x] = root(roots[x]); //attach all to root
    return root(roots[x]);
  }
}
          
  
bool same(int x, int y) {
  return (root(x) == root(y));
}

void unite(int x, int y) {
  roots[root(x)] = root(y);
}


int main() {

  int n, q;
  cin >> n >> q;

  for (int i = 0; i < n; i++) {
    roots[i] = i;
  }

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

    int com, x, y;
    cin >> com >> x >> y;
    //cout << "command is " << com << endl;
    //for (int j = 0; j < n; j++) {
    //cout << "node + " << j << " has root: " << roots[j] << endl;
    //}
    if (com == 0) {
      unite(x, y);
    } else if (com == 1) {
      if (same(x, y)) {
	cout << 1 << endl;
      } else {
	cout << 0 << endl;
      }
    }
  }
    

  
}

Measured memory_bytes: 1204
#include <iostream>
#include <iomanip>

int main()
{
    using namespace std;
    
    int n, k;
    double prefix_sum[200001] = {0}, p[200000], ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> p[i];
        prefix_sum[i + 1] += ((p[i] + 1) / 2 + prefix_sum[i]);
    }
    for(int i = 0; i <= n - k; i++){
        ans = max(ans, prefix_sum[i + k] - prefix_sum[i]);
    }
    cout << fixed << setprecision(12) << ans << endl;
}


Measured memory_bytes: 6884
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }

int main(){
    int a,b; cin >> a >> b;
    if(a % 2 == 1 && b % 2 == 1) yes();
    else no();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int dp[1000005];

int dfs(vector<int> adj[], bool vis[], int i) {
    if(vis[i]) return 0;
    if(dp[i]!=-1) return dp[i];

    vis[i]=true;
    int ans=0;
    for(int j:adj[i]) ans=max(ans, 1+dfs(adj, vis, j));
    vis[i]=false;
    
    dp[i]=ans;
    return ans;
}

int main() {
    Fast

    int v,e; cin>>v>>e;
    vector<int> adj[v+1];
    for(int i=0; i<e; i++) {
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
    }

    memset(dp, -1, sizeof(dp));
    for(int i=0; i<=v; i++) {
        bool vis[v];
        memset(vis, false, sizeof(vis));
        dp[i]=max(dp[i], dfs(adj, vis, i));
        //cout<<"ans: "<<ans<<endl;
    }

    int ans=0;
    for(int i=0; i<=v; i++) ans=max(ans,dp[i]);
    cout<<ans;
    // 5 5 1 2 1 3 2 3 3 2 2 4   ans 3
}


Measured memory_bytes: 13184
/* 
	Author: ankrypt
*/


#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

ll N, M, K;
ll arr[100005], arr1[100005];
string S = "";
std::vector<ll> V;
// set<ll> S;
map<string, ll> mp;
queue<ll> q;
stack<ll> st;


int main() {
	scanf("%lld", &N);
	ll maxCnt = 0;
	for(int i = 0; i < N; i++) {
		cin >> S;
		mp[S]++;
		maxCnt = max(maxCnt, mp[S]);
	}
	map<string, ll> :: iterator itr;
	for(itr = mp.begin(); itr != mp.end(); itr++) {
		if(itr->second == maxCnt) {
			cout << itr->first << " \n";
		}
	}
	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 25344
// Problem : A - Payment
// Contest : AtCoder - AtCoder Beginner Contest 173
// URL : https://atcoder.jp/contests/abc173/tasks/abc173_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)


/*when the going gets tough the tough gets going  */
/*we are what we repeatedly do , Excellence then is not an act but a habit  - aristotle */
/*The best way to predict the future is to create it - abraham lincoln*/
/*First think , second believe , third dream and finally dare - walt disney*/
/*It is during our darkest moments that we must focus to see the light */
/*Nothing is impossible the word itself says "i'm fucking possible man just try me again and again till i seem impossible "*/
/*Dont judge each day by the harvest you reap but by the seeds you plant */
/*Do not dwell in the past, do not dream of the future, concentrate the mind on the present moment*/
/*Success is not final failure is not fatal : it is the courage to continue that counts */ 
/*the future belongs to those who believe in the beauty of their dreams */
/*The pessimist complains about the wind , the optimist waits for it to change; the realist adjusts the sails  */
/*Believe you can and you are half way there */
/*Everything has beauty but not everyone sees it */
/*Life is not about finding yourself , life is about creating yourself*/
/*You are the average of the 5 people you spend the most time with .........*/
/*Everything is hard before it is easy see for example now the list of examples is very long hahahahahaha...... ......*/
/*I believe in miracles .......*/
#include<bits/stdc++.h>
#define LL long long 
#define pb push_back

#define PII pair<int , int > 
#define PLL pair<LL , LL >
#define LD long double
#define VLL vector<LL>
#define VPII vector<PII>
#define VI vector<int>
#define VPLL vector<PLL>
#define VLD vector<LD>
#define VVI vector<VI>
#define VVLL vector<VLL>
#define VVPLL vector<VPLL>
#define VVII vector<VPII>
#define IN insert
#define wht while (t--)
#define FU( i , a  , n ) for ( int i = (int)a ; i <=(int)n ; i++  )
#define FD( i , n , a ) for (int i = (int)n ; i >=(int)a ;i--)
#define REP(i,n) for ( int i = 0 ; i < (int)n;  i++)
#define FST  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define SZ(a) int((a).size())
#define pi(n) printf("%d" , n ) 
#define pl(n) printf("%lld" , n )
#define ff first
#define ss second
#define ii(n) scanf("%d" , &n)
#define il(n) scanf("%lld" , &n )
#define LB lower_bound
#define UB upper_bound
#define BS binary_search
#define ALL(V) V.begin(), V.end()
#define ic(n) cin>>n
#define pr printf
#define INF 99999999
#define en endl
using namespace std ;
string str ;
const int tt = 0;
 void solve()
 {
 	int   m , n ,a , b ,c ;
 	cin>> n;
 	m = (n % 1000);
 	// n -= m ;
 	// m -=1000;
 	m = (1000 - m );
 	m%=1000;
 	cout << m ;
 	
 }
int main()
{
	FST;
	
    if (tt)
    {
    	int t;
    	cin>> t ;
    	while (t--)
    	{
    		solve();
    	}
    }
    else
    {
    	solve();
    }
	return 0 ;
	
 
} 

Measured memory_bytes: 3636
import math
N = int(input())
ls1 = []
ls2 = []
for i in range(N):
    ls1.append(list(map(int,input().split())))
x = 0
y = 0
for i in range(N):
    for j in range(i+1,N):
        x = (ls1[i][0]-ls1[j][0])**2
        y = (ls1[i][1]-ls1[j][1])**2
        XY = math.sqrt(x+y)
        ls2.append(XY)
if len(ls2) == 1:
    print(ls2[0])
else:
    ans = sum(ls2)*2/N
    print(ans)


Measured memory_bytes: 3064
def BobbleSort(C, N):
    flag = True
    while flag:
        flag = False
        for i in range(N-1,0,-1):
            if C[i-1][1] > C[i][1]:
                C[i-1], C[i] = C[i], C[i-1]
                flag = True
    return C

def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]

def Stable(C1, C2, N):
    # Stable なら True
    flag = True
    
    # C2 を並び替え後とする
    for i in range(1, N):
        if C2[i-1][1] == C2[i][1]:
            a = C1.index(C2[i-1])
            b = C1.index(C2[i])
            if a > b:
                flag = False
                break
    
    if flag:
        print("Stable")
    else:
        print("Not stable")
    
N = int(input())
orgC = [x for x in input().split()]
C = orgC.copy()

BobbleSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)

C = orgC.copy()
SelectionSort(C,N)
print(" ".join(C))
Stable(orgC, C, N)


Measured memory_bytes: 5612
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <set>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

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

  int h, w, k;
  cin >> h >> w >> k;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  x1--;
  y1--;
  x2--;
  y2--;
  vector<string> c(h);
  for (auto &x: c) cin >> x;

  vector<vector<int> > dist(h, vector<int>(w, 1000000007));
  vector<vector<bool> > visited(h, vector<bool>(w));
  dist[x1][y1] = 0;
  queue<Pii> que;
  que.emplace(x1, y1);
  while (!que.empty()) {
    auto [x, y] = que.front();
    que.pop();
    if (visited[x][y]) continue;  
    visited[x][y] = true;
    // up
    for (int i = x - 1; i >= max(0, x - k); i--) {
      if (c[i][y] == '@') break;
      if (dist[i][y] < dist[x][y] + 1) break;
      if (dist[i][y] > dist[x][y] + 1 && !visited[i][y]) que.emplace(i, y);
      dist[i][y] = dist[x][y] + 1;
    }
    // down
    for (int i = x + 1; i <= min(h - 1, x + k); i++) {
      if (c[i][y] == '@') break;
      if (dist[i][y] < dist[x][y] + 1) break;
      if (dist[i][y] > dist[x][y] + 1 && !visited[i][y]) que.emplace(i, y);
      dist[i][y] = dist[x][y] + 1;
    }
    // left
    for (int j = y - 1; j >= max(0, y - k); j--) {
      if (c[x][j] == '@') break;
      if (dist[x][j] < dist[x][y] + 1) break;
      if (dist[x][j] > dist[x][y] + 1 && !visited[x][j]) que.emplace(x, j);
      dist[x][j] = dist[x][y] + 1;
    }
    // right
    for (int j = y + 1; j <= min(w - 1, y + k); j++) {
      if (c[x][j] == '@') break;
      if (dist[x][j] < dist[x][y] + 1) break;
      if (dist[x][j] > dist[x][y] + 1 && !visited[x][j]) que.emplace(x, j);
      dist[x][j] = dist[x][y] + 1;
    }
  }

  if (dist[x2][y2] != 1000000007) cout << dist[x2][y2] << endl;
  else cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 12112
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N;
    std::cin >> N;
    
    std::string temp;
    char tail;
    char head;
    std::vector<std::string> words;
    bool win = true;
    for (auto i=0; i<N; ++i) {
        std::cin >> temp;
        auto find_iter = std::find(words.begin(), words.end(), temp);
        if (find_iter != words.end()) {
            win = false;
            break;
        }
        words.push_back(temp);
        head = temp.front();
        if (i != 0) {
            if (head != tail) {
                win = false;
                break;
            }
        }
        tail = temp.back();
    }
    if (win) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > //第二成分の大きさが関係ない
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



ll ans[26];

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

	ll N;
	cin >> N ;
	rep(i, 26){
		ans[i] = 50;
	}

	rep(i, N){
		string inp;
		cin >> inp;
		vector<ll> cnt;
		rep(j,26){cnt.pb(0);}

		rep(j, inp.size()){
			cnt[inp[j]-'a'] ++;
		}

		rep(j, 26){
			ans[j] = min(ans[j], cnt[j]);
		}

	}

	rep(i, 26){
		rep(j, ans[i]){
			cout << (char)('a' + i);
		}
	}
	cout << " " << endl;

	//cout << fixed << setprecision(16) << ans << endl;
	return 0;
}


Measured memory_bytes: 256
//ABC048B
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
#include <unordered_map>
using namespace std;

int main(){
	long long int a, b, x;
	cin >> a >> b >> x;
	long long int ans;
	if(a == 0){
		ans = b/x+1;
	}else{
		ans = b/x-(a-1)/x;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int mod = 1e9 + 7;

int f(int& x){
    if (x >= mod)
        x %= mod;
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<vi> dp(n + 1, vi(n + 1, 0));
    dp[1][1] = 1;

    vector<vi> p(n + 1, vi(n + 1, 0));
    for (int i = 1; i <= n; ++i)
        p[1][i] = 1;

    for (int len = 2; len <= n; ++len){
        for (int b = 1; b <= len; ++b){
            if (s[len - 2] == '<'){
                dp[len][b] += p[len - 1][b - 1];
            } else {
                dp[len][b] += p[len - 1][len - 1] - p[len - 1][b - 1];
            }
            dp[len][b] += 2 * mod;

            f(dp[len][b]);
        }

        for (int i = 1; i <= n; ++i){
            p[len][i] = p[len][i - 1] + dp[len][i];
            f(p[len][i]);
        }
    }

    int sol  =0;
    for (int i = 1; i <= n; ++i){
        sol += dp[n][i];
        f(sol);
    }

    cout << sol << '\n';
}

Measured memory_bytes: 141184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main(void) {
	ll N, A, B;
	cin >> N >> A >> B;
	if(N == 1){
		if(A != B)printf("0\n");
		else printf("1\n");
		return 0;
	}

	ll ma = A + B * (N - 1);
	ll mi = A * (N - 1) + B;
	printf("%lld\n", max(0ll, ma - mi + 1));
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;

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


int main(){
    string S, T;
    cin >> S >> T;

    ll l = S.length();
    ll ans = 0;
    rep(i, l){
        if(S[i] != T[i]){
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

#define ll long long

void solve() {
	string s;
	cin >> s;
	if (s[0] == s[2]) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
}

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

	int t = 1, i = 1;
	//cin >> t;
	while(t--) {
		//cout << "Case #" << i << ": ";
		solve();
		//i++;
	}
	return 0;
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int main() {
    ll h,w; cin >> h >> w;
    if(h == 1 || w == 1) {
        cout << 1 << endl;
        return 0;
    }
    ll ans = h*w/2;
    if(h*w%2 == 1) ans++;
    cout << ans << endl;
    return 0;
}


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

int main(){

    int N;
    cin >> N;

    int A;
    double newCalc = 0.0;
    double oldCalc = 0.0;

    for(int i=0; i<N; i++){
        cin >> A;
        oldCalc = newCalc;
        newCalc = oldCalc + 1.0/A;
    }

    cout << 1.0/newCalc;


    return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll a, b, c, d, ans;
  cin>>a>>b>>c>>d;
  
  //最小公倍数を求める
  ll x=max(c,d), y=min(c,d), g;
  while(x%y!=0){
    x=x%y;
    swap(x, y);
  }
  g = c*d/y;
  
  ll all = b-a+1;
  ll cc = b/c-(a-1)/c;
  ll dd = b/d-(a-1)/d;
  ll gg = b/g-(a-1)/g;
  
  ans = all-(cc+dd-gg);
  cout<<ans<<endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
using namespace std;
using ll = long long;

int main()
{
    int n;
    int r;
    cin >> n >> r;
    int ans;
    if (n >= 10){
        ans = r;
    }else{
        ans = r + 100*(10-n);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256