akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
L = sorted(LI())


total = L[-1] - L[0]
diff_list = sorted([L[i+1] - L[i] for i in range(m-1)], reverse=True)
if n >= m:
    print(0)
else:
    print(total - sum(diff_list[:n-1]))

Measured memory_bytes: 59576
#include <iostream>
#include <vector>
using namespace std;
  //絶対値
int abs(int x) {
				return max(x,-x);
}
int main() {
  int a,b,c,d;
  cin >>a>>b>>c>>d;
  if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)) cout <<"Yes";
  else cout <<"No";
  
}


Measured memory_bytes: 256
/**
*    created: 04.07.2020 21:10:44
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
const long double pi = acos(-1.0);
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;
    rep(i,s.size()) if (i % 2 == 0) cout << s[i];
    cout << endl;
    return 0;
}

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

using namespace std;

int main() {
    int arr[3] = {1, 0, 0};
    char c1, c2, comma;
    while(cin >> c1 >> comma >> c2) 
        swap(arr[c1-'A'], arr[c2-'A']);
    for(int i = 0; i < 3; ++i)
        if(arr[i]) cout << (char)('A'+i) << endl;
    return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
 
static const int N = 1000;
 
void trace(int A[], int n){
  for ( int i = 1; i <= n; i++ ){
    if ( i >1 ) cout << " ";
    cout << A[i];
  }
  cout << endl;
}
 
main(){
  int n;
  int A[N+1];
  cin >> n;
  for ( int i = 1; i <= n; i++ ) cin >> A[i];
   
  trace(A, n);
  for ( int j = 2; j <= n; j++ ){
    int key = A[j];
    int i = j - 1;
    while( i > 0 && A[i] > key ){
      A[i+1] = A[i];
      i--;
    }
    A[i+1] = key;
 
    trace(A, n);
  }
}

Measured memory_bytes: 3100
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
        for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
        for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])


Measured memory_bytes: 263936
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

s = list(input().rstrip())
t = list(input().rstrip())

d = {}
N = len(s)
for i in range(N):
    if s[i] not in d:
        d[s[i]] = [i]
    else:
        d[s[i]].append(i)

now = -1
c = 0
for i in range(len(t)):
    if t[i] in d:
        next = bisect.bisect_right(d[t[i]],now)
        if next < len(d[t[i]]):
            nnum = d[t[i]][next]
            now = nnum
        else:
            c += 1
            now = -1
            next = bisect.bisect_right(d[t[i]],now)
            nnum = d[t[i]][next]
            now = nnum
    else:
        print(-1)
        break
else:
    print(c*N+now+1)

Measured memory_bytes: 56328
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

s64 T1, T2;
s64 A1, A2;
s64 B1, B2;

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

    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;

    s64 diff = A1 * T1 + A2 * T2 - B1 * T1 - B2 * T2;
    if (diff == 0)
    {
        cout << "infinity\n";
        return 0;
    }

    u64 ans = 0;
    s64 diffAB1 = A1 * T1 - B1 * T1;

    s64 temp1 = diffAB1 / diff;

    if ( (diffAB1 > 0 && diff < 0) || (diffAB1 < 0 && diff > 0) )
    {
        if (temp1 * diff == diffAB1) ans = 2 * (abs(temp1) - 1) + 2;
        else ans = 2 * abs(temp1) + 1;
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORC(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define dd long double

template<ll MOD = 998244353>
struct mint{
    ll x;
    ll mod = MOD;
    mint(ll x=0):x(x%MOD){}
    mint& operator+=(const mint a){
        if((x+=a.x)>=MOD) x-=MOD;
        return *this;
    }
    mint& operator-=(const mint a){
        if((x += MOD-a.x)>=MOD) x-=MOD;
        return *this;
    }
    mint& operator*=(const mint a){
        (x*=a.x)%=MOD;
        return *this;
    }
    mint operator+(const mint a) const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const{
        mint res(*this);
        return res*=a;
    }
    mint power(ll t) const{
        if(!t) return 1;
        mint a = power(t>>1);
        a*=a;
        if(t&1) a*=*this;
        return a;
    }

    mint inv() const{
        return power(MOD-2);
    }
    mint& operator/=(const mint a){
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const{
        mint res(*this);
        return res/=a;
    }
};
template<ll mod>
ostream & operator << (ostream & output,const mint<mod> & a){
        output<<a.x;
        return output;
}
template<ll mod>
istream & operator >> (istream & input, mint<mod>& a){
        input>>a.x;
        return input;
}

using mll=mint<>;
const ll N=1e6;
mll fact[N+1];
mll ifact[N+1];

void init(){
    fact[0]=fact[1]=1;
    FOR(i,2,N+1){
        fact[i]=fact[i-1]*i;
    }
    ifact[0]=1;
    ifact[1]=1;
    ifact[1]/=1;
    FOR(i,2,N+1){
        ifact[i]=1;
        ifact[i]/=i;
        ifact[i]*=ifact[i-1];
    }
}

mll pnc(ll n, ll r){
    mll a=fact[n];
    a*=ifact[r];
    a*=ifact[n-r];
    return a;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    ll n,m,k;
    cin>>n>>m>>k;
    mll ans=0;
    REP(i,k+1){
        mll temp=m;
        temp*=pnc(n-1,i);
        mll holder=(m-1);
        temp*=holder.power(n-1-i);
        ans+=temp;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 34772
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

//#define int long long
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

struct P
{
	int x, y;
	P(int x,int y):x(x),y(y){}
	P() :P(-1, -1) {}
};

int A[10];
int N;

bool solve()
{
	vector<int> va, vb;
	va.push_back(0), vb.push_back(0);
	rep(i, 0, 10)
	{
		if (va.back() < A[i])
		{
			va.push_back(A[i]);
		}
		else if (vb.back() < A[i])
		{
			vb.push_back(A[i]);
		}
		else
		{
			return false;
		}
	}
	return true;
}

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

	cin >> N;
	rep(i, 0, N)
	{
		rep(j, 0, 10)
		{
			cin >> A[j];
		}
		cout << (solve() ? "YES" : "NO") << endl;
	}

	return 0;
}


Measured memory_bytes: 3144
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i=0; i<N; i++) cin >> A[i];

    vector<int> L(A.begin(), A.end()-1);
    sort(L.begin(), L.end());

    long long total = accumulate(L.begin(), L.end(), 0LL);
    long long res = total + A[N-1];
    for (int i = 0; i < L.size(); i++) {
        total -= L[i] * 2;
        if (i % 2 == 0)
            res = max(res, total - A[N-1]);
        else
            res = max(res, total + A[N-1]);
    }
    cout << res << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a > b;
}
int main()
{
    int num[50],n,k,sum = 0;
    cin >> n >> k;
    for(int i = 0;i < n;i++)
    {
        cin >> num[i];
    }
    sort(num,num+n,cmp);
    for(int i = 0;i < k;i++)
    {
        sum += num[i];
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;

int main(void){
    string a;
    int m_Count = 0; 
    cin >>a;

    for(int i = 0; i < a.size() ; i++)
    {
        if(a[i] == '1')
            ++m_Count;
    }
    
    std::cout << m_Count<< std::endl;
}


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

int main(){
  int n,x[302][302]={},y[302][302]={};
  cin>>n;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)cin>>y[i][j],x[i][j]=y[i][j];
  
  int ans=max(y[0][n-1],y[n-1][0]);
  for(int i=0;i<n;i++)
    for(int j=n-2;j>=0;j--) {
      x[i][j]+=x[i][j+1];
      y[j][i]+=y[j+1][i];
      ans=max(ans,max(y[j][i],x[i][j]));
    }

  int sum[302][302],K[2][302][302]={};
  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++) sum[i][j]=-100000000;


  int t=0,f=1;
  while(f){
    t++,f=0;

    for(int i=0;i<n;i++) //yoko
      for(int j=i+1;j<n;j++) {//yoko
	int a=K[t%2][i][j];
	K[(t+1)%2][i][j]=a;
	sum[i][j]=-100000000;
	for(int k=a+1;k<n;k++) { //tate
	  int X=(x[a][i]-x[a][j+1])+(x[k][i]-x[k][j+1]);
	  int Y=(y[a+1][i]-y[k][i])+(y[a+1][j]-y[k][j]);
	  if(sum[i][j]<=X+Y)sum[i][j]=X+Y,K[(t+1)%2][i][j]=k;
	  ans=max(ans,sum[i][j]);
	}
	if(K[t%2][i][j]!=n-1)f=1;
	for(int k=K[t%2][i][j]+1;k<K[(t+1)%2][i][j];k++){//tate
	  sum[i][j]+=(x[k][i+1]-x[k][j])-(x[k-1][i]-x[k-1][j+1]);
	  ans=max(ans,sum[i][j]);
	}
      }
  }
  cout <<ans<<endl;
	  
  return 0; 
}

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

#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define vll vector<ll>
#define pll pair<ll , ll>
#define vpll vector<pair<ll, ll> >
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define N 100001
#define HOLE 1000000007

ll fn(ll x,ll rn[])
{
    if(rn[x]==x) return x;
    else return rn[x]=fn(rn[x],rn);
}

void un(ll x,ll y,ll rn[],ll sz[])
{
    x=fn(x,rn);
    y=fn(y,rn);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    sz[x]+=sz[y];
    rn[y]=x;
    return;
}

ll power(ll x,ll y)
{
    ll res = 1; // Initialize result

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x)%HOLE;

        // n must be even now
        y = y >> 1; // y = y/2
        x = (x * x)%HOLE; // Change x to x^2
    }
    return res;
}

vector <ll> adjl[N];
ll marked[N]={0};
vector <ll> order;

void dfs (ll x){

    if(marked[x])
        return;
    marked[x]=1;

    REP(i,0,adjl[x].size()){

    }

    return;
}

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

    ll q=1;
    //cin>>q;
    while(q--){

        ll n;
        cin>>n;

        ll a[n];

        int flag=0;


            cout<<(n/500)*1000+((n%500)/5)*5<<endl;


    }

return 0;
}


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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007

signed main()
{
	init();
	solve();
}

int cnt[3];
int card[3][1000];

void init()
{
	rep(i, 3) {
		CIN(string, s);
		int l = s.length();
		rep(j, l) {
			card[i][l-j-1] = s[j] - 'a';
		}
		cnt[i] = l - 1;
	}
}

void solve()
{
	int pl = 0;
	while (cnt[pl] != -1) {
		cnt[pl]--;
		pl = card[pl][cnt[pl]+1];
	}
	cout << (char) (pl + 'A') << endl;
}



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

using namespace std;

int matrix[11][11];

int main()
{
	int n,sum;
	
	for(;;)
	{
		cin>>n;
		if(n==0)break;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>matrix[i][j];
			}
		}

		for(int i=0;i<n;i++)
		{
			sum=0;
			for(int j=0;j<n;j++)
			{
				sum+=matrix[i][j];
			}
			matrix[i][n]=sum;
		}
		for(int j=0;j<n;j++)
		{
			sum=0;
			for(int i=0;i<n;i++)
			{
				sum+=matrix[i][j];
			}
			matrix[n][j]=sum;
		}
		sum=0;
		for(int i=0;i<n;i++)
		{
			sum+=matrix[i][n];
		}
		matrix[n][n]=sum;
		
		for(int i=0;i<=n;i++)
		{
			for(int j=0;j<=n;j++)
			{
				cout<<setfill(' ')<<setw(5)<<right<<matrix[i][j];
			}
			cout<<endl;
		}
	}
}

Measured memory_bytes: 0
import java.util.*;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String s = sc.next();

        Boolean ans = true;
        String strings[] = s.split("-");
        if(strings.length != 2)
            ans = false;
        else if(strings[0].length() != a)
            ans = false;
        else if(strings[1].length() != b)
            ans = false;

        if(ans)
            System.out.println("Yes");
        else
            System.out.println("No");
        sc.close();
        return;
    }
}


Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

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

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};

const int dx8[8] = {1,1,0,-1,-1,-1,0,1};
const int dy8[8] = {0,1,1,1,0,-1,-1,-1};

vector< vector<int> > Graph;
vector< int > value;





int main(int argc, const char * argv[]) {

    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int H,W; cin >> H >> W;
    vector<string> field(H);
    rep(i,H) cin >> field[i];
    
    vector<bool> row(W,false);
    vector<bool> col(W,false);
    
    rep(i,H)rep(j,W){
        if(field[i][j]=='#') {
            row[i] = true;
            col[j] = true;
        }
    }
    
    rep(i,H){
        if(!row[i]) continue;
        
        
        
        rep(j,W) if(col[j]) cout << field[i][j];
        
        
        cout << endl;
    }
}



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

int main(){
    int n; cin>>n;
    vector<int> a(n+2,0);
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=abs(a[i]-a[i-1]);
    }
    sum+=abs(a[n]);
    
    for(int i=1;i<=n;i++){
        cout<<sum-abs(a[i-1]-a[i])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1])<<endl;
    }
}

Measured memory_bytes: 1664
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int x, n;
	cin >> x >> n;
	VI p(n);
	REP(i, n) { cin >> p[i]; }
	vector<bool> is_enable(101 + 1, true);
	REP(i, n) { is_enable[p[i]] = false; }
	int result = x;
	int diff = INF;
	RANGE(i, 0, 101 + 1) {
		if(!is_enable[i]) {
			continue;
		}
		if(diff <= abs(i - x)) {
			continue;
		}
		diff = abs(i - x);
		result = i;
	}
	cout << result << endl;
	return 0;
}


Measured memory_bytes: 3628
n = int(input())
l = 1
s = {0}
r = []
for i in range(0, 10):
  t = set()
  for a in s:
    for b in [3, 5, 7]:
      t.add(a + (10 ** i) * b)
  r += t
  s = t
#print(sorted(r))
count = 0
for a in r:
  s = str(a)
  if (357 <= a <= n) and '3' in s and '5' in s and '7' in s:
    count += 1
print(count)


Measured memory_bytes: 10196
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int sum = 0;
    for (int i = 0; i < 5; i++) {
      int score = sc.nextInt();
      if (score < 40) {
        score = 40;
      }
      sum += score;
    }
    System.out.println(sum / 5);
  }
}


Measured memory_bytes: 26100
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = [[10**18]*(10**5+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(10**5+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        
        if j+v<=10**5:
            dp[i+1][j+v] = min(dp[i+1][j+v], dp[i][j]+w)

for i in range(10**5, -1, -1):
    if dp[N][i]<=W:
        print(i)
        exit()

Measured memory_bytes: 121068
import itertools
n = int(input())
l = list(map(int,input().split()))
ans = 0
for i, j, k in itertools.combinations(l, 3):
	if i + j > k > abs(i-j) or j + k > i > abs(j-k) or k + i > j > abs(k-i):
		if i != j and j != k and k != i:
			ans += 1
print(ans)

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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7 3");
            WillReturn.Add("3 2 2");
            //0
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 3");
            WillReturn.Add("1 4 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 1");
            WillReturn.Add("100");
            //99
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        var wkDict = new Dictionary<int, int>();
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            wkDict.Add(I, AArr[I]);
        }

        int SameCnt = 0;
        int PrevKey= -1;        

        while (wkDict.Count > 0) {
            //最大のものを選ぶ
            int MaxKey = -1;
            int MaxValue = -1;
            foreach (var EachPair in wkDict) {
                if (PrevKey == EachPair.Key) continue;

                if (EachPair.Value > MaxValue) {
                    MaxKey = EachPair.Key;
                    MaxValue = EachPair.Value;
                }
            }

            //Console.WriteLine("MaxKey={0},PrevKey={1}", MaxKey, PrevKey);

            if (MaxKey == -1) {
                SameCnt++;
                if (--wkDict[PrevKey] == 0) wkDict.Remove(PrevKey);
            }
            else {
                if (--wkDict[MaxKey] == 0) wkDict.Remove(MaxKey);
                PrevKey = MaxKey;
            }
        }
        Console.WriteLine(SameCnt);
    }
}


Measured memory_bytes: 3160
extern crate proconio;
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut dp = 1000;
    for i in 1..n {
        let nxt = dp % a[i - 1] + dp / a[i - 1] * a[i];
        dp = std::cmp::max(dp, nxt);
    }
    println!("{}", dp);
}


Measured memory_bytes: 2156
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;
 
struct State{
    int y, x, c;
    State(int y_, int x_, int c_) : y(y_), x(x_), c(c_) {}
};
 
int main(){
    int H, W, K;
    cin >> H >> W >> K;
 
    vector<string> field(H);
    for(int i=0;i<H;i++){
        cin >> field[i];
    }
    int si = -1, sj = -1;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(field[i][j] == 'S'){
                si = i;
                sj = j;
            }
        }
    }
 
    queue<State> que;
    que.emplace(si, sj, 0);
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    visited[si][sj] = true;
 
    const int dd[] = {0, 1, 0, -1, 0};
 
    int ans = H * W + 1;
    while(que.size()){
        auto s = que.front(); que.pop();
        if(s.y == 0 || s.y == H-1 || s.x == 0 || s.x == W-1){
            ans = 1;
            break;
        }
        int shortest = min(min(s.y, H-1 - s.y), min(s.x, W-1 - s.x));
        ans = min(ans, 1 + (shortest + K - 1) / K);
        if(s.c >= K) continue;
        for(int i=0;i<4;i++){
            int ny = s.y + dd[i], nx = s.x + dd[i+1];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || field[ny][nx] == '#') continue;
            if(!visited[ny][nx]){
                visited[ny][nx] = true;
                que.emplace(ny, nx, s.c+1);
            }
        }
    }
    cout << ans << endl;
    
    return 0;
}

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

using namespace std;

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

	int n;
	cin >> n;
	int arr[n];
	for(int i=0; i<n; i++){
		arr[i] = i+1;
	}
	int arrn[n];
	int arrq[n];
	for(int i=0; i<n; i++){
		cin >> arrn[i];
	}
	for(int i=0; i<n; i++){
		cin >> arrq[i];
	}

	int indekn = 0;
	int indekq = 0;
	int indeks = 0;
	do {

			indeks++;
			bool cekn = true;
			bool cekq = true;
			for(int i=0; i<n; i++){
				if(arr[i] != arrn[i])
					{
						cekn = false;

					}
				if(arr[i] != arrq[i])
					{
						cekq = false;

					}
			}
			if(cekn)
			{
				indekn = indeks;
			}
			if(cekq){
				indekq = indeks;
			}




	} while(next_permutation(arr,arr+n));
	cout << abs(indekq - indekn) << 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;

int main() {
  ll A, B, K;
  cin >> A >> B >> K;

  if (K <= A)
    cout << A - K << " " << B << endl;
  else if (K <= A + B)
    cout << 0 << " " << B - (K - A) << endl;
  else
    cout << 0 << " " << 0 << endl;
  return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;
struct UnionFind {
  vector<int> parent,s;
  UnionFind(int n): parent(n), s(n){
    rep(i,n) {
      parent[i] = i;
      s[i] = 1;
    }
  }
  int root(int x) { return parent[x]==x ? x : parent[x] = root(parent[x]); }
  bool same(int x, int y) { return root(x)==root(y); }
  int size(int x){ return s[root(x)]; }
  void unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return;
    if (s[x] < s[y]) {
      parent[x] = y;
      s[y] += s[x];
    } else {
      parent[y] = x;
      s[x] += s[y];
    }   
  }
};

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> a(n);
  UnionFind uf(n);
  rep(i,n) cin >> a[i];
  rep(i,m) {
    int x,y;
    cin >> x >> y;
    uf.unite(x-1,y-1);
  }
  
  int ans = 0;
  rep(i,n) if(uf.same(i,a[i]-1)) ++ans;
  cout << ans << endl;
}

Measured memory_bytes: 1408
s = input()
t = input()
lis = []
for i in range(len(s) - len(t) + 1):
    count = 0
    for j in range(len(t)):
        if t[j] == s[i + j] or s[i + j] == '?':
            count += 1
        else:
            break
    if count == len(t):
        temp = s[:i] + t + s[i + len(t):]
        lis.append(temp.replace('?', 'a'))
if len(lis) == 0:
    print('UNRESTORABLE')
else:
    lis.sort()
    print(lis[0])

Measured memory_bytes: 3064
def test
	ss = gets.chomp
	keys = %w(A C G T)
	cnt = 0
	ans = 0
	ss.each_char do |s|
		if keys.include?(s)
			cnt += 1
		else
			ans = cnt if cnt > ans
			cnt = 0
		end
	end
	[ans, cnt].max
end

puts test


Measured memory_bytes: 1788
#include <stdio.h>
#include<math.h>
#include <algorithm>
using namespace std;
int main(){
	int n,table[100],count;
	while(true){
		scanf("%d",&n);
		if(n == 0)break;
		for(int i=0; i < n; i++){
			scanf("%d",&table[i]);
		}
		count = 0;
		for(int i=n-2; i >= 0; i--){
			for(int k=0; k <= i; k++){
				if(table[k] > table[k+1]){
					swap(table[k],table[k+1]);
					count++;
				}
			}
		}
		printf("%d\n",count);
	}
}


Measured memory_bytes: 2584
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main() {
	ll N, A, B;
	cin >> N >> A >> B;
	cout << (A * (N / (A + B)) + min(A, N % (A + B))) << endl;
	return 0;
}

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

#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
const ll inf = 100100100100100;


vector<ll> dijkstra(int s, vector< vector<pair<int,ll>>> l, int v){
    vector<ll> dist; rep(i,0,v) dist.push_back(inf); dist[s] = 0;
    priority_queue< pair<int, ll>,vector<pair<int, ll>>,greater<pair<int, ll>>> que; que.push(make_pair(0,s));

    while(!que.empty()){
        pair<int,ll> p = que.top(); que.pop();
        int vertex = p.second;
        if(dist[vertex] < p.first) continue;
        rep(i,0,l[vertex].size()){
            pair<int,ll> to = l[vertex][i];
            if(dist[to.second] > dist[vertex] + to.first){
                dist[to.second] = dist[vertex] + to.first;
                que.push(make_pair(dist[to.second],to.second));
            }
        }
    
    }
    return dist;
}

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

    int v,e,s;
    cin >> v >> e >> s;
    vector<vector<pair<int,ll>>> alist;
    vector<pair<int,ll>> t;
    rep(i,0,v) alist.push_back(t);
    rep(i,0,e){
        int from, to, cost; cin >> from >> to >> cost;
        alist[from].push_back(make_pair(cost,to));
    }

   vector<ll> distances = dijkstra(s,alist,v);
   rep(i,0,v) if(distances[i] < inf) cout << distances[i] << endl; else cout << "INF" << endl;

}


Measured memory_bytes: 31744
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N;
  cin >> N;
  vl A(N);
  map<ll, ll> cnt;
  rep(i, N){
    cin >> A[i];
    cnt[A[i]]++;
  }

  stable_sort(A.begin(), A.end());

  vector<bool> dp(A[N - 1] + 1, true);

  ll ans = 0;
  vl done;

  rep(i, N){
    if(!dp[A[i]]) continue;
    
    if(cnt[A[i]] == 1) ans++;
    if((done.size() > 0) && (done[done.size() - 1] == A[i])) continue;

    done.push_back(A[i]);
    ll n = 2 * A[i];

    while(n <= A[N - 1]){
      dp[n] = false;
      n += A[i];
    }
  }
  
  cout << ans << "\n";
  
  return 0;
}


Measured memory_bytes: 21008
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
template <class T> inline bool  chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
int main() {
int n;
cin>>n;
string s;
cin>>s;
int ans=0,cnt=0;
for(int i=1;i<n;i++){
        cnt=0;
        for(char c='a';c<='z';c++){
                bool left=false,right=false;
                for(int j=0;j<i;j++){
                        if(s.at(j)==c)left=true;
                }
                        for(int j=i;j<n;j++){
                                if(s.at(j)==c)right=true;

                        }
                if(left&&right)cnt++;
        }
chmax(ans,cnt);
}
cout<<ans<<endl;
}


Measured memory_bytes: 256
S=input()
m=a=0
for i in range(len(S)):
    if S[i]=="A" or S[i]=="T" or S[i]=="C" or S[i]=="G":
        a+=1
    else:
        m=max(m,a)
        a=0
m=max(a,m)
print(m)


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

int main() {
  int from;
  int to;
  int index;
  
  int val;
  int val1;
  int val2;
  int val4;
  int val5;
  
  int count = 0;
  
  cin >> from >> to;

  for(index = from; index <= to; index++)
  {
    val = index;
    val1 = val / 10000;
    val = val % 10000;
    val2 = val / 1000;
    val = val % 1000;
    val = val % 100;
    val4 = val / 10;
    val5 = val % 10;
    
    if (val1 == val5 && val2 == val4)
    {
      count++;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll binpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int n;
int main()
{
    cin>>n;
    cout<<((binpow(10,n)-2*binpow(9,n)+binpow(8,n))%mod+mod)%mod<<endl;
    return 0;
}

Measured memory_bytes: 3608
import numpy as np
n = int(input())

def plus_idx(num):
  return 2 * int(np.ceil(np.log2(1 + 3*num)/2)) - 2

def minus_idx(num):
  return 2 * int(np.ceil(np.log2(1 + 3 * abs(num) / 2)/2)) - 1

def return_idx(num):
  if num == 0:
    return 0
  elif num > 0:
    return plus_idx(num)
  else:
    return minus_idx(num)
    
def minus_two_recur(num, l):
  if num == 0:
    return 0, l
  elif num > 0:
    idx = plus_idx(num)
    l[-(idx+1)] = 1
    new_num = num - (-2)**idx
    return new_num, l
  elif num < 0:
    idx = minus_idx(num)
    l[-(idx+1)] = 1
    new_num = num - (-2)**idx
    return new_num, l

num = n
max_length = return_idx(num)
result = [0] * (max_length+1)
while num != 0:
  num, result = minus_two_recur(num, result)

print("".join(map(str,result)))

Measured memory_bytes: 12504
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,i,j,k,l,m,a[301010];
char c;
string s;
std::vector<ll> q1 ;
map<ll,ll> q2;
set<ll> q3;
int main() {
   cin>>n;
   j=1;
   for(i=1;i<=n;i++)
   {
       cin>>k;
       if(k%2==0)
       {
           if(k%3==0||k%5==0)
           {
               
           }
           else {
               j=0;
           }
       }
   }
   if(j)
   {
       cout<<"APPROVED";
   }
   else {
       cout<<"DENIED";
   }
   
}

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

const int N = 2e5+45;
int a[N];
int h[N];

int main() {
  long long n, k; scanf("%lld%lld", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a+i);
    --a[i];
  }
  int pos = 0; bool done = false;
  for (int i = 1; i <= k; ++i) {
    if (!done && h[pos]) {
      int cycle = i-h[pos];
      k = (k-i)%cycle;
      done = true;
      if (!k) break;
      else k = i+k;
    }
    //printf("%d -> ", pos+1);
    h[pos] = i;
    pos = a[pos];
  }
  printf("%d", pos+1); 
  return 0;
}

Measured memory_bytes: 5328
/*input
3
1 2 3
5 2 2
*/
#include <bits/stdc++.h>

using namespace std;

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


#define FileIn(file) freopen(file, "r", stdin)
#define FileOut(file) freopen(file, "w", stdout)
#define syso(n) cout<<n<<endl;
#define sysom(message, n) cout<<message<<n<<\n;
#define all(c) c.begin(), c.end() 
#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define present(container, element) (container.find(element) != container.end())  //map, set
#define cpresent(container, element) (find(all(container),element) != container.end()) //vector
#define what_is(x) cout << #x << " is " << x << endl; 


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

ll lcm(ll fir, ll sec){
	return (fir*sec)/(gcd(fir, sec));
}


const int MOD = 1e9 + 7;
const string small_alphabets = "abcdefghijklmnopqrstuvwxyz";
const int month_days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// --
// -- 
// -- 
// std::cout << std::fixed;
// std::cout << std::setprecision(5) << f << '\n';


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

	ll a[n], b[n];
	for (int i = 0; i < n; ++i){
		cin>>a[i];
	}
	ll needed = 0;
	ll available = 0;
	for (int i = 0; i < n; ++i){
		cin>>b[i];
		if(b[i] < a[i]) {
			needed += a[i]-b[i];
		}
		else if(a[i] < b[i]) {
			available += (b[i] - a[i]) / 2;
		}
	}
	
	if(needed>available){
		syso("No");
		return 0;
	}
	syso("Yes");
	return 0;
}


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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  long long n;
  long long ans = 1e13;
  cin >> n;

  // vector<pair<long long, long long>> res;
  vector<long long> sum;
  for(long long i = 1; i * i <= n; i++){
    // cout << i << endl;
    if(n%i == 0){
      // res.push_back(make_pair(i, n/i));
      sum.push_back(i + n / i);
    }
  }
  for(int i = 0; i < sum.size(); i++){
    ans = min(ans, sum[i]);
  }
  cout << ans - 2 << endl;

  return 0;
}

Measured memory_bytes: 3504
use std::io;

fn main() {
    let mut s = String::new();
    io::stdin().read_line(&mut s).ok();
    let n: u64 = s.trim().parse().unwrap();

    let mut v: Vec<(u64, u64)> = (1..(n+1)).map(|e| (e, n/e))
        .filter(|(e, _)| e*e <=n).collect();
    let x = v[v.len()-1];
    let mut ans = 0;
    if x.0 == x.1 {
        ans += x.0 * x.0 * (x.0+1) / 2;
    } else {
        v.push((x.1, x.0));
    }
    // println!("{}", ans);
    for i in 0..(v.len()-1) {
        ans += v[i].0 * v[i].1 * (v[i].1 + 1) / 2;
        // println!("{}", ans);
        ans += v[i].0 * (v[i].0 + 1) * (v[i].1 - v[i+1].1) * (v[i].1 + v[i+1].1 + 1) / 4;
        // println!("{}", ans);
    }
    // println!("{:?}", v);
    println!("{}", ans);
}


Measured memory_bytes: 2188
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int a,b; cin >> a >> b;
  if ((a+b)&1) {
    cout << "IMPOSSIBLE" << endl; return 0;
  }
  cout << (a+b) / 2 << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [int(x) for x in input().split(' ')]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]

aa = 0
for i in range(1, n, 2) :
    aa += a[i]
b[0] = sum(a) - 2 * aa

for i in range(1,n) :
    b[i] = 2 * a[i-1] - b[i-1]
print(str(b).strip("[]").replace(",",""))

Measured memory_bytes: 14092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10; //1e-9?
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    string k; int d; cin >> k >> d;
    int n = k.length();

    auto dp = vec<ll>(n + 1, 2, d);
    dp[0][0][0] = 1;
    FOR(i, 0, n)FOR(small, 0, 2)eFOR(x, 0, (small ? 9 : k[i] - '0'))FOR(m, 0, d) {
        (dp[i + 1][small | (x < k[i] - '0')][(m + x) % d] += dp[i][small][m]) %= mod;
    }
    
    cout << (dp[n][0][0] + dp[n][1][0] - 1 + mod) % mod << "\n";
}

Measured memory_bytes: 17024
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
vector<int> vec;
char s[5],res[666];
inline int Q1(int l,int r) {
    printf("? ");
    for (int i=l;i<=r;++i)
        printf("%d%c",i,i==r?'\n':' ');
    fflush(stdout);
    char s[5];scanf("%s",s);
    return 2-(s[0]=='R');
}
inline int Q2() {
    printf("? ");
    for (int i=0;i<(int)vec.size();++i)
        printf("%d%c",vec[i],i+1==(int)vec.size()?'\n':' ');
    fflush(stdout);
    char s[5];scanf("%s",s);
    return 2-(s[0]=='R');
}
inline void go(int p,int x) {
    char ch=(x==1)?'R':'B';
    res[p]=ch;
}
int main()
{
    scanf("%d",&n);
    a=Q1(1,n);
    b=3-a;
    go(1,a);
    go(n+n,b);
    int left=1,right=n+1;
    while (left+1<right) {
        int mid=(left+right)>>1;
        int c=Q1(mid,mid+n-1);
        if (a==c) left=mid;
        else right=mid;
    }
    for (int i=right;i<=left+n-1;++i) vec.push_back(i);
    for (int i=1;i<right;++i) {
        vec.push_back(i);
        go(i,Q2());
        vec.pop_back();
    }
    for (int i=left+n;i<=n+n;++i) {
        vec.push_back(i);
        go(i,Q2());
        vec.pop_back();
    }
    int c1=n/2,c2=n/2;
    vec.clear();
    go(left,a);
    go(left+n,b);
    for (int i=1;i<left;++i) {
        if (c1&&res[i]=='R') vec.push_back(i),--c1;
        if (c2&&res[i]=='B') vec.push_back(i),--c2;
    }
    for (int i=left+n+1;i<=n+n;++i) {
        if (c1&&res[i]=='R') vec.push_back(i),--c1;
        if (c2&&res[i]=='B') vec.push_back(i),--c2;
    }
    for (int i=right;i<=left+n-1;++i) {
        vec.push_back(i);
        go(i,Q2());
        vec.pop_back();
    }
    printf("! ");
    puts(res+1);
    fflush(stdout);
    return 0;
}


Measured memory_bytes: 724
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;

    cin >> n;

    while (n--) {
        int a[3];

        cin >> a[0] >> a[1] >> a[2];
        sort(a, a + 3);

        if (a[2] * a[2] == a[0] * a[0] + a[1] * a[1]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1168
# https://atcoder.jp/contests/abc115/tasks/abc115_c
# C - Christmas Eve
import itertools

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

for _ in range(n):
    h_list.append(int(input().split()[0]))

h_list = sorted(h_list)

min_value = float('inf')

for i, v in enumerate(h_list[:-k+1]):
    diff_h = h_list[i+k-1] - v
    if diff_h < min_value:
        min_value = diff_h

print(min_value)


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

int main(void){
    int D, cbuf, sbuf, tbuf;
    vector<int> c;
    cin >> D;
    vector<vector<int>> s(D, vector<int>(26, 0));
    vector<int> t;
    for(int i=0; i<26; i++){
        cin >> cbuf;
        c.push_back(cbuf);
    }
    for(int i=0; i<D; i++){
        for(int j=0; j<26; j++){
            cin >> sbuf;
            s[i][j] = sbuf;
        }
    }
    for(int i=0; i<D; i++){
        cin >> tbuf;
        tbuf--;
        t.push_back(tbuf);
    }
    int satisfaction = 0;
    vector<int> last(26, -1);
    for(int i=0; i<D; i++){
        satisfaction += s[i][t[i]];
        last[t[i]] = i;
        for(int j=0; j<26; j++){
            satisfaction -= c[j]*(i-last[j]);
        }
        cout << satisfaction << endl;
    }
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)



struct RollingHash {
	vector<ll>hash;
	vector<ll>base_pow;
	ll base, mod;
	const ll DEFAULT_BASE = 1009, DEFAULT_MOD = 1e9 + 7;
	RollingHash(string S = "", ll base_ = -1, ll mod_ = -1) {
		base = (base_ > 0) ? base_ : DEFAULT_BASE;
		mod = (mod_ > 0) ? mod_ : DEFAULT_MOD;
		if (S.size() > 0)initialize(S);
	}
	void initialize(string& S) {
		int N = S.size();
		vector<int>s(N);
		for (int i = 0; i < N; i++)s[i] = S[i];
		initialize2(s);
	}

	void initialize2(vector<int>& S) {
		hash.resize(S.size() + 1);
		base_pow.resize(S.size() + 1);
		hash[0] = 0;
		base_pow[0] = 1;
		for (int i = 1; i <= S.size(); i++) {
			hash[i] = (hash[i - 1]*base + S[i-1]) % mod;
			base_pow[i] = base_pow[i - 1] * base % mod;
		}
	}

	//[a,b)
	ll between(int a,int b) {
		return (mod + hash[b] - hash[a] * base_pow[b - a] % mod)%mod;
	}
};


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

	int N;
	string S;
	cin >> N >> S;
	RollingHash rh1(S, 1007, 1e9 + 7), rh2(S, 1009, 1e9 + 9);

	int ans = 0;
	for(int len = 0;len <= N;len++){
		set<pair<ll, ll>>val;
		vector<pair<ll, ll>>v(N);
		int check = 0;
		for (int i = 0; i + len <= N; i++) {
			if (i >= len) {
				val.insert(v[i - len]);
			}
			v[i] = { rh1.between(i,i + len),rh2.between(i,i + len) };
			if (val.count(v[i])) {
				check = 1;
				break;
			}
		}
		if (check)ans = max(ans, len);
	}
	puts(ans);


	return 0;
}

Measured memory_bytes: 768
import java.util.Arrays;
import java.util.Scanner;

class Main {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int[] V = new int[N];
    int[] C = new int[N];
    for (int i = 0; i < N; i++) {
      V[i] = scanner.nextInt();
    }
    for (int i = 0; i < N; i++) {
      C[i] = scanner.nextInt();
    }
    int[] D = new int[N];
    for (int i = 0; i < N; i++) {
      D[i] = V[i] - C[i];
    }
    Arrays.sort(D);
    int ans = 0;
    for (int i = D.length - 1; i >= 0 && D[i] > 0; i--) {
      ans += D[i];
    }
    System.out.println(ans);
  }

}


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

const int INF = 1e9;
const int MOD = 1e9 + 7;

using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REPD(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i < int(b); i++)
#define FORD(i, a, b) for (int i = b - 1; i >= int(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main()
{
    string s;
    cin >> s;
    if(s == "ABC")
    cout <<  "ARC" << endl;
    else
    cout <<  "ABC" << endl;
}

Measured memory_bytes: 3596